62The decision map — pick the right structure on sight

In Chapter 61 we built the thirteenth and last container — Union-Find. That fills the volume's shelf: thirteen structures, thirteen chapters. This capstone doesn't add a fourteenth. Instead it teaches the one skill the other thirteen were quietly building toward — how to choose a structure on sight, the way a doctor reads a chart. Here's the plan. We lay all thirteen on a single master table, draw the flowchart that turns an access pattern into a structure, then throw the table away. The real move isn't memorising it; it's deriving it. All the way through we keep asking the one question that turns thirteen facts into a single reflex — what do I do to this data most, and which shape in memory makes that operation free? By the end you'll meet a fresh problem, name the operation you repeat most, and read the structure straight off it. Then we close the series — from a single bit in Volume 1 to the containers that organise a program's whole world.

01Every structure is one answer to one question

Rewind to the promise this volume opened with: a data structure is a deal you strike with memory — spend a little space here to make an operation instant there. Watch how every chapter signed that same deal differently. The array laid its elements in one contiguous block so that position i is a multiply-add away — O(1) index — and paid for it with O(n) inserts in the middle. The hash map scattered its entries across a sparse table so a key becomes an address — O(1) lookup — and paid with cache misses and empty slots. The heap folded a tree into a flat array so the minimum sits at index 0. And Union-Find — the structure we just left — shrank "are these connected?" to a walk up a parent-pointer forest flattened almost to nothing. Different shapes in RAM, each bending the cost of one operation down to the floor.

So the thirteen aren't thirteen facts to hoard. They're five shapes memory can take — a row, a grid, a sparse table, a hierarchy, a web — and a handful of variations on each. Hold the five shapes in your head and the whole volume collapses into something you can see.

First, though, let's lay all thirteen side by side — one page you could pin above a desk. Not to memorise, but so the pattern behind it becomes impossible to miss. →

02The master table — thirteen structures on one page

Here is the whole volume as a lookup. Read each row as a profile: what shape it takes in RAM, what one slot costs, and — the columns that matter — which operations it makes cheap and which it makes expensive. The green cells are what each structure is for; the red-ish O(n) cells are the price it charges everywhere else. No structure is green across the board. That's the entire point: every structure is fast at something by being slow at something else.

Those space numbers aren't guesses — they're measured. The container's own overhead per element, on CPython 3.12, spans a striking 50× range: a packed byte for a bytearray, up through the 8-byte reference of a list, to the ~93 all-in bytes a dict spends to buy you O(1) keys.

import sys
from collections import deque

sys.getsizeof([])                                        # -> 56    empty list = just the header
(sys.getsizeof(list(range(10000)))  - 56) / 10000        # -> 8.0   B/item  · one 8-byte reference
(sys.getsizeof(deque()))                                 # -> 760   a deque pre-allocates a block
(sys.getsizeof({i:i for i in range(10000)}) - 64)/10000  # -> 29.5  B/item  · sparse-table slots only
(sys.getsizeof(set(range(10000)))  - 216) / 10000        # -> 52.4  B/item  · a set is even sparser

Line by line: an empty list is 56 bytes of header and nothing else. Grow it to ten thousand elements and each one adds exactly 8.0 bytes — the contiguous array of references we built back in the array chapter, over-allocation already amortised in. A deque starts at 760 bytes because it eagerly grabs a whole memory block to make both ends O(1). The dict spends 29.5 bytes per entry on table machinery alone — and once you add the boxed key and value objects (~32 B each for a big int), it's ~93 bytes all-in to record one key→value pair. That's the price of O(1) by key: emptiness. A hash table must stay mostly empty to stay fast.

A table is a lookup, and lookups are for people who already know what they want. The harder skill is arriving with a vague problem and walking out with a structure. That's a flowchart — and here it is, made clickable. →

03The decision flowchart — from access pattern to structure

Forget the thirteen names for a moment and ask a single question about your data: what do I do to it most? Not occasionally — most, in the hot loop, a million times. Every branch below is a different answer to that one question, and each lands on the structure whose layout makes that answer O(1) (or as close as the problem allows). Read it top-down: identify your dominant access pattern, follow the branch, arrive at the container.

Now make it yours. Below, toggle the operation you'd do most and the flowchart hands back the structure — plus the one-line reason its layout wins. There's no "best" button, because there is no best structure. There's only the one whose shape makes your hot operation free.

The flowchart tells you which structure. But to trust it, you have to feel why the same operation can be free in one and ruinous in another. Pick an operation and watch all thirteen sort themselves. →

04Same operation, every structure — watch the costs sort out

Here's the claim the whole table rests on: costs aren't assigned, they're forced by the layout. "Get the item at position i" is O(1) on an array because the address is arithmetic — base + i·8, computed and read in one step. It's O(n) on a linked list because position isn't stored anywhere; the only way to reach the i-th node is to start at the head and follow next i times. Same operation, same name, two layouts — and the layout, not the operation, decides the price.

Play with it and the punchline lands: the array wins "index i" and loses "insert at front"; the hash map wins "by key" and can't even offer "position i"; the heap owns "remove the minimum" and is useless for membership. There is no row that's green everywhere. Choosing a structure is choosing which column you want green and which you can afford to leave red.

import timeit
# SAME job — remove from the front 2000 times — on two layouts:
timeit.timeit("q.pop(0)",    "q=list(range(100000))", number=2000)                  # -> ~0.33 s   list: O(n) shift
timeit.timeit("q.popleft()", "from collections import deque;"
                             "q=deque(range(300000))", number=2000)                  # -> ~5e-5 s   deque: O(1)

# SAME question — is it present? — scanned vs hashed:
timeit.timeit("99999 in c", "c=list(range(100000))", number=1000)                   # -> ~0.64 s   list: O(n)
timeit.timeit("99999 in c", "c=set(range(100000))",  number=100000)                 # -> ~0.003 s  set:  O(1)

Line by line, and every number here was RAN: popping the front of a list is O(n) because every remaining element shifts down one slot — ~0.33 s for 2000 pops. A deque does the same removal in O(1) by moving a pointer, not the data — about 6000× faster on this machine. Then membership: scanning a list for a value is O(n), and 1000 worst-case scans of 100k elements cost ~0.64 s; a set hashes straight to the answer, so a hundred times as many checks finish in ~0.003 s. Same goals, different layouts, and the gap is the difference between a snappy app and a hung one. (Timings are machine-dependent; the ratios are the point.)

You've now seen the table, the flowchart, and the costs. Time to throw the table away — because the people who are genuinely good at this don't carry it in their heads at all. →

05You don't memorise the table — you derive it

Here's the 1% move, and it's smaller than you'd think. Faced with any problem, the expert doesn't scan a mental list of thirteen structures. They ask one question: "what's the operation I'll do most — and which layout makes that operation O(1)?" Answer it, and the structure is no longer a choice you agonise over; it's a consequence you read off. Need constant lookup by an id? A layout that turns a key into an address → hash map. Need the next-smallest thing again and again? A layout that keeps the minimum at the front → heap. Suggesting words as someone types? A layout with one node per letter → trie. The structure falls out of the operation.

One question — "what do I do most, and which layout makes it O(1)?" — is the entire volume, distilled. Which means you're ready for the last section: where a person goes once the containers stop being mysterious. →

06Where you go from here — a bit, a structure, a system

Step back and look at the whole climb. Volume 1 started at a single bit — a box in RAM that's 0 or 1 — and built up through bytes, addresses, references, and the heap until a Python object was something you could picture down to its header. Volume 2 made that machine program: files, modules, tests, concurrency. Volume 3 taught it to think: Big-O, the memory hierarchy, divide-and-conquer, greedy, DP, the algorithms that turn brute force into elegance. And this volume, Volume 4, gave those algorithms their containers — the thirteen shapes that decide, before a single line of logic runs, what's cheap and what's ruinous. Bit → byte → object → structure. You can now trace a program's data from the metal all the way up to the shape it lives in.

So where next? Outward, into systems built from exactly these parts. Open any database and you'll find our structures load-bearing: an index is a B-tree (a fat, disk-friendly BST) or a hash index; write-optimised stores like Cassandra and RocksDB layer LSM-trees over sorted arrays and heaps; a query planner walks a DAG. Step up to distributed systems and the same shapes reappear, hardened for scale: consistent hashing is a hash map wrapped around a ring so machines can join and leave without reshuffling the world; Merkle trees — hash trees — let Git, Bitcoin, and Amazon's Dynamo verify terabytes by comparing a single root hash; bloom filters trade a little accuracy for a set that fits in a breath of memory; CRDTs let two offline copies of a structure merge without conflict. None of these is new magic. Each is one of your thirteen, chosen because its layout makes the system's hottest operation cheap — the exact reasoning you now own.

And that's the quiet gift of this whole series. You didn't memorise thirteen containers or two dozen algorithms; you learned to look at a problem and see the shape it wants — the operation underneath, the layout that makes it free, the price you're willing to pay elsewhere. That reflex doesn't expire. It's the same move whether you're picking a Python dict, designing a database index, or sketching a system on a whiteboard for a million users. Start from a bit; ask what you do most; choose the shape that makes it O(1). You began this series not knowing what a variable really was. You're leaving it able to reason about the machine from the transistor to the distributed cluster — from first principles, all the way up. Go build something, and pick your structures on sight.

This closes Volume 4 — and the series. Your next move isn't another chapter here; it's a real system. Take the reflex you built and open the door marked databases and distributed systems: B-trees on disk, LSM-trees under your writes, hash rings across a fleet, Merkle trees keeping it all honest. Same thirteen shapes, bigger stage. You're ready. →