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, or a network.
- Match against the toolbox, and accept a structure only if its weak operations are ones the program rarely performs.
Step 3 is the one people skip. Every structure in this course is bad at something, and a choice is only safe once you have checked that the weakness sits somewhere the program never goes.
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 or dedupe by key | dict or 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 and pop, O(1) peek, 8-1 |
| sorted order with fast inserts | balanced BST | O(log n) everything, 7-3 |
| fewest steps between things | graph plus BFS | ring-by-ring search, 5-3 and 9-2 |
| reachability or cluster counts | graph plus DFS | stack-driven coverage, 9-3 |
| totals over every consecutive range | sliding window | items enter once, leave once, 3-3 |
| O(1) splice with the node in hand | linked list | pointer rewiring, 4-2 |
Two structures barely appear in the left column, arrays and linked lists, and that is not a demotion. 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 an entire tree with no pointers at all, as lesson 8-3 showed.
So the table has two layers. The upper rows are what you reach for by name, and the bottom two are the materials those names are made of, which is why understanding them was worth four units.
This calls for a doubly linked list.
The next and prev pointers give O(1) steps in both directions, and lesson 4-3 showed O(1) insert and delete whenever the node itself is in hand, which the premise supplies.
An array fails on the middle insert. Adding a song after the current one shifts every later song, which is O(n), and a playlist is exactly where mid-list edits happen.
What the problem does not ask is as informative as what it does. Search by title never appears, so nothing here needs O(1) key lookup.
If searching by title were also hot, the answer would not be to swap structures. It would be to add a dict mapping titles to nodes, keeping the list for the ordering and the dict for the lookup, which is how real systems compose structures rather than picking one.
A size-10 min-heap, the top-k pattern from lesson 8-2.
Each score is one O(log 10) push plus at most one pop, which is about four steps regardless of whether the player base is 2 million or 200 million. Reading the top 10 is just the heap's contents.
Re-sorting 2 million entries per score is O(n log n) every time, which at thousands of scores per second is hopeless. Keeping a sorted list is no better, since each insert pays O(n) shifting.
A BST is the trap worth naming. Scores arriving in any near-sorted run would build the degenerate chain from lesson 7-3, dragging every operation to O(n).
The memory side matters too. The heap holds ten numbers rather than two million, so the leaderboard's cost does not grow with the player count at all.
The core is a dict, a hash table mapping each key to its count.
Lookup and update are O(1) per request, which is exactly the tally pattern from lesson 6-3, and it holds no matter how many keys exist.
The operation named in the problem is lookup by key, not by position and not by priority, and that phrase alone selects the structure. Any scanning structure would be O(n) per request across millions of keys, which for a rate limiter means the limiter itself becomes the bottleneck.
Real limiters add more than a count. They track timestamps or per-window buckets, often the deque from lesson 5-2 held as the dict's value, but the hash table remains the engine that finds the right client in one step.
The reason was cache locality: contiguous memory is cache-friendly, since CPUs read neighbors nearly free, while pointer-chasing scatters the reads.
Big-O deliberately ignores constant factors, and hardware does not. Sequential reads through one block are often 10 to 100 times faster than hopping across scattered nodes, because each fetch brings along the neighbors that are about to be needed.
That gives a clean tiebreaker. When the paper costs tie, prefer the contiguous layout, which is why a Python list beats a hand-rolled linked list for most everyday work.
The rule does not invert the analysis, though. When paper costs differ by a growth family, paper wins, and no cache advantage rescues an O(n) operation from an O(log n) one once n gets large.