One question decides everything
Every structure in this course answered the same prompt: which operations must be fast? So choosing a structure is not memorization, it is translation. Take the problem, list the operations it performs constantly, and match them:
- Name the hot operations. "Look up by ID", "always take the most urgent", "serve in arrival order", "read by position".
- Name the required orders. Arrival order? Sorted order? Priority order? Nesting? A network?
- Match against the toolbox, and only accept a structure whose weak operations are ones you rarely do.
The toolbox on one screen
| you constantly need | reach for | why |
|---|---|---|
| read by position | list (array) | O(1) index formula (2-1) |
| grow at the end | list | amortized O(1) append (2-2) |
| lookup / dedupe by key | dict / set | O(1) hashing (6-1) |
| newest first | list as stack | LIFO, O(1) both ops (5-1) |
| oldest first | deque | FIFO, O(1) both ends (5-2) |
| most urgent first | heapq | O(log n) push/pop, O(1) peek (8-1) |
| sorted order + fast inserts | balanced BST | O(log n) everything (7-3) |
| fewest-steps between things | graph + BFS | ring-by-ring search (5-3, 9-2) |
| reachability / cluster counts | graph + DFS | stack-driven coverage (9-3) |
| totals over every consecutive range | sliding window | items enter once, leave once (3-3) |
| O(1) splice with node in hand | linked list | pointer rewiring (4-2) |
Two structures barely appearing in the left column, arrays and linked lists, are still everywhere: they are what the others are BUILT FROM (hash buckets are arrays, deques are linked blocks, and a heap is an array whose index arithmetic — children at 2i+1 and 2i+2 — encodes the whole tree, lesson 8-3).
Quiz
A music app needs: skip to the next song, go back to the previous song, and insert a song right after the current one, all O(1), given the current song in hand. Which structure?
Quiz
A leaderboard shows the top 10 of 2 million players and receives thousands of new scores per second. Hot operations: insert a score, read the current top 10. Which fits best?
Problem
A web server must ensure each API key makes at most 100 requests per minute. The hot operation is "given this key string, find its request count, fast, millions of times". Which structure is the core of this rate limiter?
Quiz
The honest tiebreaker: two structures both handle your hot operations in O(1)-ish time. Lesson 4-3 gave a reason the ARRAY-BASED one usually wins in practice. What was it?