Abstract Data Structures (HL): Stacks, Queues, Lists, Trees and Graphs
What the exam tests
Abstract data structures tests how data is organized and operated on independently of its implementation. HL questions cover stacks, queues, linked lists, binary trees and graphs, including operations, traversals, applications and complexity.
Core rules
- An ADT defines behavior (operations); a data structure is a concrete implementation.
- Stack: LIFO; push, pop, peek, isEmpty. Used for recursion, undo, expression evaluation.
- Queue: FIFO; enqueue, dequeue, front, isEmpty. Used for scheduling and buffering.
- Linked list: nodes hold data and a next pointer; insertion/deletion at a known position is O(1), but search is O(n).
- Binary search tree: left subtree values are smaller, right subtree values larger; in-order traversal gives sorted output.
- Graph: vertices and edges; directed/undirected, weighted/unweighted; represented by adjacency matrix or list.
Worked example
Insert 50, 30, 70, 20, 40 into a BST. 50 is the root; 30 goes left; 70 goes right; 20 goes left of 30; 40 goes right of 30. In-order traversal visits left, root, right: 20, 30, 40, 50, 70. Reasoning: in-order traversal of a BST is always ascending, but the tree shape depends on insertion order; sorted insertion can produce a degenerate O(n) tree.
Traps
Confusing in-order, pre-order and post-order; using a stack where FIFO is required; forgetting empty-structure checks; assuming a BST is always balanced; saying linked-list access is O(1); ignoring memory overhead of pointers.