IB Computer Science HL Topic 5 (Abstract Data Structures)

imported from computersciencecafe.com

​​2D arrays

A data structure that stores elements in a grid-like format with rows and columns.

Stacks

A data structure that follows the Last-In-First-Out (LIFO) principle, where elements are added and removed from the same end.

Queues

A data structure that follows the First-In-First-Out (FIFO) principle, where elements are added to one end and removed from the other end.

Heaps

A tree-based data structure that is used to implement priority queues, where the highest priority element is always at the root.

Linked lists

A data structure that stores elements in nodes, where each node contains a value and a pointer to the next node.

Double linked lists

A linked list where each node has a pointer to both the next and the previous node.

Circular linked lists

A linked list where the last node points to the first node, creating a circular structure.

Pointers

A variable that stores the memory address of another variable.

Binary trees

A tree-based data structure where each node has at most two children.

Non-binary trees

A tree-based data structure where each node can have more than two children.

Nodes

An individual element of a data structure, such as a linked list or a tree.

Parent node

A node that has one or more children.

Left-child node

The child node of a parent that appears to the left.

Right-child node

The child node of a parent that appears to the right.

Subtree node

A smaller tree that is part of a larger tree.

Root node

The topmost node in a tree.

Leaf node

A node that has no children.

Tree traversal

The process of visiting all nodes in a tree data structure.

Pre-order traversal

A type of tree traversal where the root node is visited first, followed by the left subtree and then the right subtree.

Post-order traversal

A type of tree traversal where the left subtree is visited first, followed by the right subtree, and then the root node.

In-order traversal

A type of tree traversal where the left subtree is visited first, followed by the root node, and then the right subtree.

Recursion

A programming technique where a function calls itself.

Base case

The terminating condition for a recursive function.

Recursive case

The condition where a recursive function continues to call itself.