62The decision map — pick the right structure on sight

In Chapter 61 we built the thirteenth and last container, Union-Find. With it the volume's shelf is full: thirteen structures across thirteen chapters. This capstone doesn't add a fourteenth. Instead it teaches the one skill the other thirteen were quietly building toward. That skill is how to choose a structure on sight, the way a doctor reads a chart. Here's the plan. First we lay all thirteen on a single master table. Then we draw the flowchart that turns an access pattern into a structure. Then we throw the table away, because the real move isn't memorising it, it's deriving it. The whole way through we keep asking 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. You 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 position i is a multiply-add away. That buys O(1) index, and it pays 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. That buys O(1) lookup, and it pays 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 really five shapes memory can take: a row, a grid, a sparse table, a hierarchy, and a web. Each of the thirteen is one of those five with a handful of variations. Hold the five shapes in your head and the whole volume collapses into something you can see.

Let's make the five shapes concrete before we lean on them. The row is the array, the list, and the string, with elements laid end to end. The grid is the 2D array and the matrix, a row of rows. The sparse table is the hash map and the set, mostly-empty slots addressed by a key. The hierarchy is the tree family: the binary search tree, the heap, the trie, and Union-Find's parent forest. The web is the graph, where any node may point at any other. Thirteen names, five shapes. Once you can sort a new structure into one of these five, you already half-know its costs.

Try the sorting on a structure we haven't named yet. A stack — push on top, pop from the top — is just a row you only ever touch at one end, so it inherits the row's O(1) append and needs nothing new. A priority queue that always hands back the smallest item is a hierarchy, a heap wearing a friendlier name. Neither is a fourteenth shape. Once you see the shape underneath, its costs are already half-written, because you met them in the chapter that built that shape.

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 single lookup, with each row read as a profile. It tells you what shape the structure takes in RAM, what one slot costs, and which operations it makes cheap or expensive. The green cells are what each structure is for, and the red-ish O(n) cells are the price it charges everywhere else. Notice that 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. It runs from 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

Let's read it 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. That's the contiguous array of references we built back in the array chapter, with 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. Add the boxed key and value objects at about ~32 B each for a big int, and it reaches ~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.

Why does the table stay partly empty in the first place? Because a hash map only stays O(1) while collisions stay rare, and collisions get common the moment the table fills up. So CPython holds it to about two-thirds full: for every 2 entries it keeps roughly 3 slots, which leaves 1 slot in 3 sitting empty on purpose. Pack it tighter and keys start landing on top of one another, and every lookup slows to a scan. The emptiness isn't sloppiness. It's the headroom the O(1) promise is bought with.

Let's sanity-check one of those numbers by hand. Take a list of 10,000 references: at 8.0 bytes each that's 80,000 bytes for the slots, plus the 56-byte header, so about 80,056 bytes in total. Divide back out and the per-element cost is essentially 8 bytes, exactly the array-of-references picture. The dict tells the opposite story. To keep collisions rare it holds its entries in a table that stays only about two-thirds full, so roughly a third of its slots sit empty on purpose. That deliberate emptiness isn't waste — it is the O(1) lookup you paid for.

Do the same for the dict's all-in figure and it checks out. The 29.5 bytes of table machinery per entry come first. Then the key and the value are separate heap objects, about 32 bytes each for a big int. Add them up: 29.5 + 32 + 32 comes to 93.5, which rounds to the ~93 bytes we quoted. So a single dict entry costs more than eleven bare list slots, and every one of those bytes is buying you the O(1) key lookup.

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, but most, in the hot loop, a million times over. Every branch below is a different answer to that one question. Each branch 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, and arrive at the container.

Here's what "dominant access pattern" means in the flesh. Say you're counting how often each word appears in a book. The operation you do most is "take this word and bump its count," millions of times over. That's a lookup by key, so the layout that turns a key into an address wins, and you reach for a dict. Now say you're instead always asking "what's the smallest unfinished task?" That's remove-the-minimum, over and over, so the layout that keeps the minimum at the front wins, and you reach for a heap. Same reasoning, two problems, two shapes. You never listed all thirteen. You named the hot operation and let it point.

Two branches we skipped, just to complete the five. Say the hot operation is "what's at row r, column c" on a game board. That's access by coordinate, and a grid answers it with one multiply-add: on a 100-wide board, cell (3, 4) sits at offset (3·100 + 4)·8 = 2432 bytes from the base, read in a single step. Or say the hot operation is "who is connected to whom" — friends, links, roads. That's a web, and a graph stores each node's neighbours right beside it. Five access patterns, five shapes. Name the operation and the shape is already chosen.

One more, because the reflex only sticks with reps. Say you're serving autocomplete, and the hot operation is "find every word that starts with ca." That's a prefix query. The layout that stores one node per letter and shares common stems wins, so you reach for a trie. Now change the question to "is this exact word in my spellcheck list?" The prefix stops mattering, plain membership wins, and a set answers in O(1). Same words, two questions, two shapes. The data never told you which structure to use. The operation did.

INPUTfrom collections import deque

# one suitcase, one Sunday night, five verbs
pocket = {"passport": "LM4820913", "boarding pass": "NZ0148 14C"}   # by KEY
days   = ["linen shirt", "tee + shorts", "swimsuit", "smart shirt"] # by POSITION
door   = []                                                         # LIFO
gate   = deque(["A17", "A18", "A19"])                               # FIFO
packed = {"socks", "toothbrush", "charger"}                         # MEMBERSHIP

for last_minute in ("charger", "keys", "sunglasses"):
    door.append(last_minute)                    # thrown on the pile, top last

print("passport         ->", pocket["passport"])          # dict   - one key, no scan
print("day 3 outfit     ->", days[2])                     # list   - one address
print("grab on the way  ->", door.pop())                  # stack  - newest first
print("             then->", door.pop())
print("boarding next    ->", gate.popleft())              # queue  - oldest first
print("             then->", gate.popleft())
print("socks packed?    ->", "socks" in packed)           # set    - one probe
print("towel packed?    ->", "towel" in packed)
print("still by door    ->", door, "| still queued ->", list(gate))

print()
verbs = [("by a key",        "dict",  "hash the key, land on the slot"),
         ("by position",     "list",  "base + i*8, one read"),
         ("newest first",    "stack", "append / pop, one end only"),
         ("oldest first",    "deque", "popleft, no shifting"),
         ("is it in there?", "set",   "hash the value, look once")]
for verb, structure, why in verbs:
    print(f"  {verb:16} -> {structure:6} : {why}")

OUTPUTpassport         -> LM4820913
day 3 outfit     -> swimsuit
grab on the way  -> sunglasses
             then-> keys
boarding next    -> A17
             then-> A18
socks packed?    -> True
towel packed?    -> False
still by door    -> ['charger'] | still queued -> ['A19']

  by a key         -> dict   : hash the key, land on the slot
  by position      -> list   : base + i*8, one read
  newest first     -> stack  : append / pop, one end only
  oldest first     -> deque  : popleft, no shifting
  is it in there?  -> set    : hash the value, look once

Now make it yours. Below, toggle the operation you'd do most and the flowchart hands back the structure, along with the one-line reason its layout wins. There's no "best" button, because there is no best structure — 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 pure arithmetic — you compute base + i·8 and read it in one step. The same operation is O(n) on a linked list because position isn't stored anywhere, so 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. The layout, not the operation, decides the price.

Put real numbers on that gap. Suppose both structures hold a million items and you want the last one. On the array you compute one address and read it, a single step no matter how big the array grows. On the linked list you follow next from the head, so reaching the millionth node means a million pointer-hops. One step versus a million, and nothing changed but the shape the data lives in. That is what forced by the layout means. The verb is identical, and the price is set purely by how you can reach the data.

Play with it and the punchline lands in a single sweep. The array wins "index i" but 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. Every winner is somebody's loser, so 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.

Put a number on "loses insert at front." Take an array of a million items and push one new element onto the front. Every existing item has to slide up one slot to make room, so that's a million writes for a single insert. A hash map asked to store one new key does one write and is done. A million versus one, the same lopsided gap as before, and again nothing changed but the shape the data lives in. The array put position at your fingertips, and the bill for that comes due the instant you disturb position.

And that isn't bad luck you could engineer away — it's forced. A layout can only put one thing at your fingertips: the array puts position there, the hash map puts the key there, the heap puts the minimum there. Optimising for one arrangement of bytes necessarily de-optimises the others, because the bytes can only sit in one arrangement at a time. That's why the green cell always drags a red cell behind it. There is no free lunch in memory, only a choice of which meal you're buying.

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. That costs ~0.33 s for 2000 pops. A deque does the same removal in O(1) by moving a pointer, not the data. That's 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, but 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 stops being a choice you agonise over. It becomes 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. It 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, and the algorithms that turn brute force into elegance. And this volume, Volume 4, gave those algorithms their containers. Those are 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 else a hash index. Write-optimised stores like Cassandra and RocksDB layer LSM-trees over sorted arrays and heaps, and 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, which are 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. That's 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, and 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.

from collections import deque
import heapq

# 1 - "keep only the last 3 messages"  -> newest in, oldest falls out  -> deque(maxlen)
chat = deque(maxlen=3)
for msg in ["hey", "you up?", "landed", "bag lost", "found it"]:
    chat.append(msg)
print("1  last 3 messages     ->", list(chat), " (deque, ch52 - the ends are the verb)")

# 2 - "top 3 scores, inserted constantly" -> always-max -> a size-k heap
top = []
for score in [412, 980, 77, 1503, 640, 1201, 88]:
    heapq.heappush(top, score)
    if len(top) > 3:
        heapq.heappop(top)                       # evict the smallest of the keepers
print("2  top 3 scores        ->", sorted(top, reverse=True),
      " (heapq, ch58 - the root IS the answer)")

# 3 - "is this a word?" a million times -> membership -> set
words = {"the", "graph", "python", "metal", "structure"}
print("3  'python' a word?    ->", "python" in words,
      "| 'pythom'?", "pythom" in words, " (set, ch54 - one probe, any size)")

# 4 - "suggest as they type 'we'" -> prefix -> trie (a dict of dicts)
trie = {}
for city in ["wellington", "westport", "whanganui", "auckland"]:
    node = trie
    for ch in city:
        node = node.setdefault(ch, {})
    node["$"] = True

def suggest(trie, prefix):
    node = trie
    for ch in prefix:
        node = node.get(ch)
        if node is None:
            return []
    out = []
    def walk(n, sofar):
        if "$" in n:
            out.append(sofar)
        for ch, kid in n.items():
            if ch != "$":
                walk(kid, sofar + ch)
    walk(node, prefix)
    return out

print("4  suggest('we')       ->", suggest(trie, "we"),
      " (trie, ch59 - stand on the prefix, read below)")

# 5 - "are these two accounts the same person?" -> merge + ask -> union-find
parent = {}
def find(x):
    parent.setdefault(x, x)
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root
def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        parent[rb] = ra

for a, b in [("u1", "u7"), ("u7", "u9"), ("u2", "u5")]:
    union(a, b)
print("5  u1 and u9 the same? ->", find("u1") == find("u9"),
      "| u1 and u2?", find("u1") == find("u2"),
      " (union-find, ch61 - forget the route, keep the label)")

print("\nfive problems, five verbs, zero memorising:")
for verb, pick in [("both ends, bounded", "deque"), ("always the max", "heap"),
                   ("is it in there?", "set"), ("what starts with...", "trie"),
                   ("same group?", "union-find")]:
    print(f"   {verb:20} -> {pick}")
print("\nyou never chose a structure. you named the verb, and it chose itself.")

# ---------------- OUTPUT, verbatim (CPython 3.12.7) ----------------
# 1  last 3 messages     -> ['landed', 'bag lost', 'found it']  (deque, ch52 - the ends are the verb)
# 2  top 3 scores        -> [1503, 1201, 980]  (heapq, ch58 - the root IS the answer)
# 3  'python' a word?    -> True | 'pythom'? False  (set, ch54 - one probe, any size)
# 4  suggest('we')       -> ['wellington', 'westport']  (trie, ch59 - stand on the prefix, read below)
# 5  u1 and u9 the same? -> True | u1 and u2? False  (union-find, ch61 - forget the route, keep the label)
#
# five problems, five verbs, zero memorising:
#    both ends, bounded   -> deque
#    always the max       -> heap
#    is it in there?      -> set
#    what starts with...  -> trie
#    same group?          -> union-find
#
# you never chose a structure. you named the verb, and it chose itself.

# ------------------------------------------------------------------
# 1  last 3, newest in / oldest out ..... deque(maxlen=3)       ch52-53
# 2  top 3, inserted all day ............ a size-3 heap         ch58
# 3  "is this a word?", a million times . set                   ch54
# 4  "what starts with we?" ............. trie: dict-of-dicts   ch59
# 5  merge pairs, then "same person?" ... union-find            ch61
#
# And that is the end of the book. Sixty-two chapters ago you were not
# sure what a variable really was. You are leaving able to hear the verb
# inside a messy problem and reach, without looking, for the shape that
# makes that verb free. Nobody can take that back off you.
#
# Close the tab. Open an editor. Go find a problem worth the reflex.
# ------------------------------------------------------------------

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. →