Computer Science · Topic Cheatsheet
Topic 4 · Abstract Data Structures (HL)
22 key results accumulated across 4 chapters.
Stack (LIFO)
Ch 1
push/pop at the top. Undo, call stack.
Queue (FIFO)
Ch 1
enqueue rear, dequeue front. Scheduling.
Array
Ch 1
O(1) access by index; O(n) front/middle insert (shifting).
Linked list
Ch 1
Nodes + next pointers; O(1) insert, but no direct access.
Trade-off
Ch 1
Random access → array; lots of insert/delete → linked list.
Recursion
Ch 2
Calls itself toward a base case: `f(n)=n*f(n-1)`, `f(1)=1`.
Base case
Ch 2
Stops recursion; without it → stack overflow.
Call stack
Ch 2
Calls push (wind up), resolve LIFO (unwind).
Binary tree
Ch 2
≤ 2 children. Root (no parent), leaf (no children).
Traversals
Ch 2
Pre (root,L,R) · In (L,root,R = sorted for BST) · Post (L,R,root).
Big-O
Ch 3
O(1) < O(log n) < O(n) < O(n log n) < O(n²).
Linear search
Ch 3
O(n); any list.
Binary search
Ch 3
O(log n); SORTED list only — halves each step.
Bubble sort
Ch 3
O(n²); swaps adjacent pairs, largest bubbles to the end.
Dictionary / Hash table
Ch 4
Key→value map. Hash function turns key into bucket index. O(1) average lookup, insert, delete.
Hash function
Ch 4
Deterministic map from key to integer; good ones spread keys evenly across buckets.
Collision
Ch 4
Two keys hash to same bucket. Resolved by chaining (linked list per bucket) or open addressing (probe next slot).
Load factor
Ch 4
items / buckets. Above ~0.7 collisions hurt performance — table resizes (doubles).
Hash table vs BST
Ch 4
Hash = O(1) avg, NO order. BST = O(log n), preserves sorted order. Pick by need.
When to use
Ch 4
Stack: undo / call stack / DFS. Queue: print queue / BFS / scheduling. Hash: keyed lookup. BST: ordered + lookup. Array: random access. Linked list: many inserts.
Space-time trade-off
Ch 4
Hash tables sacrifice MEMORY for SPEED. A recurring pattern in CS — caches, indexes, memoisation are all instances.
Big-O hierarchy
Ch 4
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). At n=10⁶, the gap between O(1) and O(n²) is 10⁶.