⚡ Rapid revision — the 20-minute version
| Spine | The mark |
|---|---|
| Choose by operations | Array = O(1) access; linked list = O(1) insert — the access pattern decides |
| Stack vs queue | LIFO reverses; FIFO preserves — the order question |
| Trees | Balanced BST: lookup/insert/delete O(log n) — halves every step |
| Hash tables | O(1) average; collisions chained or probed |
| Binary search | Halving — ONLY on sorted data |
| Big-O | Growth rate, not machine speed — nested loops multiply: n² |
1. Data structures — organise for the operations you need
Data structure: A way of ORGANISING data so the operations you need are fast. The choice question is always: which operations dominate — access by position? insert/remove often? search by key? There is no best structure, only the right one for the access pattern. An ALGORITHM is the step-by-step procedure; complexity measures how it SCALES.
Worked: an undo feature needs last-in-first-out → stack. A printer queue needs first-in-first-out → queue. A dictionary lookup by word → hash table. Name the operation pattern, then the structure — that pairing is the mark.
2. Arrays — index addressing
Array: Elements in CONTIGUOUS memory, addressed by INDEX (0-based in most languages). Access by index: O(1) — direct address arithmetic. Insert/delete in the middle: O(n) — every later element shifts. 2D arrays address as [row][col], stored row by row. Fixed size in many languages — overflow is a design failure, not a surprise.
Worked: scores[4] reads the 5th element instantly (one address computation). Inserting at position 0 of a 1,000-element array moves 1,000 elements. Random access → array; frequent middle inserts → linked list. The trade-off IS the answer.
3. Stacks and queues — the two disciplines
Stack and queue: STACK: LIFO — push adds to the top, pop removes from the top (call stack, undo, expression evaluation, backtracking). QUEUE: FIFO — enqueue at the rear, dequeue from the front (printers, task scheduling, breadth-first search). Both are ABSTRACT types: any underlying storage that keeps the discipline qualifies.
Worked: push A, B, C then pop twice → C then B (reverse order of arrival). Enqueue A, B, C then dequeue twice → A then B (arrival order). The order question is the exam's staple: stack REVERSES, queue PRESERVES.
4. Linked lists — nodes and pointers
Each NODE holds data + a POINTER to the next node; the head anchors the chain; the last points to null. Insert at head: O(1) — rewire two pointers, no shifting. Search: O(n) — must walk the chain; no random access (unlike arrays). Doubly linked adds a prev pointer; a circular list links the tail back to the head. The trade-off: arrays win on access, lists win on insert/delete without shifting.
5. Trees and graphs — hierarchy and networks
Tree and graph: TREE: hierarchical nodes — one root, no cycles. BINARY SEARCH TREE: left descendants are smaller, right descendants larger — lookup, insert, delete all O(log n) when balanced (degrades to O(n) if it becomes a linked chain). GRAPH: VERTICES joined by EDGES — directed/undirected, weighted/unweighted; models maps, networks, dependencies. Traversal: BFS (level by level, uses a QUEUE) vs DFS (deep first, uses a STACK or recursion).
Worked: find 7 in a balanced BST of 1..15 — compare at root 8 (go left), then 4 (go right), then 6 (go right), found: 3 comparisons for 15 elements — that halving IS O(log n). Shortest unweighted path → BFS; explore all dependencies deeply → DFS. Structure + traversal matched to the job.
6. Hash tables — key to bucket
Hash table: A HASH FUNCTION maps a key to a bucket index: average O(1) insert, lookup, delete. COLLISIONS (two keys, one bucket) are handled by CHAINING (a list per bucket) or OPEN ADDRESSING (probe the next free slot). Worst case degrades to O(n) when everything collides — the load factor (entries ÷ buckets) is kept low by resizing.
Worked: 'obi' hashes to bucket 11, stored there in O(1). 'ada' also hashes to 11 → chaining appends it to bucket 11's list; lookups in that bucket now scan the chain. The hash function's QUALITY decides the speed — that is why 'design a good hash' questions exist.
7. Searching — linear vs binary
Binary search: LINEAR search: check each element in turn — O(n), works on ANY list. BINARY search: check the MIDDLE, discard half, repeat — O(log n), but ONLY on a SORTED list (the trap: applying it to unsorted data silently returns wrong answers). One million sorted elements: linear up to 1,000,000 comparisons; binary about 20 — the halving is the whole story.
Worked: find 42 in [3, 8, 15, 42, 67] — middle 15 (go right), middle 42 — found in 2 comparisons. The list MUST be sorted; sorting costs O(n log n), so for ONE search linear is cheaper — binary pays off on repeated searches. Name the precondition; it is the marked line.
8. Sorting — the growth families
| Algorithm | Complexity | Character |
|---|---|---|
| Bubble sort | O(n²) | Swap neighbours; simple, slow, easy to trace |
| Merge sort | O(n log n) | Divide, sort halves, merge — predictable, stable |
| Quick sort | O(n log n) average, O(n²) worst | Partition around a pivot; fast in practice, bad pivots hurt |
Worked: bubble on [5, 3, 8, 1] — pass 1: 3,5,1,8; pass 2: 3,1,5,8; pass 3: 1,3,5,8 — three passes, n−1 worst case each: O(n²). Merge halves the work each level (log n levels × n merge work). The exam wants the COMPLEXITY CLASS matched to the algorithm, and bubble traced by hand.
9. Big-O — how it scales, not how fast it runs
Big-O: Big-O gives the GROWTH RATE as input size n rises, ignoring constants and small terms: O(1) constant, O(log n) halving, O(n) linear, O(n log n) good sorts, O(n²) nested loops, O(2ⁿ) brute-force subsets. The trap: Big-O says NOTHING about machine speed or constant factors — an O(n²) on ten items beats an O(n) on ten million. Nested loops over n multiply: n × n = O(n²).
Worked: for i in n { for j in n { work } } → n² operations: at n = 1,000 that is a million — the nested loop is the visual signature. Halving the search space each step is log n. 'What is the complexity of...' is answered by counting the LOOPS, not the lines.
10. Summary — the DS&A spine
| Question type | Method beat | Trap |
|---|---|---|
| Choose a structure | Dominant operation decides | No universal best — match the access pattern |
| Stack vs queue | LIFO reverses; FIFO preserves | Pop order vs dequeue order |
| Binary search | Halve — but ONLY sorted data | Silently wrong on unsorted input |
| Hash tables | Hash to bucket; chain or probe collisions | Worst case O(n) — average is the O(1) |
| Complexity | Count the loops; halving = log | Constants and machine speed are NOT Big-O |
| Traversal | BFS queue, level order; DFS stack, deep | Match traversal to the question asked |
Command discipline: 'state the complexity' = the class, no derivation needed; 'justify' = the growth-rate reason (halving, nesting); 'show' = trace the algorithm on the GIVEN data, every pass written down. DS&A papers pay for the SCALING argument — a number without the growth reason earns half.