Data structures — where your data lives

00What a data structure really is

Before the thirteen structures, one idea that all of them are made of. A data structure is two things welded together: a way of arranging data in memory, and the set of operations that arrangement makes cheap. That's the whole subject. By the end of this chapter you'll be able to look at any structure — one you've used for years or one you meet on page 200 — and ask the three questions that actually matter: how is it laid out in RAM, what does each operation cost, and when is it the right tool. Get fluent at those three and you've got most of what "good at data structures" means.

A data structure is a deal you strike with memory

Here is the oldest puzzle in the field, and it has nothing to do with code. A phone book lets you find a person's number in seconds — flip to the surname, done. But hand you a number and ask whose it is, and that same book is agony: you'd read every line. Same data. Same paper. The arrangement — sorted by name — made one question instant and left the other impossible. That trade is the entire discipline. Every data structure is a deal: spend a little space arranging things this way, and some operation you care about becomes cheap; in return, some other operation gets expensive. There is no free arrangement, only arrangements tuned to different questions.

To make the deal concrete you have to see the arrangement in memory. Recall Volume 1: RAM is one enormous row of numbered boxes, each holding a byte, each with an address. A value doesn't float in the abstract — it sits at an address. So "arranging data" literally means deciding which addresses hold what, and how the pieces find each other. Take three songs and store them two ways. Pack them into one contiguous block — slot after slot, no gaps. Or scatter them anywhere and have each one hold a pointer (an address) to the next. Same three songs; two completely different deals with memory.

Look at what the picture already tells you, before a line of code. In the array, item #3 is at a computable address — base + 2×8 — so you leap to it in one step. In the linked version the nodes sit at unrelated addresses (@6280, @1032, @4160); the only thing that knows song #2 follows song #1 is the pointer stored inside song #1. Want the third song? You have no choice but to follow the chain. Two arrangements of identical data, and one made "jump to position k" instant while the other made it a walk. That gap is not a Python quirk — it's forced by where the bytes physically sit.

If the arrangement lives in memory, we'd better be fluent in the memory it lives in. One page of Volume 1, refreshed →

Memory is the substrate everything sits on

Every structure in this volume is built out of exactly three Volume 1 facts, so let's nail them. One: a name is an 8-byte reference — x = song doesn't copy the song, it stores the song's address (8 bytes, because this is a 64-bit machine). Two: every Python object carries a header before its actual data — a reference count and a pointer to its type — roughly 16 bytes of pure bookkeeping on top of whatever it holds. Three: objects live on the heap, scattered; the things that organize them — lists, dicts — are just other objects holding references to them. Data structures are almost never about the values. They're about the arrangement of references to the values.

Don't take my word for the sizes — measure them. sys.getsizeof reports an object's byte cost, and the numbers are strikingly regular:

import sys

sys.getsizeof(object())   # 16   — the bare header: refcount + type pointer
sys.getsizeof(1)          # 28   — that 16-byte header + the integer's digits
sys.getsizeof([])         # 56   — an empty list is not free: header + growth bookkeeping
sys.getsizeof(list(range(100)))   # 856

# so what does one more slot in a list actually cost?
(856 - 56) / 100          # 8.0  bytes per slot

Read it top to bottom. A bare object() is 16 bytes — that's the header alone, the tax every Python object pays. A small int is 28: the same header plus room for its digits. An empty list already costs 56 bytes, because a list is a real object with its own header and its own record of how much room it's holding. Fill it with 100 items and it's 856 bytes — and the arithmetic on the last line is the punchline: (856 − 56) / 100 = 8.0. Each item you add costs the list exactly 8 bytes. Not the size of the value — 8 bytes, the size of one reference. The list stores addresses; the 28-byte integers themselves live elsewhere on the heap. A Python list is a contiguous array of 8-byte references, exactly as Volume 1 promised.

There's a wrinkle worth knowing now, because it recurs all volume. That empty list was 56 bytes with room for zero items — so where does the first item's slot come from? Watch the size jump as you append: 56, then 88, then it holds steady, then leaps to 120, then 184. The list grabs slots in batches, not one at a time, keeping spare capacity so most appends touch memory it already owns. That's the dynamic array trick — Volume 3's amortized O(1) append — and Chapter 01 takes it apart bolt by bolt.

We can see the layout and price the bytes. But a "stack," a "queue," a "map" — those are promises, not pictures. Where do the promises end and the pictures begin? →

The contract and the implementation are two different things

Here's the distinction that separates people who use data structures from people who understand them. A structure has two layers. The contract (also called the abstract type) is the promise: the operations it offers and what they mean. A stack promises three — push (add to the top), pop (remove the top), peek (look at the top) — and swears the last thing in is the first thing out. That's it. The contract says nothing about memory. The implementation is the arrangement that keeps the promise: you can back a stack with a contiguous array, or with scattered linked nodes. Same contract. Different pictures in RAM. And — this is the whole point — different costs.

Two words people mix up, so let's be precise. A node is a container that holds a value and the pointer(s) to its neighbours; the value is just the payload inside it. When we say a linked list is "scattered nodes," the scattering is the nodes; the values they point to are scattered too, but separately. The contract only ever talks about values ("give me the top"). The implementation is what decides whether getting that value is a leap or a walk.

So the same operation can be O(1) or O(n) depending on the layout. Which means we can't judge a structure by vibes — we have to price it. Here's the price list, and why it reads the way it does →

We grade a structure by what its operations cost

You choose a structure the way you'd choose a vehicle — not by how it looks, but by what it makes cheap. For every structure we ask the cost of four operations, plus its space, and we express each as a Big-O in n (Volume 3's yardstick): access (reach the k-th item), search (find a value), insert, and delete. The magic is that you can derive each cost by reasoning about the layout — you never have to memorize a table. Access on a contiguous array is O(1) because the address is base + k×8, one multiply-and-add regardless of k. Access on linked nodes is O(n) because the only route to node k is through the k−1 pointers before it. The layout forces the cost.

Search shows the same logic, and it's the one you feel every day. Asking "is x in here?" of a plain list means scanning until you find it or run out — O(n). Asking the same of a set means computing x's hash into an address and looking in one spot — O(1). Different arrangement (a sparse hash table, Volume 1 ch7), radically different cost for the identical question. Timed on this machine:

data  = list(range(100_000))    # the same values, two arrangements
sdata = set(data)
    target = 99_999   # a value near the end (worst case for the scan)

target in data      # scan every slot until found/absent  → O(n)
target in sdata     # hash the key, look at one bucket     → O(1)

# measured, best of many runs on this machine:
#   x in list  ≈ 565,000 ns   (half a millisecond)
#   x in set   ≈      51 ns   (~11,000× faster for the SAME question)

Line by line: data and sdata hold the exact same 100,000 numbers — only the arrangement differs. The membership test reads identically in code (target in …), so the contract is the same. But the list must walk its slots while the set jumps to a hashed address, and the stopwatch reports the difference bluntly: about half a millisecond versus about fifty nanoseconds — roughly eleven thousand times faster (a machine-dependent ratio, but the shape — O(n) versus O(1) — is not). You didn't write smarter code. You picked a smarter arrangement. That is the entire skill, in one line.

But two structures with the same Big-O can still run at wildly different speeds. Big-O is the algorithm; the metal has opinions of its own →

Same Big-O, different metal — and the humans who saw it

Big-O deliberately throws away the constant factor (Volume 3), and that's usually the right call — but the constant is where the hardware lives, and sometimes it roars. Recall the memory hierarchy: the CPU never fetches one byte, it drags a whole cache line — 64 contiguous bytes — into fast memory at once. A contiguous array is a gift to that machine: touch element 0 and elements 1 through 7 ride along for free, already in cache when you reach them. Pointer-chasing a linked list is the opposite: each node lives at an unrelated address, so following a pointer can mean a fresh trip to slow RAM — a cache miss — even though the operation count is identical. Same O(n) walk, very different real speed.

An honest caveat, because this volume doesn't sell you clean stories. In pure Python the effect is muted — summing a two-million-element list versus a linked chain of the same values clocked 46.5 ms against 59.3 ms here, only about 1.3× apart, because the interpreter's own overhead swamps the cache penalty and Python's integers are scattered heap objects either way. Drop to C or NumPy, where the values are packed inline, and the same contrast can be 10× or more. So: the cache principle is real and it governs serious systems, but its size depends on how close to the metal you are. We'll feel it at full force in Chapter 06 (matrices) and the heap.

None of these arrangements grew on trees — a person had to see them. That's the part worth stealing. Someone looked at a key like "session_9f3a" and thought: what if I could turn the key itself into an address, so I never search at all? — and the hash table was born. Someone stared at a branching tree and realized it could live in a flat array with no pointers, a child's position computed by arithmetic from its parent's — and the heap became the fast thing it is. The structures are frozen insights. Learning them is really learning the moves the insights make: turn a lookup into an address, turn a shape into arithmetic, turn a walk into a jump.

If the access pattern picks the structure, then choosing well is a decision you can actually make on sight. Here's the decision — the one this whole volume is teaching you to make →

The one skill: match the access pattern to the layout

Everything so far collapses into a single move. You have a problem. It has a dominant operation — the thing your code does far more than anything else. Name that operation, and the structure almost picks itself, because each family exists to make one access pattern cheap. Need to keep things in order and reach them by position? That's the LINEAR family — arrays and their kin. Need to jump to a value by a key? KEYED — the hash map. Always need the smallest or largest next? HIERARCHY — the heap, a tree in an array. Data that's a grid of rows and columns? GRID — the matrix. Things defined by their connections? NETWORK — the graph. Five families, five access patterns. The thirteen structures are variations within them.

One honest edge, so you don't over-trust the map: real problems often have two hot operations that pull toward different families, and then you either compose structures (a dict of lists, a heap beside a hash map — you'll build exactly these) or accept a compromise. That tension is the interesting part of the job, not a failure of the method. The map gets you to the right neighbourhood; judgment picks the house.

Enough framework. Time to build. Chapter 01 opens the LINEAR family with the array — the single contiguous block your Python list has secretly been all along — and shows how it turns one slot of spare capacity into amortized-O(1) growth, and why "insert at the front" is the operation that quietly wrecks it. →

01The array — the block everything is built on

A data structure is a deal you strike with memory, and the array is the first deal — the one every other structure in this volume is negotiated from. It is nothing but a contiguous block of equal-size slots, laid end to end in RAM with no gaps. That one choice — same-size boxes, packed tight — is what makes reaching the millionth element exactly as cheap as reaching the first, and it is also what makes inserting in the middle expensive. By the end of this chapter you'll see why indexing is O(1) and a middle insert is O(n) — not as rules to memorise but as facts forced by the layout — why Python's list grows in sudden jumps, why a list of a million integers costs 36 MB while the same numbers packed cost 8, and when the array is the container to reach for. Which, more often than you'd guess, it is.

One block, equal slots, no gaps

Start from the metal. Volume 1 drew RAM as one long row of numbered boxes, each box one byte, each with an address — its number in the row. An array is the simplest possible way to store a sequence in that row: pick a slot size, then lay the elements down in consecutive slots starting at some address. That starting address is the array's base. The slot size — how many bytes each element occupies — is the stride. Nothing marks where one element ends and the next begins except the fact that they're all the same width, so the machine can always find element i by counting: skip i strides from the base.

The word doing all the work is contiguous — "touching, in one unbroken run." The slots are neighbours in physical memory. There is no header between them, no pointer from one to the next, no bookkeeping. That absence is the whole trick, and everything good and bad about the array flows from it.

If the position of element i is nowhere written down, how does the machine find it instantly? It doesn't look. It calculates →

Why indexing is O(1): one multiply-add

Here is the array's superpower, and it's pure arithmetic. To find element i, the machine computes its address directly:

address(i) = base + i × stride

One multiply, one add. The CPU forms that address and reads the slot — no scanning, no comparing, no walking from the front. It does not matter whether i is 0 or 9,999,999: the same two operations land on the exact byte. That is what O(1) — constant time — means: the cost doesn't grow with the size of the collection. This is the payoff Volume 1 (ch6) promised when it called a Python list "a contiguous array of references": indexing is a jump, not a search.

We can watch the formula on real memory. The array module gives us a block of packed 8-byte slots and will hand back the true base address of slot 0:

import array
A = array.array('q', [10, 20, 30, 40, 50])   # 'q' = signed 8-byte slots
base, length = A.buffer_info()                # the REAL address of slot 0
for i in range(length):
    print(i, base + i * A.itemsize)           # itemsize == stride == 8
# 0 2606972461072
# 1 2606972461080   <- exactly 8 bytes on from slot 0
# 2 2606972461088
# 3 2606972461096
# 4 2606972461104

Line 3 asks the array for its base address — an actual location in this process's RAM. Line 5 applies the formula: slot i sits at base + i × 8. The printed addresses climb by exactly 8 each step, no gaps — proof the slots are contiguous, and proof that reaching any one is a single multiply-add. The machine never touched slots 0–3 to find slot 4; it computed straight to it.

And it's flat in the clock, not just in theory. Timing index access on lists of wildly different sizes (machine-dependent numbers, but the shape is the point):

import timeit
for n in (1_000, 100_000, 10_000_000):
    L = list(range(n))
    t = timeit.timeit(f"L[{n//2}]", globals={"L": L}, number=2_000_000)
    print(n, round(t/2e6*1e9, 1), "ns")
# 1000       13.9 ns
# 100000     13.7 ns
# 10000000   14.4 ns   <- a 10,000x bigger list, same access time

Reaching the middle of a thousand-element list and the middle of a ten-million-element list both cost about 14 nanoseconds on our machine. The list grew ten-thousand-fold; the access time didn't budge. That is O(1) you can see on a stopwatch.

Instant reads sound like a free lunch. They aren't — the same tight packing that makes index a jump makes the middle a wall →

The price of the packing: the shift

The array's contiguity is a promise: no gaps, ever. Reads love that promise. Inserts hate it. Suppose you want to slip a new track into the middle of the playlist, at position i. There is no empty slot waiting there — slot i is occupied by its neighbour, and its neighbour by its neighbour, all the way to the end. To open a hole at i without breaking the "no gaps" promise, every element from i onward must slide one slot to the right. That's n − i elements moved for a single insertion. Delete in the middle and it's the same in reverse: everything after the hole shifts left to close it.

So insertion and deletion are O(n) — the cost grows with how much sits after the cut. Insert at the very end (i = n) and nothing shifts: cheap. Insert at the front (i = 0) and all n elements move: worst case. The measurement is unambiguous — inserting at the front of lists ten times larger costs ten times more:

import timeit
for n in (10_000, 100_000, 1_000_000):
    L = list(range(n))
    t = timeit.timeit("L.insert(0, 99)", globals={"L": L}, number=1000)
    print(n, round(t/1000*1e6, 1), "us per front-insert")
# 10000        1.7 us
# 100000      17.1 us    <- 10x the elements, ~10x the shift
# 1000000    185.0 us    <- and again: linear, O(n)

Each L.insert(0, 99) forces CPython to shove every existing element up one slot before writing the new value into slot 0. As n goes 10k → 100k → 1M, the time goes 1.7 → 17 → 185 microseconds — a clean straight line. There's the O(n), lived. (Appending to the end of these same lists, by contrast, runs in tens of nanoseconds — thousands of times faster, because it shifts nothing.)

The array so far has a fatal-sounding flaw: a fixed size. Lay six slots and you've committed to six. So how does list — which you .append to forever — live on top of it? →

Static vs dynamic: how a fixed block grows

A raw array is static: its length is fixed the moment it's allocated, because the slots after it may belong to something else. Python's list is a dynamic array — the same contiguous block, wrapped in a trick that lets it grow. The trick is overallocation: the list quietly asks for more slots than it currently needs, and keeps the spare capacity in reserve. Appending just writes into the next spare slot and bumps a length counter — O(1), no copying. Only when the spare runs out does the list allocate a bigger block, copy everything across, and free the old one.

You can watch the reserve fill and refill. sys.getsizeof reports the block's real byte size; it only changes when the underlying capacity does:

import sys
L, size = [], sys.getsizeof([])          # empty list header = 56 bytes
for i in range(40):
    L.append(i)
    s = sys.getsizeof(L)
    if s != size:                        # only prints when it RESIZED
        print(len(L), s, "bytes  capacity", (s - 56)//8)
        size = s
# 1   88 bytes  capacity 4
# 5  120 bytes  capacity 8
# 9  184 bytes  capacity 16
# 17 248 bytes  capacity 24
# 25 312 bytes  capacity 32
# 33 376 bytes  capacity 40

The empty list is a 56-byte header with zero slots. The first append jumps it to capacity 4 (88 = 56 + 4×8); appends 2, 3, 4 are then free — they fill the reserve without changing the size. The 5th append exhausts capacity 4, so CPython grows to 8, copies the four elements over, and carries on. The pattern of capacities — 4, 8, 16, 24, 32, 40 — shows the block growing by a shrinking proportion each time, roughly 1.125×, not doubling. The gaps between resizes are why almost every append is cheap.

Doesn't that copy-everything resize make append secretly O(n)? Sometimes — a single append that triggers a resize really does move all n elements. But it happens so rarely (only when capacity fills) that spread across all the appends, the average cost stays constant. That's amortized O(1) — the honest-average accounting from Volume 3 (ch3). Timing the whole build proves it: the per-append cost stays flat even as the list grows 100×.

# build a list of n by appending, then divide total time by n
100_000  appends:  ~28 ns each
1_000_000 appends:  ~38 ns each
10_000_000 appends: ~40 ns each     <- flat: amortized O(1) per append

That last line hides the biggest surprise in this chapter. A Python list of a million numbers is far heavier than a million numbers — and the reason is what the slots actually hold →

References vs values: why a list weighs 4× an array

Here's the twist that trips up almost everyone. A Python list's slots do not hold your numbers. They hold references — 8-byte addresses (Volume 1: a name is a reference) pointing to full int objects that live scattered elsewhere on the heap. Each of those integer objects carries the ~28-byte object header every Python object pays (refcount, type pointer, the digits). So one integer in a list costs you two things: 8 bytes in the contiguous slot block, plus ~28 bytes for the boxed object it points at. The block is tidy and contiguous; the values it references are strewn across memory.

The array module offers the other layout — a packed array that stores the raw values directly, no per-element object, no reference indirection. The size difference is not subtle. We measured it:

import sys, array
n = 1_000_000
L = list(range(n))
A = array.array('q', range(n))            # packed 8-byte values

sys.getsizeof(L)                          # 8_000_056  → just the references
sum(sys.getsizeof(x) for x in set(L))     # 28_000_000 → the boxed ints behind them
sys.getsizeof(A)                          # 8_183_816  → raw values, no boxing

The list's slot block is ~8 MB — a clean million 8-byte references. But follow those references and you find a million 28-byte int objects: another ~28 MB. The list's true footprint is about 36 MB (≈36 bytes per element). The packed array holds the identical numbers in ~8.2 MB (~8 bytes each). Same data, 4.4× less memory — because the array pays no object tax and stores no pointers, just values back to back.

Lighter is only half the win. The packed block is also the shape the CPU physically runs fastest over — and that's not a metaphor, it's the cache →

Why the metal loves a block: cache locality

Big-O counts operations and treats every memory access as one unit. The hardware disagrees, and the array is where the disagreement pays off. Recall the memory hierarchy from Volume 3 (ch2): an L1 cache hit costs ~1 ns, a miss out to RAM ~100 ns, and the CPU never fetches one byte — on every miss it hauls in the whole surrounding cache line, ~64 bytes. For a packed array of 8-byte values that's eight neighbours per fetch: one miss, then seven free hits. Walk the block in order and the prefetcher, seeing the straight march, fetches the next line before you ask. A contiguous scan is, quite literally, the fastest thing a CPU does.

To prove the speed comes from the layout and nothing else, walk the same block twice — once in order, once through a shuffled set of indices. Identical reads, identical count, only the address pattern differs:

import timeit, random
n = 5_000_000
data = list(range(n))
seq  = list(range(n))                     # visit 0,1,2,... in order
rnd  = list(range(n)); random.shuffle(rnd)   # same indices, shuffled
def walk(order):
    s = 0
    for i in order: s += data[i]
    return s
# walk(seq): ~140 ms
# walk(rnd): ~1139 ms   → 8.1x slower, exact same reads

Both loops touch every element exactly once and add it up — same n, same O(n), same interpreter overhead per step. The only difference is that seq marches through consecutive addresses (cache-friendly) while rnd leaps to random ones (a miss almost every time). Result: the ordered walk ran ~8× faster on our machine. That gap is not in the operation count — Big-O is identical. It's the constant the layout bakes in, and it's why the contiguous array beats a scattered structure with the same complexity.

Light, instant to index, cache-loving, cheap to append. It's no accident this is where every other structure begins →

The 1% move: the array is the default, and the foundation

Being "good at data structures" is mostly knowing which one fits the access pattern — and the array is the default, the one others must earn their way past. Its profile: O(1) indexing, O(1) amortized append, unbeatable cache behaviour, minimal overhead (packed: ~8 bytes/element; boxed list: ~36) — in exchange for O(n) middle inserts/deletes and, when packed, a fixed element type. So the rule is sharp: if you access by position, iterate in order, and grow at the end, use an array. Reach for something else only when your dominant operation is middle churn, keyed lookup, or hierarchical order — and the chapters ahead are exactly those "something elses."

The human insight worth taking with you is the one that made all of it possible: turn position into arithmetic. Someone realised that if you fix the slot size, an element's location stops being something you store and search for and becomes something you compute — base + i × stride, one multiply-add. That single idea — address as a formula — is the seed of the whole field. A stack and a queue are arrays with a rule about which end you touch. A heap is a tree flattened into an array where a node's children are found by arithmetic (2i+1, 2i+2). A matrix is an array indexed by row × width + col. Even a hash table (Volume 1, ch7) is an array whose index you compute from the key. Learn to see the block under all of them and the rest of this volume stops being thirteen unrelated tricks and becomes variations on one move.

The everyday transfer is real too: a parking garage numbers its spaces so you find yours by arithmetic instead of wandering; a packed shelf shoves every book down when you wedge one into the middle. The array is the oldest idea in computing because it's the most human one — put things in a row of equal boxes, and you'll always know where each one is.

Chapter 02 unbolts the block. The linked list throws away contiguity, scatters its elements as nodes joined by pointers, and buys back the one thing the array can't do cheaply — O(1) insertion in the middle — at the price of the multiply-add that made indexing free. Two structures, opposite deals with memory. →

02The linked list — data joined by pointers

Chapter 1 gave you the array: one contiguous block, every element a neighbour of the next. The linked list is its exact opposite. Each element becomes a separate little object on the heap — a node — that holds its value and a pointer to where the next node lives. Order stops being about addresses and starts being about arrows. By the end of this chapter you'll know precisely why inserting into a linked list is O(1) when you already hold the spot, why finding that spot is O(n), why a scattered list crawls even though it's "the same" O(n) as an array — and when that trade is the one you want.

Order without neighbours

An array keeps order by adjacency: element 5 sits right after element 4 in one block, so "next" just means "8 bytes further along" (Volume 1, chapter 8). A linked list throws that rule out. It scatters its elements anywhere the heap has room, and each element carries a note — a reference, the same 8-byte machine pointer names use in Volume 1 — saying where the next one is. The container remembers just one thing: a head reference to the first node. Follow the notes and the sequence unspools, even though no two nodes need be anywhere near each other in memory.

Read that carefully, because it's the whole idea and everything else falls out of it: logical order lives in the pointers, not in the addresses. Two nodes that are "adjacent" in your playlist can sit on opposite ends of RAM. That single decision buys the linked list its superpower — you can rearrange the sequence without moving any data — and lands it with its curse — you can't jump to the middle, because there's no address to compute. Let's see it in memory first.

If order is just arrows, rearranging the playlist should be almost free — no block to shift. Let's cash that in. But first: what does one node actually cost? →

The pointer tax

Nothing is free, and the linked list's bill comes due in bytes. In an array (a Python list), each element is stored as one bare 8-byte reference, packed shoulder-to-shoulder in a shared block; the object header is paid once for the whole list. A linked list can't do that. Every element is its own heap object, so every element pays the full Python object tax again. I measured a minimal node — a class with __slots__ so it carries no per-instance dictionary — on CPython 3.12:

import sys

class Node:
    __slots__ = ('value', 'next')      # no per-instance __dict__
    def __init__(self, value):
        self.value = value             # a reference to the song
        self.next  = None              # a reference to the next node (or None)

a = Node("Levels"); b = Node("Wake Me Up"); c = Node("Titanium")
a.next = b; b.next = c                  # a -> b -> c -> None
print(sys.getsizeof(a))                 # 48   bytes per node

48 bytes. The node holds only two useful references — 16 bytes of actual pointers — wrapped in 32 bytes of Python machinery: the reference count, the type pointer, and the garbage-collector bookkeeping every tracked object carries (Volume 1, chapter 4). So to store one element's worth of sequence, an array spends 8 bytes and a linked list spends 48 — a 6× memory tax, 40 extra bytes on every single node. That surcharge is what buys the flexible arrows; it is never free.

So a node is heavy but its arrows are flexible. Now spend that flexibility — insert a song mid-playlist and count what actually moves. →

Insertion is two pointers — given the node

Here's the linked list's marquee trick. To insert a new node X between two existing nodes A and B, you do exactly two things: point X.next at B, then point A.next at X. Two reference writes. Nothing else in the entire structure is read or moved — not the million nodes before A, not the million after B. Compare an array, where inserting at position i must shift every element from i onward one slot down to open a gap (Volume 1, chapter 8): that's O(n) copies. The linked list splice is O(1), and — this is the beautiful part — it's O(1) no matter where in the sequence you splice, because the cost doesn't depend on position at all. Order is arrows; you're just re-drawing two of them.

The widget makes it literal. Slide to pick where the new node goes and watch: the linked list always writes two pointers, while the array beside it must shift a different number of elements depending on where you cut.

Which raises the obvious question: if I only have an index — "give me the 500th song" — how does a linked list find it? →

…but finding it is a walk

Ask an array for element 500 and it does one multiplication: base + 500 × 8, jump straight there, done — O(1), the reward for living in one block (Volume 1, chapter 8). A linked list can offer nothing like it. There is no base address and no arithmetic, because the nodes are scattered and only the arrows know the order. To reach index k you must start at head and follow next k times, node by node. Reaching the 500th node means visiting the other 500 first. That's O(n), and it's baked into the layout — the price of trading adjacency for arrows.

I measured the gap on a million-node list. Walking to the middle took about 9 milliseconds; the array's lst[k] took about 0.1 microseconds — the O(n) walk versus the O(1) address computation. Most of those 9 ms is simply the half-million pointer hops the walk is forced to make; the array never hops at all. (Wall-clock numbers vary by machine; the O(n)-vs-O(1) shape does not.)

Drive the walk yourself. Slide the target index and watch the current pointer crawl from the head, one hop per node — the hop count is the index.

O(n) to walk, O(n) to scan — the same big-O as an array. So a full pass over a linked list and a full pass over an array should take the same time, right? Time them and prepare for a shock. →

Same O(n), wildly different speed

This is the section that separates people who know Big-O from people who know the machine. Summing a linked list and summing an array are both O(n): n additions, one per element. Big-O says they should scale identically — and they do. But wall-clock time is a different story, and the reason is the memory hierarchy from Volume 3, chapter 2. The CPU never fetches one value from RAM; it fetches a whole cache line — 64 bytes, eight references' worth — and keeps it in fast on-chip memory. An array is one contiguous block, so a single fetch pulls in the next eight elements for free. The scan streams: fetch a line, use eight, fetch the next. This is called spatial locality, and hardware is built to reward it.

A linked list has none of it. Its nodes are scattered wherever the allocator found room, so following next lands you at an unrelated address every time. Each hop is a fresh cache miss — the CPU stalls, waits a hundred-odd cycles for RAM, pulls a 64-byte line to use just 8 bytes of it, then hops somewhere else and does it again. This is pointer-chasing, and it's the linked list's hidden tax. I measured a two-million-element sum three ways:

array sum (contiguous)                     49 ms   (24 ns/elem)
linked list sum (nodes in alloc order)     55 ms   (28 ns/elem)
linked list sum (nodes shuffled in RAM)   407 ms  (204 ns/elem)

Same n, same additions, same O(n). Yet the scattered linked list ran roughly 8× slower than the array on that run — and about 6× on a second run (it's a cache effect, so the exact ratio drifts with the machine and memory state, but it's always a large constant, never 1×). Look closely at the middle row: a linked list whose nodes happen to be allocated in order is nearly as fast as the array, because consecutive nodes land near each other and the scan stays cache-friendly. It's the scattering that kills it, not the linking. Two structures, one complexity class, an order-of-magnitude difference in the only number the user feels.

If it's heavier and slower to scan, why does the linked idea sit at the heart of some of the most-used software on your machine? Because there's a job only it can do. →

Two-way streets, and where this really lives

Add one more pointer to each node — a prev reference back to the previous node — and you get a doubly linked list. Now you can walk either direction and, crucially, delete a node in place when you're standing on it: reach both neighbours through prev and next, wire them to each other, and the node is gone in O(1) — no need to have walked from the head to find the one before it. My measurement puts a doubly linked node at 56 bytes versus the singly node's 48: one extra 8-byte pointer, the fee for two-way travel. Link the tail's next back to the head and it becomes circular — no beginning, no end, useful for round-robins.

You almost never type class Node in Python — the built-in list and deque (chapter 5) cover the common needs faster, thanks to their block layout. The linked list's real importance is that the idea is everywhere underneath, doing the one job it owns: rearranging a sequence, or splicing and unsplicing elements, in O(1) when you hold a handle to the spot — with no reallocation and with node identities that stay valid while the structure changes around them.

One more thing only a linked structure gives cheaply: reversal. Flip every node's arrow and the sequence runs backward — no data copied, just pointers turned around. Watch it move only pointers:

def reverse(head):
    prev = None
    cur  = head
    while cur is not None:
        nxt = cur.next     # remember where we were going
        cur.next = prev    # flip this node's arrow backward
        prev = cur         # advance the two walkers
        cur = nxt
    return prev            # prev is the new head

# a -> b -> c  becomes  c -> b -> a
# before: ['Levels', 'Wake Me Up', 'Titanium']
# after : ['Titanium', 'Wake Me Up', 'Levels']

Line by line: prev trails behind and cur leads. Each turn of the loop stashes the forward link in nxt (or we'd lose the rest of the list the instant we overwrite it), flips cur.next to point backward at prev, then shuffles both walkers one step forward. When cur runs off the end, prev is left holding the last node — the new head. I ran it on Levels → Wake Me Up → Titanium and got Titanium → Wake Me Up → Levels, and not a single value object moved in memory — only the arrows turned. That is the linked list's whole personality in eight lines: cheap to re-wire, and it never touches the data.

Chapter 3 does exactly that. Take a list, forbid every operation except push and pop at one end, and you get the stack — the simplest container there is, and the one quietly running your program's function calls right now. →

03The stack — last in, first out

A stack is the simplest deal you can strike with memory: you agree to add and remove items at one end only — the top — so the last thing you put in is the first thing you take out. That single rule, Last In, First Out (LIFO), makes all three moves — push, pop, peek — cost O(1), and it turns out to be the exact shape of function calls, undo, the browser Back button, and matching brackets. By the end of this chapter you'll see the stack that runs underneath every program you've ever written, write a bracket-matcher from scratch, and recognise a "LIFO" access pattern on sight.

One end, and the world's simplest rule

Picture a spring-loaded stack of cafeteria trays. You can only do two things: drop a tray on top, or lift the top tray off. You can't slide one out of the middle, and you can't reach the bottom one until every tray above it is gone. Whatever went on last comes off first. That's the whole idea, and its name is LIFO — Last In, First Out. The tray you can currently touch is called the top; adding is push; removing the top is pop; looking at the top without removing it is peek.

Now the memory picture, because a stack is not some exotic new object — from Volume 1 you already own it. A Python list is a contiguous block of 8-byte references with some spare slots on the end (Vol 1, ch 6). A stack is just that list with a promise: I will only ever touch the far end. Push is append; pop is .pop(); peek is a[-1]. There is no separate "top pointer" stored anywhere — CPython keeps the list's length in its header, so the top is simply the last index, len − 1. Look at the block in RAM before we touch a line of code.

What does one item cost? I measured it on CPython 3.12: an empty list is 56 bytes (a bare header, no data block yet), and a list of a million integers is 8,000,056 bytes — almost exactly 8 bytes per element, because the block stores only the reference; the integer object it points at lives elsewhere on the heap. A stack is therefore about as light as a container gets: 8 bytes of "plumbing" per item, plus a little overallocated slack on the end.

If only the top ever moves, how expensive can any operation possibly be? Let's derive the cost from the layout instead of taking it on faith. →

Why push, pop, and peek are all O(1)

Reason straight from the block. To push, CPython looks at the length, finds the next free slot right after the last item, writes one reference into it, and increments the length. It does not look at slot 0, or slot 3, or the million items underneath — it touches exactly one cell. Work independent of how big the stack is means O(1). To pop, it reads the top cell, hands the reference back, and decrements the length — again one cell, O(1). To peek, it reads a[-1] and returns it without changing anything — O(1). Three operations, none of which ever walks the block.

There's one honest wrinkle. Every so often a push finds no free slot left, so CPython allocates a bigger block and copies the references over. That single push is O(n) — but it happens rarely, and the growth is geometric, so if you average the cost over many pushes it comes out to a constant. This is amortized O(1) (Vol 3, ch 3), the same accounting that makes list.append cheap. I watched the block grow in jumps: pushing onto a fresh list, getsizeof stepped 56 → 88 → 120 → 184 → 248 → 312 → 376…, reallocating at sizes 1, 5, 9, 17, 25, 33 — a handful of copies across dozens of pushes, each copy buying room for the next batch.

stack = []
stack.append('do')      # push   O(1)  -> ['do']
stack.append('re')      # push   O(1)  -> ['do', 're']
stack.append('mi')      # push   O(1)  -> ['do', 're', 'mi']
top = stack[-1]         # peek   O(1)  -> 'mi'   (stack unchanged)
gone = stack.pop()      # pop    O(1)  -> 'mi'   (stack is ['do', 're'])

Line by line: three appends push onto the far end, each dropping a reference into the next slot. stack[-1] peeks — it reads the top without disturbing it, so the list still has three items. stack.pop() removes and returns the top, 'mi' — the last thing pushed is the first thing out, LIFO made literal. Timed at a million operations each, a push averaged about 26 nanoseconds and a pop about 24 nanoseconds on my machine (wall-clock varies by hardware; the point is that neither grows with the stack's size).

So a stack is a list you agreed to touch at one end. But hold on — Python never made you declare a "Stack". Where is the stack, exactly? →

A stack is not a type — it's a discipline

Here is the reframe that trips almost everyone up. In many languages a stack is a class you import and instantiate. In Python, a stack is not a data type at all — it's a rule you impose on a list. The moment you promise yourself "I will only ever append and pop(), never index into the middle, never pop(0)," that ordinary list is a stack. The structure isn't in the object; it's in the discipline. Nothing in the runtime enforces it — the LIFO-ness is a contract you keep with yourself, and its whole payoff is that every operation stays O(1) and the code reads as "a stack."

You do have choices for the backing, and they matter for reasons Volume 3 made physical. A list keeps its references contiguous, so a run of pushes and pops streams through the same cache lines — the CPU prefetcher loves it. The textbook alternative, a linked stack — one small node per item, each holding a value and a next pointer, push = make a node and point it at the old top, pop = follow next — is correct and also O(1), but every node is a separate heap allocation scattered across RAM, so pushing and popping is allocation plus pointer-chasing, and each hop risks a cache miss (Vol 3, ch 2). I measured the gap: pushing and popping 2,000,000 items was about 0.20 s on a list versus 0.88 s on a node-per-item stack — same Big-O, roughly 4× slower on the metal. And the node is heavier too: a minimal two-field node with __slots__ is 48 bytes each (ballooning to ~344 bytes if it carries an ordinary __dict__), against the list's flat 8 bytes per item.

You've been imposing this discipline by hand. Now meet the stack you never declared — the one the interpreter has been running under your feet this whole time. →

The stack you're already standing on

Every time one function calls another, the machine has to remember where to come back to and what the caller's local variables were. It stores that in a frame — a little record holding a call's local names and its return address (Vol 1, ch 9). And it keeps those frames in exactly one arrangement: a stack. When a calls b calls c, three frames are pushed; when c returns, its frame is popped and control resumes in b. It must be LIFO, because the function that started most recently is the one that has to finish first before the one that called it can continue. This is the call stack, and it is the most important stack you will ever use — you use it in every program without ever typing push.

You can see it directly. CPython links each frame to its caller through f_back, so walking that chain from the running function outward is reading the stack top-to-bottom.

import sys

def show_frames():
    f = sys._getframe()             # the frame running right now (top of the stack)
    names = []
    while f:                        # walk f_back all the way down
        names.append(f.f_code.co_name)
        f = f.f_back                # step to the caller's frame
    print(" -> ".join(names))

def a(): b()
def b(): c()
def c(): show_frames()
a()                                 # show_frames -> c -> b -> a -> <module>

Reading it: sys._getframe() hands back the frame on top — the one for show_frames itself. The while loop follows f_back link by link, and each link is the frame that called this one, so we climb down the stack recording names. The real output was show_frames -> c -> b -> a -> <module> — the exact push order, read back in reverse, which is what "popping" would give you.

This is also why recursion costs memory and why it can crash. Each recursive call pushes another frame; the frames only start popping when a base case lets calls return. Recur without a base case and you push frames forever — until the stack runs out of room. Python guards against blowing the real, finite C stack underneath by capping its own depth: sys.getrecursionlimit() is 1000 by default, and an unbounded recursion raised RecursionError at a depth of about 999 when I ran it. That crash has a famous name.

The call stack matches nested function calls for a living — open a, open b, close b, close a. That's the same shape as nested brackets. Let's make a stack check them by hand. →

Matching brackets — a stack's party trick

Is ([{}]) balanced? Is ([)]? A human eyes it; a stack proves it in one pass. The rule that makes brackets legal is that the one you opened most recently must be the one you close first — which is LIFO exactly. So scan left to right: every time you meet an opener, push it; every time you meet a closer, the thing it must match is whatever is on top of the stack, so pop and check they're a pair. If they don't match, or the stack is empty when you need something to pop, it's broken. If you reach the end with an empty stack, every opener found its partner — balanced.

def balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':                       # an opener → push it
            stack.append(ch)
        elif ch in ')]}':                      # a closer → the top must be its partner
            if not stack or stack.pop() != pairs[ch]:
                return False                   # nothing to match, or a mismatch
    return not stack                           # balanced only if nothing is left open

for t in ['()', '([])', '([)]', '(((', '{[()]}', '](']:
    print(repr(t), '->', balanced(t))

Walk it: pairs maps each closer to the opener it needs. For an opener we append — push. For a closer we check two failure modes at once: not stack (a closer with nothing open) and stack.pop() != pairs[ch] (the most recent opener is the wrong kind). Reach the end and not stack asks "is everything closed?" I ran it, and it returns exactly what your eye does: '()' -> True, '([])' -> True, '([)]' -> False (the ) tries to close a [), '(((' -> False (three left open), '{[()]}' -> True, and ']( ' -> False. Twelve lines, and it's the beating heart of every compiler, JSON parser, and the rainbow-bracket highlighter in your editor.

Push to remember, pop to go back. That "go back" is not a toy — it's the mechanism behind undo, the browser Back button, and depth-first search. →

The Back button of everything

Once you can see LIFO, you start finding it everywhere, because a huge class of features is really one wish: "take me back to the thing I was just at." That is a pop. Undo is a stack of past states — every action you take pushes a way to reverse it; Ctrl-Z pops the most recent and applies it. Add a second stack for the ones you undo and you get redo: undo pops from one stack and pushes onto the other. Your browser's Back button is a stack of pages — each link you follow pushes the current page; Back pops it and returns you. Depth-first search (Vol 3, ch 13) explores a maze by pushing each junction and popping back to the last one when it hits a dead end — recursion does this on the call stack, or you carry an explicit stack to do it yourself. Even a calculator evaluating 3 + 4 × 2 leans on a stack to hold operands. You press Back without a thought; you were popping a stack.

That's the stack's mirror image: the queue, First In, First Out — the structure of every line you've ever stood in, every print job, and the OS scheduler deciding who runs next. It's cheap at both ends for a reason we'll build from memory up. →

04The queue — first in, first out

A stack (chapter 03) hands you back the last thing you put in. A queue does the opposite: it hands you back the first. Add at the back, remove from the front — like a line at a shop, the order preserved, nobody jumping ahead. That one rule, First In, First Out, is how your operating system shares the CPU, how a breadth-first search explores a maze level by level, and how every keystroke you type waits its turn. By the end of this chapter you will build a queue that adds and removes in true O(1), you will know exactly why the obvious Python version secretly runs in O(n), and you will see — in memory — the trick that fixes it.

One rule, and it means order

A queue is a linear collection with two doors, one at each end, and a law about which door does what. The back door is enqueue: a new item is added there and only there. The front door is dequeue: an item is removed there and only there. Because you always remove the oldest surviving item — the one that has waited longest — the queue preserves arrival order perfectly. First in, first out. A stack is LIFO; a queue is FIFO; both are just a rule about which end you touch.

That rule is not a toy. FIFO is fairness: the request that arrived first gets served first, so no task starves while newer ones cut the line. It is also buffering: when a fast producer feeds a slow consumer — your keyboard feeding a busy program, a network card feeding your app — a queue holds the backlog in the exact order it arrived, and the consumer drains it at its own pace without losing or reordering a thing. Keep those two words, fairness and buffering, in mind; every real use at the end of this chapter is one of them.

Now the part this volume cares about most: what does a queue actually look like in RAM? The honest first picture is a row of slots — a contiguous block, exactly the array of 8-byte references from Volume 1 — plus two markers. One marker, front, points at the oldest live item (the next to leave). The other, back, points at the next free slot (where the next arrival will land). Enqueue writes at back and nudges back forward. Dequeue reads at front and nudges front forward. Nothing else moves.

If both operations touch a single slot and bump a single index, both should be O(1). So why does the most natural Python queue crawl to a halt on big inputs? →

Why a plain list makes a terrible queue

Reach for a queue in Python and the obvious move is a list: append to add at the back, pop(0) to remove from the front. It looks right. It even works — for a while. Then it dies, and the reason is buried in how a list lives in memory. Recall from Volume 1 chapter 6: a Python list is a contiguous array of references with a fixed front pinned at index 0. There is no movable front marker. So when you delete index 0, the list cannot just "advance a pointer" — it must keep index 0 meaning index 0. Every one of the remaining n−1 references has to slide down one slot to close the hole.

"Slides down one slot" is a bulk memory copy — internally a single memmove of n−1 pointers. For six items it is invisible. For a million-item queue, every single dequeue copies almost eight megabytes of references before it can return one value. That is O(n) per removal, which makes draining the whole queue O(n²). We do not have to trust the reasoning — we can time it. Here each trial dequeues one item from a size-n queue and re-enqueues it, so the size stays fixed and we isolate the cost of one front removal:

import timeit
from collections import deque

for n in (10_000, 100_000, 1_000_000):
    tl = timeit.timeit("l.append(l.pop(0))",       # dequeue front, re-enqueue
                       setup=f"l=list(range({n}))", number=5000) / 5000
    td = timeit.timeit("d.append(d.popleft())",    # same, but a deque
                       setup=f"from collections import deque; d=deque(range({n}))",
                       number=5000) / 5000
    print(f"n={n:>9}   list {tl*1e9:8.0f} ns   deque {td*1e9:4.0f} ns")

# n=    10000   list    14790 ns   deque   27 ns
# n=   100000   list   151925 ns   deque   28 ns
# n=  1000000   list   526401 ns   deque   24 ns

Read the list column top to bottom. Ten thousand items: ~15 µs per dequeue. Ten times the items: ~152 µs — ten times the cost, a dead-straight line, exactly what O(n) predicts. The deque column beside it never twitches: ~25 nanoseconds whether it holds ten thousand items or a million. (Numbers are from this machine and will vary; the shapes — one climbing, one flat — are the law.) Push it further and it stops being a benchmark and becomes pain: draining a 100,000-item queue front-to-back took the list 7.5 seconds; the deque did the same job in 5.4 milliseconds — about 1,400× faster, and the gap widens with every extra item.

The list's sin was a front that couldn't move. What if we let it move — and let both ends wander freely around a fixed block of slots? →

The ring buffer — two indices chasing around a fixed array

Here is the human insight that fixes everything, and it is beautifully cheap. The whole problem was that dequeuing tried to keep the front pinned at index 0. So don't pin it. Keep the same contiguous array, but let front and back be movable integer indices. Dequeue? Just advance front by one — the old slot is now dead space, and we don't care. Enqueue? Write at back, advance back by one. No element ever moves. Both operations are a write and an add: genuine O(1).

But if both indices only ever crawl forward, they march off the end of a fixed array. The fix is the trick that names the structure: wrap around. When an index reaches the last slot, its next step goes back to slot 0 — computed with a single modulo, (i + 1) % capacity. The array is no longer a line; it is a ring. The live queue is the arc of slots from front up to back, and that arc drifts around the circle as items come and go, forever reusing the slots that dequeues freed behind it. This is a ring buffer (also called a circular buffer), and it is one of the most-used structures in all of systems programming.

A ring buffer is perfect when you know the capacity up front. But Python's queue of choice grows without bound and still gives O(1) at both ends. How? →

collections.deque — the real fix, and its memory

You will rarely hand-roll a ring buffer in Python. You will reach for collections.deque (pronounced "deck," from double-ended queue), the standard library's answer to exactly this problem. It gives you O(1) append and pop at the back and O(1) appendleft and popleft at the front — no shifting, ever. For a FIFO queue you use just two of its four doors: append to enqueue, popleft to dequeue.

from collections import deque

q = deque()          # an empty FIFO
q.append("A")        # enqueue at the back
q.append("B")
q.append("C")
first = q.popleft()  # dequeue from the front  ->  "A"  (first in, first out)
print(first, list(q))
# A ['B', 'C']

Line by line: deque() builds an empty double-ended queue; three appends enqueue A, B, C at the back in order; popleft() removes from the front and returns "A" — the oldest item, exactly FIFO; what remains is B then C. Same five lines a list would use, minus the O(n) landmine.

What does a deque look like in memory, and why does it stay O(1) at both ends? Not one contiguous array — that would re-create the list's problem at one end or the other. Instead a deque is a doubly linked list of fixed-size blocks. Each block is a small contiguous array (64 reference slots in CPython), and the blocks are chained with next/prev pointers. The deque keeps direct pointers to the first and last block, plus the write position inside each. Adding at either end writes into the end block; when an end block fills, a new block is linked on. No element is ever copied to make room — growth just links another block.

That design has a memory price worth naming out loud. An empty list weighs 56 bytes; an empty deque weighs 760 bytes, because it pre-allocates its first block of slots up front. So for tiny collections a deque is heavier. But per element the two converge on the same figure — about 8 bytes each — because both, at bottom, store 8-byte references (Vol 1), not the objects themselves:

import sys
from collections import deque
print(sys.getsizeof([]),        sys.getsizeof(deque()))       # empty:  56   760
for n in (1000, 10000):
    print(n, sys.getsizeof(list(range(n))), sys.getsizeof(deque(range(n))))
# 1000    8056    8680
# 10000  80056   83128

At 10,000 items the list holds 80,056 bytes and the deque 83,128 — the deque's small surplus is the per-block bookkeeping (the next/prev pointers and partly-filled end blocks). Both are ~8 bytes times n plus a fixed header: a container of references, precisely the Volume 1 model. The deque buys you O(1) at both ends for a modest, near-constant space premium — a very good trade.

You now have a real O(1) FIFO. The last question is the one that makes it worth knowing: where does the machine — and the wider world — actually run on queues? →

How the machine feels it, and why search runs on queues

Big-O says the ring buffer and a naive pointer-per-node linked queue are both O(1) per operation. The metal disagrees about which is fast. A ring buffer is one contiguous array, so consecutive slots sit in consecutive cache lines; walking the queue streams through the CPU cache (Vol 3 ch 2) at full speed. A linked queue with one heap node per item scatters those nodes anywhere in memory, so every dequeue chases a pointer to an address the cache never predicted — a stall of hundreds of cycles, again and again. The deque splits the difference on purpose: 64 items per block means you get long contiguous runs (cache-friendly) with only an occasional pointer hop between blocks. That block size is not arbitrary; it is tuned so the pointer-chase is rare relative to the streaming. This is the whole reason a heap lives in a flat array too — a lesson chapter 11 makes central.

That is the deepest "wow" in the chapter: BFS and a queue are the same idea. The queue holds the frontier — nodes seen but not yet explored. Dequeue the oldest, enqueue its undiscovered neighbours at the back, repeat. Because a queue is FIFO, everything one step from the start is processed before anything two steps away, so BFS sweeps outward in perfect concentric rings and lands on the shortest path first. Change one line — dequeue from a stack instead — and the identical loop becomes depth-first search. The container chooses the algorithm. That is the 1% move in miniature: the data structure is the strategy.

When to reach for a queue

Good at data structures is mostly one skill: matching the access pattern to the container on sight. The queue's tell is unmistakable — whenever items must be handled in arrival order, and you always take the oldest first. Fairness (serve who came first) or buffering (a fast source, a slow drain, order preserved between them). The instant you catch yourself writing list.pop(0) in a loop, stop: you have found a queue wearing a list's clothes, and it is quietly O(n²). Type from collections import deque instead.

You have the FIFO half of the story. But notice the widget above did something a pure queue never needs: it added and removed at both ends. That double-ended power — appendleft as easily as append — is not a queue at all; it is the deque in full, and its 64-slot block design is a small marvel of engineering worth a chapter of its own.

Next (chapter 05): the deque — one structure that is a stack and a queue at once. We open up those linked blocks of 64, see why that exact number, and watch appendleft and popleft stay O(1) at the end nobody else can touch. →

05The deque — fast at both ends

A deque — say "deck", short for double-ended queue — is a stack and a queue fused into one container: you can push and pop at the front and the back, and all four of those moves cost O(1). This chapter shows you the trick that buys both-ends speed — a chain of small memory blocks — and the single caveat that tells you when to reach for it. By the end you'll spot an "ends-only" access pattern on sight, use a bounded deque as a self-trimming history, and collapse a sliding-window problem from O(n·k) down to O(n).

Both ends, for free

From Volume 1 you know a list is a contiguous block of 8-byte references. That makes it cheap at the back — append is amortized O(1), it just drops a reference into a spare slot — but the front is a trap. pop(0) and insert(0, x) have to shift every remaining reference one slot over to keep the block gap-free (Volume 1, chapters 6 and 8). I measured it: draining 50,000 items one at a time with list.pop(0) took about 4.7 seconds; the same drain with a deque took about 4 milliseconds — roughly a thousandfold gap, and it widens with n because the list is quietly O(n²).

A deque is engineered so both ends are as cheap as a list's back. The whole secret is the layout, so let's look at the memory before we look at the code.

Why 64? Why blocks at all — why not one node per item like a textbook linked list, or one big array like a list? →

Link blocks, not items

Here's the design insight — and it's the kind of "aha" worth stealing. A textbook doubly-linked list gives you O(1) ends, but it pays a whole node object per item. I measured a minimal Python node (a class with __slots__ for value/next/prev): 56 bytes each — and ~344 bytes if it carries an ordinary __dict__ — and every node is a separate heap allocation scattered across RAM. Walking such a list is pure pointer-chasing, and each hop is a fresh cache miss (Volume 3, chapter 2). A plain array is the opposite: 64 references sit shoulder to shoulder and stream through cache, but the front is O(n) and a growth means reallocating the whole block.

The deque's author refused to choose. Link the blocks, not the items. Inside one block, 64 references are contiguous — one allocation feeds 64 items, and they scan cache-friendly. Between blocks, prev/next pointers give the front the exact same cheap, local growth the back already had. You get the linked list's flexible ends and keep most of the array's locality.

The numbers back it up (all RAN on CPython 3.12). A block is 64 × 8 = 512 bytes of cells plus two 8-byte links — 528 bytes. An empty deque already weighs 760 bytes: a ~232-byte header plus one pre-allocated block, because a deque is never truly without a block to write into. Append into it and watch sys.getsizeof climb in flat +528-byte steps — one per new block — while the list next to it grows in fine-grained overallocation steps.

import sys
from collections import deque

print(sys.getsizeof(deque()))       # 760   (header + one 528 B block)

d = deque()
prev = sys.getsizeof(d)
for i in range(1, 260):
    d.append(i)
    s = sys.getsizeof(d)
    if s != prev:                   # print only when a new block is hooked on
        print(i, prev, "->", s)     # 33 760 -> 1288 ; 97 1288 -> 1816 ; ...
        prev = s

Line by line: the first print confirms the 760-byte floor. Then we append 259 items, and print only on the steps — the moments getsizeof changes. The real output was jumps at n = 33, 97, 161, 225, each adding exactly 528 bytes — one block. Why the first jump at 33, not 64? Because a fresh deque drops its first item in the middle of the block, so an append-only run fills the right half (~32 cells) before it needs a second block. Steady-state cost: about 8.25 bytes per element versus a list's flat 8.00 — the block links cost roughly a quarter-byte per item, plus up to one block of slack riding at each end.

So an append is cheap. But how cheap, and what does it physically do to those cells? →

What one append actually does

Let's derive the O(1) instead of asserting it. To append(x), CPython looks at the rightmost block and rightindex — the cursor sitting on the last used cell. If there's a free cell to its right, it writes the reference to x into that cell and bumps rightindex by one. That's it: one pointer write, one integer increment. Independent of how many million items the deque holds — so, O(1). Only when rightindex is already on the block's last cell (every 64th append) does it grab a block from the freelist, link it on the right, and reset the cursor to the new block's start — still constant work. appendleft is the mirror image on the left; pop and popleft read an end cell, step the cursor inward, and unhook a block once one empties. Nothing between the two ends is ever read or moved.

from collections import deque

up_next = deque(["Levels", "One More Time", "Strobe"])
up_next.append("Titanium")      # add at the back    O(1)
up_next.appendleft("Encore")    # cut in at the front O(1)
first = up_next.popleft()       # serve the front    O(1)  -> "Encore"
last  = up_next.pop()           # drop the back       O(1)  -> "Titanium"

Four operations, four constant-time moves — no shifting, no reallocation, no walking. This is the widget below made literal. Drive it and watch the two cursors crawl outward as you push and inward as you pop, and catch the moment a full block hooks a fresh one on.

Both ends are O(1). So is a deque just a better list you should use everywhere? Try to grab the middle element and the answer arrives fast. →

The catch: the middle is O(n)

Ask a list for a[i] and it computes one address — base + i × 8 — and jumps there. That's the payoff of a contiguous block: O(1) random access (Volume 1, chapter 8). A deque can't do that, because its cells are scattered across linked blocks with no single base. To reach dq[i] it starts at the nearer end and walks the chain block by block — 64 items per hop — until it lands in the right block, then indexes inside. That walk is proportional to how deep i sits: O(n).

I measured it on a million-item deque: dq[n//2] took about 47 microseconds, while list[n//2] took about 0.17 microseconds — roughly 280× slower, and the gap grows with n. This is not a small constant; it is a different complexity class. The deque is a specialist for the ends, and paying for the middle is how you misuse it.

"Ends-only" sounds like a limitation. It's the opposite — a whole family of features you use daily are pure ends games. Start with the one running in your browser right now. →

A history that forgets — maxlen

Build a deque with maxlen=N and it becomes a fixed-size window on a stream: once it holds N items, every append silently drops one off the other end to make room. A rolling "last N" in one line — newest kept, oldest evicted for free, no manual trimming, and crucially no O(n) pop(0).

from collections import deque

recent = deque(maxlen=3)                 # keep only the 3 most recent
for page in ["A", "B", "C", "D", "E"]:
    recent.append(page)
    print(list(recent))
# ['A'] -> ['A','B'] -> ['A','B','C'] -> ['B','C','D'] -> ['C','D','E']

I ran it: once the deque is full at three, appending "D" shoulders out "A", and "E" shoulders out "B" — you're always looking at the three newest, and the eviction is an O(1) drop at the far end, not a whole-array shuffle. That single line is the skeleton of a surprising amount of software.

maxlen uses a deque as a rolling buffer. Now use both ends at once, as deliberate scratch space, and an O(n·k) problem collapses to O(n). →

The killer app: sliding-window maximum in O(n)

Volume 3, chapter 7 slid a window across an array and kept its sum current in O(1) by adding the entering value and subtracting the leaving one. Maximum is nastier: when the current maximum slides out of the window, you can't cheaply recover the next one — re-scanning the whole window is O(k), for O(n·k) overall. The fix is a monotonic deque, and it's the deque's signature move.

Keep a deque of indices whose values are strictly decreasing from front to back. For each new element, three steps: (1) pop indices off the back whose values are ≤ the newcomer — while this bigger, newer value stands, they can never again be a window maximum, so discard them; (2) append the new index at the back; (3) if the front index has slid out of the window, popleft it. After those, the front index always holds the current window's maximum. Every index is appended once and removed once across the whole run, so the total work is O(n) — amortized, exactly the reasoning of Volume 3 chapter 3.

from collections import deque

def max_sliding_window(a, k):
    dq = deque()                       # holds INDICES, values decreasing front->back
    out = []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x:    # (1) evict smaller tails: they can't be max
            dq.pop()
        dq.append(i)                   # (2) newcomer joins the back
        if dq[0] <= i - k:             # (3) front slid out of the window?
            dq.popleft()
        if i >= k - 1:
            out.append(a[dq[0]])       # front index = this window's maximum
    return out

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))   # [3, 3, 5, 5, 6, 7]

Walk it: dq never holds values, only indices — that's how it also knows when a candidate expires. The while loop (1) clears every tail index whose value the newcomer x beats or ties, keeping the deque decreasing. Step (2) appends the newcomer at the back. Step (3) checks the front: if its index is ≤ i - k it has fallen off the window's left edge, so popleft. From i = k-1 on, a[dq[0]] — the value at the front index — is the window maximum, emitted in O(1). I ran it against a brute-force max(a[i:i+k]): identical output [3, 3, 5, 5, 6, 7]. On a bigger case (n = 200,000, k = 1000) the deque version took about 80 ms versus the brute force's ~4.8 s — roughly 59× faster here (the gap grows with k; wall-clock varies by machine, the O(n) vs O(n·k) shape does not).

That is the deque's reason to exist, generalized: it is O(1) scratch space with two working ends. Palindrome checks (pop a character from each end and compare), balanced-parenthesis and BFS frontiers (Volume 3, chapter 13), rotate(k) for round-robin scheduling — all lean on cheap access at both ends. Run deque([1,2,3,4,5]).rotate(2) and you get [4,5,1,2,3] in O(k), no reshuffle.

Every linear structure so far — array, stack, queue, deque — reaches its data by walking: to a position, or to an end. The next family throws walking out. Hand it a key — a title, a name, a label — and it computes the address and lands on the value in a single hop, no matter how many million entries sit inside. How can a key become an address? →

06The hash map — a value by its key, instantly

A hash map — Python spells it dict — is the structure that answers the question "what's the value for this key?" without looking at any other entry. Not by walking, not by binary search — by computing the address from the key itself and jumping straight there. This chapter shows you the one trick that makes that possible, why the table is deliberately kept two-thirds empty, why it is the heaviest structure per item you'll meet, and why a key has to be frozen. By the end you'll read d[key] and see the hash, the bucket, and the single jump — and you'll know on sight when a problem is really a hash-map problem.

The address is hidden inside the key

Every structure so far reaches its data by position. A list lands on a[i] with one multiply-and-add because its cells are contiguous (Volume 1, chapter 8). But that only works when you already know the index. What if your key is a song title, a username, an IP address — a label, not a number? Searching a list for it is an O(n) walk. Keeping it sorted and binary-searching is O(log n) (Volume 3). The hash map does something that sounds impossible: it reaches the value in O(1) average — one jump, no matter how many million entries sit inside.

The trick is a function called hash. Feed it any hashable object and it returns a fixed-size integer — a scramble of the key's contents. That integer, taken mod the table size, is an index into a plain array of slots called buckets. So the key computes its own address: bucket = hash(key) % N. Store means "scramble to a bucket, drop the value there"; lookup means "scramble to the same bucket, read the value." Both touch exactly one slot. That's the whole idea — everything else in this chapter is defending it.

Here is the derivation the "O(1)" hangs on. Computing hash(key) depends on the key's own size, not on how many entries the table holds. The % N is one integer op. The array is contiguous, so "jump to bucket b" is one base + b × slot address computation — the exact primitive from Volume 1's list. Add them up: the work to find any entry is independent of n. That is the definition of O(1). The list had to walk n slots; the sorted array bisected to log n; the hash map skips the search entirely because the key already knows where it lives.

>>> hash(42)          # small ints hash to themselves
42
>>> hash(42) % 8      # ... so the bucket is just the low bits
2
>>> d = {"Levels": 84, "Strobe": 631}
>>> d["Levels"]       # hash("Levels") % N -> one jump -> 84
84

I ran it: hash(42) is 42 (small integers hash to themselves), so hash(42) % 8 is 2 — bucket 2, computed straight from the key. d["Levels"] never looks at the "Strobe" entry at all; it hashes "Levels", mods, jumps, reads. Two entries or two billion, the lookup does the same amount of work.

One jump — as long as no two keys ever want the same bucket. But with 8 buckets and a 9th key, two must collide. What happens then? →

When two keys want one bucket

Collisions are not a bug; they are arithmetic. You are squeezing a giant space of possible keys through % N into N slots, so the moment you have more than N keys, two of them share a bucket by the pigeonhole principle — and long before that, birthday-style coincidences make near-collisions common. A hash map is really two ideas welded together: a function that scatters keys evenly, and a plan for when the scatter lands two keys on the same slot.

There are two classic plans. Chaining: each bucket holds a little linked list, and colliding keys hang off the same bucket. Open addressing: keep everything in the one flat array, and if your bucket is taken, probe — try another slot by a fixed rule until you find a free one. CPython's dict uses open addressing, because a flat array streams through cache far better than chasing per-bucket linked-list nodes across the heap (Volume 3, chapter 2 — pointer-chasing stalls; contiguous memory flies). The figure below shows the simplest probe — walk to the next slot — but see the deeper cut: real CPython uses a perturbed sequence so collisions don't clump.

Build the intuition by driving it. In the widget, pick a key and watch it compute hash % 8 and light its home bucket; insert it and watch a collision probe forward to the next free slot.

Probing stays cheap only while there's plenty of free space to probe into. Let the table fill up and every insert turns into a long hunt. So the map watches how full it is — and acts. →

Two-thirds full, then grow

The number that governs a hash map's health is the load factor: entries divided by buckets. Empty is 0; half full is 0.5. As it climbs toward 1.0, free slots vanish, probe chains lengthen, and the beautiful O(1) rots into an O(n) scan. So the map never lets it get close. CPython resizes the moment the table would cross two-thirds full — it grows the bucket array (doubling it) and rehashes every existing key into the bigger table, because each key's bucket is hash % N and N just changed.

You can watch it happen with sys.getsizeof. I inserted integers one at a time and printed only when the table's byte size jumped:

import sys
d = {}
prev = sys.getsizeof(d)
for i in range(1, 130):
    d[i] = i
    s = sys.getsizeof(d)
    if s != prev:                 # only print the resize moments
        print(i, prev, "->", s)
        prev = s
# 1   64 -> 224     (first key: an 8-bucket table appears)
# 6   224 -> 352    (6th key crosses 2/3 of 8  -> grow to 16)
# 11  352 -> 632    (11th crosses 2/3 of 16    -> grow to 32)
# 22  632 -> 1168   (22nd -> 64)   43  1168 -> 2264  (-> 128)   86  2264 -> 4688  (-> 256)

Read the resize points: 6, 11, 22, 43, 86. Those are exactly two-thirds of 8, 16, 32, 64, 128 — the table doubles every time it crosses the line. An empty dict is a bare 64-byte header with no bucket array at all; the first key conjures an 8-slot table (jumping to 224 bytes). From there each resize copies every key into a fresh, larger, mostly-empty array. That copy is O(n) — but it happens rarely and the table doubles, so the cost amortizes to O(1) per insert (the same amortized bookkeeping as the list's overallocation, Volume 3, chapter 3). You pay a big bill occasionally to keep every other insert instant.

Doubling to stay two-thirds empty is why lookups fly — and also why a hash map is the heaviest structure you'll carry. Let's weigh it. →

The heaviest structure per item

Every deal with memory has a price, and the hash map's is space. Look back at the layout: a big fraction of the buckets are deliberately empty — that's the load factor — and each occupied bucket doesn't just hold a value, it holds the hash and a reference to the key and a reference to the value. A list stores one 8-byte reference per element and nothing else. The dict stores far more, and keeps spare slots on top. Here's the same data both ways, measured:

import sys
keys = range(1000)
d = {k: k for k in keys}
L = list(keys)
print(sys.getsizeof(d))   # 36952  -> ~37 bytes per slot
print(sys.getsizeof(L))   # 8056   -> ~8  bytes per slot

big = {i: i for i in range(1_000_000)}
print(sys.getsizeof(big)) # 41943128  -> ~41.9 bytes per entry (~41.9 MB)

The list of 1000 is 8,056 bytes — about 8 per element, one reference apiece. The dict is 36,952 bytes — roughly 37 per slot, four to five times heavier, and that's just the table, before counting the key and value objects it points to. Scale up and it holds: a million-entry dict weighs ~41.9 MB of table alone (~41.9 bytes/entry). That is the space-for-speed bargain stated in bytes — you buy the single-jump lookup by keeping the array sparse and paying for two references and a cached hash per entry.

Sparse, reference-heavy, self-resizing — and it all rests on one quiet assumption about the key: that its hash never changes. Break that and the value vanishes. →

Why a key must be frozen

A hash map finds a key by recomputing hash(key) and going to that bucket. That only works if the key hashes to the same bucket every time. So the key must be hashable, which in practice means immutable — its contents, and therefore its hash, can never change while it's in the map. Strings, numbers, and tuples of immutables qualify. Lists and dicts do not, and Python refuses them outright:

>>> {[1, 2]: "x"}
TypeError: unhashable type: 'list'
>>> {(1, 2): "point"}[(1, 2)]      # a tuple is frozen -> fine
'point'

Why the hard ban? Picture what a mutable key would do. Suppose the map let you use a mutable object whose hash tracked its contents. You store value under it, landing in bucket 4. Then you mutate the key — now it hashes to bucket 7. Ask the map for it and lookup goes to bucket 7, finds nothing, and reports the key missing — while the value sits orphaned in bucket 4, unreachable. I built exactly that trap:

class Bad:
    def __init__(self, v): self.v = v
    def __hash__(self): return hash(self.v)   # hash tracks a mutable field
    def __eq__(self, o):  return self.v == o.v

k = Bad(1)
store = {k: "found me"}
print(store.get(k))        # 'found me'   -> hashes to its bucket, found
k.v = 999                  # mutate the key: its hash just changed
print(store.get(k))        # None         -> now hashes elsewhere, lost
print("found me" in store.values())   # True -> still physically in the table

The output was 'found me', then None, then True: the value never left the table — the key just stopped pointing at the right bucket. That is why immutability isn't a style rule here, it's a correctness requirement. Freezing the key is the price of computing its address. (This is the Volume 1, chapter 7 callback made concrete: hashability is exactly the contract a key signs.)

$ python -c "print(hash('secret'))"
-7922894392216367691
$ python -c "print(hash('secret'))"
7804674963121063573        # different seed each process -> different hash
$ python -c "print(hash(42))"
42                          # ints aren't randomized: hash(n) stays n

I ran hash('secret') in three fresh interpreters and got three unrelated numbers; hash(42) came back 42 every time. String hashes are salted per process (that's PYTHONHASHSEED at work); integer hashes aren't, because they're not the flooding target. Same key, same run — same bucket. Different run — possibly a different bucket. Which is also why you should never persist a Python hash to disk and expect it to match next launch.

Frozen keys, defended averages, a table two-thirds empty — add it up and you have the workhorse of modern computing. Where does it actually run? Almost everywhere, including inside Python itself. →

Where you meet this — everywhere, including inside Python

The access pattern the hash map owns is "reach a thing by its label" — and once you see it, you see it constantly. Every dict you write, obviously. But also: database indexes (a hash index turns a WHERE-clause value straight into a row location, no table scan); Redis and memcached, whole databases that are essentially one giant hash map living in RAM, serving billions of lookups a second; deduplication (drop everything into a set, collisions reveal the duplicates); a compiler's symbol table, mapping every variable name to its type and address as it parses your code; and memoization/caching — @lru_cache is a dict keyed by your function's arguments.

A set is the same machinery with the values thrown away: a hash table that stores only keys, answering "is x in here?" in O(1). I measured a membership test on a million-element set at about 38 nanoseconds — versus the list's worst-case scan of the same size, which I clocked at roughly 6.4 milliseconds, over a hundred-thousand times slower. When your question is "have I seen this before?" or "is this in the allowed set?", that gap is the whole reason sets exist.

Because a hash map scatters keys to random buckets, it destroys one thing utterly: order. Ask it for "the smallest key," or "every key between 10 and 20," and it has no answer but to scan everything. The structures ahead keep order on purpose. But first, the next chapter leaves the world of one-dimensional rows entirely — it arranges data in a grid, rows and columns, and asks a question that decides how fast every image filter and neural network runs: when you store a 2-D table in 1-D memory, which way do you lay it down? →

07The matrix — a grid in a straight line of memory

A matrix is a grid: rows and columns, like a spreadsheet, a chessboard, or the pixels of a photo. But the machine underneath has no grid — Volume 1 drew RAM as a single line of numbered boxes, one address after another. So a matrix is a quiet magic trick: a two-dimensional idea folded flat onto one-dimensional memory. This chapter shows you the fold. After it you'll compute any cell's address in your head, feel in your bones why summing a grid row-by-row beats column-by-column on identical work, and know exactly when a real contiguous block crushes Python's list-of-lists.

A grid is a story we tell; memory is a line

Draw a 3×4 matrix and your eye sees a rectangle — three rows stacked, four columns side by side. The CPU sees no such thing. Its memory is what Volume 1 gave us: a single sequence of addressed slots, box 0, box 1, box 2, marching off in one direction only. There is no "up," no "down," no second axis. To store a grid, the machine must flatten it — unroll the rectangle into one long strip.

There are two honest ways to unroll it, and the near-universal choice is row-major order: lay down all of row 0 end to end, then immediately after it all of row 1, then row 2 — rows concatenated into one contiguous run. (The other way, column-major, lays down whole columns first; Fortran, MATLAB, and Julia use it, and it will matter later.) Row-major is how C, and therefore NumPy, and therefore almost every image and tensor you touch, arranges a grid. The rectangle in your head is a line in the RAM.

If the whole grid is one flat line, then cell (i, j) lands at some exact position in it. Which one? There's a single formula — and it's the reason indexing a matrix is instant →

The one formula: base + (i·ncols + j)·slot

Look at the strip again and reason it out. To reach the start of row i, you must step past every row before it. Each of those rows is exactly ncols slots wide, and there are i of them — so i × ncols slots lie behind you. Now walk j slots into row i to reach the column you want. The cell's position in the flat line — its linear index — is therefore:

index = i × ncols + j  →  address = base + (i × ncols + j) × itemsize

where base is the RAM address of cell (0,0) and itemsize is the bytes per slot (8 for a 64-bit number). That's one multiply, one add — a fixed amount of arithmetic, no matter how vast the grid. This is why reading matrix[i][j] is O(1): the machine never searches for a cell, it computes where the cell must be and fetches it directly, exactly as array indexing did in chapter 1, now with the 2D→1D twist baked into the offset. And notice what's doing the work: ncols, the width. The formula only holds because every row is the same width — the grid is rectangular. Store a jagged grid and the trick collapses.

We didn't take this on faith. NumPy lays a matrix out as exactly this flat block, so we can ask the machine for each cell's real address and check it against the formula:

import numpy as np
M = np.arange(20).reshape(4, 5)      # a 4×5 grid, so ncols = 5
base = M.ctypes.data                 # RAM address of cell (0,0)

for (i, j) in [(0,0), (0,3), (1,0), (2,4), (3,4)]:
    offset = (M[i, j:j+1].ctypes.data - base) // M.itemsize
    print((i, j), "formula i*ncols+j =", i*5 + j, " measured offset =", offset)

print("strides (bytes):", M.strides)      # (20, 4)  ·  one row = 5×4 bytes
print("C_CONTIGUOUS:", M.flags['C_CONTIGUOUS'])   # True

Line 2 builds the grid and reshapes it row-major. Line 3 grabs the base address. The loop asks NumPy for the true byte address of each cell, subtracts base, and divides by the slot size to get the offset in elements. Every single one matched the formula exactly: (0,0)→0, (0,3)→3, (1,0)→5, (2,4)→14, (3,4)→19. The last line prints the strides — (20, 4) — the machine's own words for the same fact: stepping one column over moves 4 bytes (one slot, the neighbour), stepping one row down moves 20 bytes (a whole ncols × itemsize leap). Hold onto that asymmetry; the next section is entirely about it.

One multiply, one add, and you're at any cell. So why can two loops that touch every cell — same count, same Big-O — finish many times apart? Because of which direction you walk the line →

Row by row is a sprint; column by column is a stumble

Here is the payoff, and it is pure Volume 3, chapter 2. Summing an n×n grid touches n² cells no matter which way you loop — the operation count, the Big-O, is identical. But the machine doesn't charge by the operation; it charges by the cache line. Recall the metal: every miss to RAM hauls in a whole 64-byte line, betting you'll want the neighbours next, and a prefetcher races ahead when it spots a straight march. A matrix is laid out so that row neighbours are memory neighbours — and column neighbours are ncols slots apart.

So walk it row by row (the inner loop runs along j) and you stream straight down the contiguous strip: one miss pulls in eight useful numbers, the prefetcher sees your line and readies the next. Walk it column by column (the inner loop runs down i) and every single step jumps a full ncols × itemsize stride to a different cache line — a fresh miss per element, seven-eighths of every fetched line thrown away, the prefetcher blind. Same n² reads. Wildly different metal.

We measured both. In pure Python — a nested loop over a 2000×2000 list-of-lists, four million additions either way — row-major ran ≈354 ms and column-major ≈480 ms, about 1.36× slower (timings are hardware-dependent; here the interpreter's own overhead swamps most of the cache cost). To see the effect undiluted, strip the interpreter away and move the same bytes through NumPy's C loop: reading a 4096×4096 block in memory order took ≈41 ms, reading it strided down the columns ≈250 ms — about 6× for the identical data. Same work. The only thing that changed was the direction of the walk.

M = [[1]*2000 for _ in range(2000)]      # a 2000×2000 nested list

def row_major():                          # inner loop runs ALONG a row
    t = 0
    for i in range(2000):
        row = M[i]                        # one row object, then stream it
        for j in range(2000):
            t += row[j]                   # memory neighbours — cache-friendly
    return t

def col_major():                          # inner loop runs DOWN a column
    t = 0
    for j in range(2000):
        for i in range(2000):
            t += M[i][j]                  # jumps between scattered rows — hostile
    return t
# measured best-of-5: row_major ≈ 354 ms · col_major ≈ 480 ms  (≈1.36×)

The two functions compute the identical sum. The only difference is the loop nesting. In row_major the inner loop fixes i and sweeps j, so line 9 marches along one contiguous row after hoisting it into row. In col_major the inner loop fixes j and sweeps i, so line 16 re-indexes a different row object on every step, chasing pointers all over the heap. Swapping two for lines is the whole change — and it's free speed.

The pure-Python numbers were oddly muted — only 1.36×. That's a clue: a Python "matrix" isn't really a contiguous block at all. Which raises the real question — where does a list-of-lists live in memory? →

Python's grid isn't a grid: list-of-lists vs one true block

When you write [[0]*cols for _ in range(rows)], you do not get one flat block. You get what Volume 1 would predict: an outer list holding rows eight-byte references, each pointing off to a separate row-list object allocated somewhere else on the heap. Each of those row-lists is itself a contiguous run of references, pointing to separate integer objects, scattered again. Three levels of indirection, and the rows can sit anywhere — so "moving to the next row" is a pointer-chase to an unrelated address. That's precisely why our column-major stumble was only 1.36×: the layout is already so scattered that walking it "the right way" barely helps.

NumPy does the opposite. An np.zeros((1000,1000)) is one contiguous block of raw values — no per-cell object, no per-row indirection — with a tiny header describing the shape and strides. Let's weigh both:

import sys, numpy as np
r = c = 1000

nested = [[0]*c for _ in range(r)]                 # list of 1000 row-lists
struct = sys.getsizeof(nested) + sum(sys.getsizeof(row) for row in nested)
print("nested list, structure only:", struct, "B")   # 8,064,856 B ≈ 8.06 MB

block = np.zeros((r, c), dtype=np.int64)           # one contiguous block
print("numpy block:", block.nbytes, "B")              # 8,000,000 B  (+128 B header)

# the catch: those shared 0s are ONE cached int. Give each cell a real value:
big = [[i*c + j for j in range(c)] for i in range(r)]  # 1,000,000 distinct ints
print("with distinct values: ~", (struct + r*c*28)//10**6, "MB vs numpy 8 MB")

Line 4 sums the outer list's header plus all 1000 row-lists: 8,064,856 bytes, about 8.06 MB — and that's only the structure, because every cell is the integer 0, which Python caches as a single shared object (Vol 1). The NumPy block on line 7 is 8,000,000 bytes of raw int64 plus a 128-byte header — essentially the same, here, since an 8-byte reference and an 8-byte integer weigh the same. The trap springs on line 12: the moment the cells hold distinct values, each is a real ~28-byte integer object on the heap, and the nested version balloons to ~36 MB while NumPy stays flat at 8 MB — about 4.5× heavier, and every one of those objects a separate cache-missing pointer-chase. NumPy stores numbers; a list-of-lists stores directions to numbers.

So the matrix is a deal: one rigid contiguous block, unbeatable when you touch cells by (i,j) and walk them in storage order. The last move is knowing when that deal is the right one to strike →

The 1% move: pick the layout that matches your walk

Here's the human insight worth stealing. Someone had to notice that a two-dimensional grid doesn't need two dimensions — flatten it once, agree on row-major, and a single multiply-add reaches any cell forever. That's the whole invention: trade the intuitive rectangle for a formula, and indexing becomes free. And the row-major-versus-column-major choice wasn't obvious either — it's a genuine historical fork. C chose row-major; Fortran chose column-major; MATLAB and Julia inherited Fortran's. Neither is "right." What's wrong is code that fights its own storage order — a column-sweeping loop over a row-major block, or vice versa, quietly paying the cache tax on every step.

So the transferable move, the thing that is being good at data structures: know your access pattern before you pick your layout. Ask what you'll do most. Do you index arbitrary cells by (i, j) and sweep in a predictable direction? A matrix is the answer — dense, contiguous, O(1) access, and near-free to stream if your loop nesting agrees with the storage order. Will you mostly walk columns? Store column-major, or transpose once up front and walk rows. The matrix isn't fast in the abstract; it's fast when your walk and its fold point the same way.

Everything so far — the array, the linked list, the stack, the queue, and now the matrix — has lived on a line, whether contiguous or chained. The matrix was the boldest bet on the line: cram a whole second dimension into it and pay with rigid, dense storage. The next family gives that up entirely. It scatters its data across the heap as nodes joined by pointers — and in exchange for abandoning the contiguous block, it buys something the line never could: the power to halve the search space at every single step.

Chapter 8 opens the hierarchy family with the binary tree — a structure with no straight line at all, where each node points to two children, and that simple branching is the seed of logarithmic search. →

08The binary tree — hierarchy, two children at a time

Every structure so far has been a line — an array, a list, a stack, a queue: things in a row. A tree breaks the line. It is the shape of anything that contains things that contain things: a folder of folders, a web page of elements, a company of departments. This chapter builds the plain binary tree — one root, up to two children per node, no cycles — from its scattered bytes on the heap upward. After it you'll see any hierarchy as nodes joined by two pointers, know why one number (its height) decides whether it's lightning or a disaster, and be able to walk it four different ways, each for a different job.

A tree is scattered boxes joined by pointers

First, the words — each defined the moment it appears. A node is one box holding a value. The single node at the top is the root. A node's children are the nodes hanging directly below it; that node is their parent; the link between them is an edge. A node with no children is a leaf. Binary means each node has at most two children, and they are named — a left child and a right child; the position carries meaning, so left and right are not interchangeable. One rule makes it a tree and not a tangle: no cycles — there is exactly one path from the root down to any node.

The cleanest way to say all of that is to say it recursively: a binary tree is either empty, or a node holding a value plus two smaller binary trees (its left and right subtrees). The definition contains itself. Hold that thought — it is the whole reason trees are easy to walk.

Now the memory picture, which is this volume's obsession. Nowhere in RAM is there a thing shaped like a tree. On the heap a tree is a scatter of node objects, each a tiny record with three fields: a reference to its value, a reference to its left child, and a reference to its right child (or None where a child is missing). The root is nothing but a name holding one 8-byte reference (Volume 1). Follow the left and right references from box to box and you are the tree — the shape exists only as pointers.

How heavy is one node? Let's measure, not guess. Give the class __slots__ so its three fields pack straight into the object, and each node is a lean record.

import sys

class Node:
    __slots__ = ('value', 'left', 'right')   # pack the 3 refs INTO the object — no per-instance dict
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left  = left
        self.right = right

root = Node('A', Node('B'), Node('C'))       # a 3-node tree, all on the heap
print(sys.getsizeof(root))                    # 56  → 16-byte header + three 8-byte references

Line 4 is the money line: __slots__ tells CPython to store value, left, and right inside the node itself instead of in a separate instance dictionary. Ran on CPython 3.12.7, sys.getsizeof(root) returns 56 bytes — a 16-byte object header plus the three 8-byte references. Drop __slots__ and each node also drags a 296-byte instance __dict__ behind it: 344 bytes per node, measured. Either way, that is the pointer tax — you pay two extra references per element (16 bytes) purely to encode the shape. Compare a Python list, a contiguous array of references (Volume 1): about 8 bytes per element plus one header. I measured 100,000 slotted nodes at 5,600,000 bytes against the same count in a list at 800,056 bytes — the tree is roughly 7× heavier. A tree is not a light structure; you buy shape with bytes.

The answer isn't in the bytes. It's in one number that measures how tall the scatter of boxes stacks up — the tree's height. →

Height is the whole game

Two more words, precisely. The depth of a node is how many edges you cross to reach it from the root (the root has depth 0). The height of a tree is the depth of its deepest node — the length of the longest root-to-leaf path. Height is the number that governs cost, and here is exactly why: to reach any node, you start at the root and follow one child pointer per level down. So finding, inserting, or deleting a node costs O(height) pointer hops — never more than the height, because that's the longest any path can be. Derive the cost from the layout and it's forced: the work is the walk, and the walk is bounded by the height.

That turns the whole question into: how tall does n nodes have to stack? Two answers, and they could not be further apart.

Balanced. Fill the tree level by level and each level holds twice the one above: 1 root, then 2, then 4, then 8, …, 2^k at level k. So k levels hold up to 2^k+1−1 nodes. Invert that — n nodes need only about log₂n levels. This is the same doubling that makes binary search O(log n) in Volume 3, now standing up in three dimensions. Measured: a balanced tree of 1,000 nodes has height 9; of 1,000,000 nodes, height 19. Nineteen hops to reach any node among a million.

Degenerate. Now insert values already in sorted order into a tree that always sends the larger value right. Every node gets only a right child; the tree collapses into a single diagonal spine. Its height is n−1 — measured, 1,000 nodes give height 999. That is not a tree in any useful sense; it is a linked list (chapter 2) wearing a tree costume, and every search is O(n).

To reach a node you followed pointers, one per level. But each pointer lands at a random address in RAM — and that randomness carries a cost that Big-O never prints on the label. →

The pointer tax, paid again at runtime

A Python list is contiguous: element i lives at base + i·8, so scanning it streams whole cache lines the CPU prefetched (Volume 3's memory hierarchy). A tree's nodes were allocated one at a time, whenever you inserted them, so they sit at unrelated addresses — look back at the memory diagram's scattered 0x7f… values. Walking the tree means chasing a pointer to a random location every single step. The prefetcher cannot guess where you'll jump next, so each hop risks a cache miss and a stall while the machine waits on RAM. Same O(n) node count as a list scan; wildly different real speed. The exponent ties; the constant, set by the memory layout, decides.

Measured, and hedged as machine-dependent: summing a million values by walking a balanced tree in Python took about 312 ms on this machine; summing the same million from a contiguous list in an equivalent Python loop took about 82 ms — roughly 3.8× faster. (The built-in sum(), running in C over that same packed array, did it in ~6.6 ms.) Part of the tree's penalty is the explicit stack and the attribute lookups; part is the cache misses of pointer-chasing. Both are the price of scatter — and both are invisible in the O(n) that the two share.

You can — and that exact trick is the secret of the heap in chapter 10. But first: how do you visit every node at all, when the shape exists only as pointers? The structure hands you the tool. →

Recursion is a tree's native tongue

Volume 3 taught recursion: solve a big problem by solving smaller versions of the same problem, down to a base case that needs no thought. A binary tree is that shape frozen into data — a node whose two children are themselves smaller trees. So the walk writes itself. To do something to a tree: handle this node, then recurse on the left subtree, then recurse on the right subtree. The base case is the empty tree (None), which needs no work at all. No loops, no manual bookkeeping — the data's self-similarity becomes the code's.

The smallest possible example is measuring the height itself:

def height(node):
    if node is None:          # BASE CASE: an empty tree is -1 edges tall
        return -1
    return 1 + max(height(node.left), height(node.right))   # 1 edge + the taller subtree

Line 2–3 is the floor: an empty tree contributes −1, so that a lone leaf (whose two children are empty) comes out to 0. Line 4 is the shrink: this node adds one edge on top of whichever subtree is taller, and each subtree is measured by the very same function on smaller data. It visits every node exactly once, so it is O(n). Ran on the six-node tree above, height returns 2 — matching the diagram.

Notice the three moves inside every tree walk: touch this node, go left, go right. The only real decision is when you touch the node relative to the two descents — and that single choice spawns four different walks, each with a different job. →

Four walks, four jobs

A traversal is a rule for visiting every node exactly once. Three of the four are depth-first — they plunge to the bottom before backing up — and they differ only by where the “touch the node” step sits among the two recursive descents. Slide that one line and you get three orders:

• Pre-order (node · left · right): touch the parent before its children. You emit a folder before its contents, a parent before its subtree — perfect to serialize or copy a tree, because a reader rebuilds it top-down.
• In-order (left · node · right): touch the node between its subtrees. On an ordered tree (a BST, chapter 9) this visits values in sorted order — the reason BSTs exist.
• Post-order (left · right · node): touch the parent after both children. You can't free a folder before its files, or add two numbers before you have them — so this is the order for deleting a tree and for evaluating an expression tree.

The fourth is breadth-first. Level-order abandons recursion for a queue (chapter 4; this is exactly BFS from Volume 3): visit the root, enqueue its children, pop the next node, enqueue its children, and repeat. You sweep the tree one level at a time, nearest first — the walk you want when “closest to the root” means “most important.”

from collections import deque

def inorder(node, out):
    if node is None: return         # base case: empty subtree, nothing to do
    inorder(node.left, out)         # LEFT subtree first
    out.append(node.value)          # THEN this node
    inorder(node.right, out)        # THEN the RIGHT subtree
# pre-order: move the append ABOVE the two calls; post-order: move it BELOW both.

def levelorder(root):
    out, q = [], deque([root])      # a queue (Vol 1 deque) — this is BFS
    while q:
        node = q.popleft()          # take the shallowest waiting node
        out.append(node.value)
        if node.left:  q.append(node.left)    # its children go to the BACK
        if node.right: q.append(node.right)
    return out

The top function is the whole depth-first family: those three lines, with append in the middle slot, are in-order; lift it above both recursive calls and you have pre-order; drop it below both and you have post-order. The bottom function swaps the call stack for an explicit queue — pull from the front, push children to the back — and that single change turns depth-first into level-by-level. Ran on the six-node tree A(B(D,E), C(·,F)), CPython 3.12.7 gave exactly: in-order D B E A C F, pre-order A B D E C F, post-order D E B F C A, level-order A B C D E F.

Four walks and a two-pointer node: that's the entire general binary tree. Its power comes alive the moment you add one rule to the shape — and each rule you can add is a whole chapter. →

When to reach for a tree

Strip everything away and a binary tree earns its keep in two situations. First, when your data is a hierarchy — a thing that contains things that contain things — the tree isn't a clever choice, it's the honest shape of the data: files, the DOM, an org chart. Second, when you need logarithmic reach — insert, find, and delete all in O(log n) — a tree delivers it, but only while its height stays near log n. That “only while” is the entire craft. A bare binary tree gives you the shape; it does not defend the balance. The specialized trees ahead each add exactly one rule to earn the log back and never let it slip.

That is the 1% move, and it is most of what being “good at data structures” actually is: match the access pattern to the layout. See a hierarchy → a tree. Need ordered data with fast search → a BST. Need the smallest (or largest) item again and again → a heap. Need to look things up by prefix → a trie. All four are this chapter's node-with-two-pointers wearing one extra discipline. Choosing the right discipline on sight — before you write a line — is the skill; the code is the easy part that follows.

Next (chapter 9): add a single rule to the shape you just learned — every value in the left subtree smaller than the node, every value on the right larger. Suddenly the in-order walk prints in sorted order for free, and finding a value becomes binary search running on a tree. That is the binary search tree — and the whole fight to keep it from degenerating into the spine you met here. →

09The binary search tree — order that stays searchable

A sorted array lets you binary-search in O(log n) — but the instant you insert one value in the middle, every element after it shifts, an O(n) tax on every change. A hash table (chapter 6) gives O(1) lookup but throws order in the bin: it cannot tell you the smallest key, or every key between 100 and 200. The binary search tree is the deal that keeps both: it stays sorted and stays fast to change, by holding order not in memory positions but in pointers. After this chapter you will insert, search, and delete in a BST, see exactly why one careless insertion order can turn it into a slow linked list, and know the fix that runs every database index on Earth.

One rule, wired into every pointer

Chapter 08 built the general binary tree: nodes on the heap, each holding data and up to two child pointers, left and right. A BST is that same skeleton plus a single, ruthless invariant — a rule that must hold at every node, without exception: everything in my left subtree is less than me; everything in my right subtree is greater than me. Not just my two children — my entire left subtree, all the way down, and my entire right subtree. That one promise is what turns a tree into a search structure.

Because the rule holds everywhere, a BST has a hidden talent you met in chapter 08: walk it in-order — left subtree, then the node, then right subtree — and the keys come out sorted, for free, no sorting step. We built one and walked it:

class Node:
    __slots__ = ("key", "left", "right")   # three references, nothing else
    def __init__(self, key):
        self.key  = key
        self.left = None                    # < me
        self.right = None                   # > me

root = None
for k in [4, 2, 6, 1, 3, 5, 7]:            # inserted in this order
    root = insert(root, k)

out = []
inorder(root, out)
print(out)          # [1, 2, 3, 4, 5, 6, 7]   ← sorted, though we never sorted

Line by line: each Node is three references — the key, a left pointer, a right pointer — and nothing more. We insert seven keys in a jumbled order. Then an in-order walk prints them 1 2 3 4 5 6 7: sorted output falls out of the invariant, because "smaller stuff is always on the left" is exactly what in-order visits first. Order isn't stored — it's implied by where the pointers go.

Now the memory bill, run for real. A node with __slots__ is the leanest a Python BST node gets, and we measured it:

import sys
sys.getsizeof(Node(30))          # 56   ← 16 GC + 16 header + 3×8 pointers
# a plain class (no __slots__):
sys.getsizeof(dict_node)         # 48   object…
sys.getsizeof(dict_node.__dict__)# 296  …plus its instance dict = 344 total
# the same 1000 ints in a Python list:
sys.getsizeof(list(range(1000))) # 8056 → ~8 bytes per reference

Read the tax. Every BST node costs 56 bytes at best (344 if you skip __slots__), of which only 24 bytes — three 8-byte references — is the data-carrying part; the rest is Python's per-object overhead (Vol 1's ~32-byte object header, here split as a 16-byte GC header and a 16-byte object head). A plain list stores those same references at 8 bytes each in one contiguous block. So a BST is roughly 7× heavier per element than a list. You are paying that overhead to buy something a list can't give you: sorted order that survives insertion and deletion in O(log n). Whether that trade is worth it is the whole question of the chapter.

The invariant isn't decoration. It's a machine for cutting the problem in half at every step →

Search: a binary search that walks pointers

Here is where the invariant pays off. To find a key, start at the root and compare. Three outcomes: equal — found it, stop. Target is smaller — the invariant guarantees it can only be in the left subtree, so the entire right subtree is eliminated in one comparison. Target is larger — go right, and the whole left subtree is gone. Each comparison throws away one of the two subtrees. That is binary search — the halving technique from Vol 3 ch5 — but instead of indexing into a sorted array, you are following pointers down a tree:

def search(root, target):
    node = root
    while node is not None:          # until we fall off the tree
        if target == node.key:
            return node              # found — stop
        elif target < node.key:
            node = node.left         # smaller → whole right subtree gone
        else:
            node = node.right        # larger  → whole left subtree gone
    return None                      # ran out of tree → not present

Line by line: we hold a moving pointer node, starting at the root. Each loop is one comparison. If equal, done. If target < node.key we step left; otherwise right. When node becomes None we've walked off a branch tip without a match — the key isn't there. The number of loops is exactly the number of levels we descend: the path length from root to where the key is (or would be).

So search costs O(h), where h is the tree's height — the longest root-to-leaf path. And here is the crux: if the tree is balanced, each level roughly doubles the node count (1, 2, 4, 8, …), so n nodes fit in about log₂ n levels, and search is O(log n). We built a million-node tree and searched it:

# tree of 1,000,000 keys, inserted in random order:
#   height              = 50        (log2(1,000,000) ≈ 19.9)
#   search steps for 20 random keys: min 17, max 35, avg 26.1

A million keys, and a lookup touches on average 26 nodes — not a million. That is the log at work: each of those 26 comparisons halved what remained. (The height is 50 rather than the ideal 20 because a randomly-built BST is only roughly balanced — more on that, and how to force it to 20, shortly.)

Search reads the tree. Insert has to grow it — and it turns out inserting is just searching for the empty spot where the key belongs →

Insert: search for where it isn't, then hang a node

Insertion reuses search entirely. To add a key, you search for it — comparing and stepping left/right — until you fall off the bottom of the tree at a None. That spot is exactly where the key belongs, because the path you walked is the same path a future search will walk to find it. You allocate a new node and hang it there. One walk down, one link:

def insert(root, key):
    if root is None:                 # empty spot found → this is the place
        return Node(key)
    if key < root.key:
        root.left  = insert(root.left,  key)   # belongs somewhere on the left
    elif key > root.key:
        root.right = insert(root.right, key)   # …or somewhere on the right
    # key == root.key: already present, do nothing (a BST holds a set)
    return root

Line by line: hit a None and you've arrived — return a fresh node, and the caller links it in. Otherwise compare and recurse into the correct subtree, re-attaching the (possibly grown) subtree on the way back up. Equal keys are ignored here, so this BST behaves as a set. The cost is the length of the walk — O(h) again, the same descent as search, plus one node allocation. Crucially, the existing nodes never move: unlike a sorted array, inserting into the middle of the key range shifts nothing. You only rewire one None into a pointer.

Insert always plants the node at the end of its search path. Which raises a dangerous question: what if every key's search path leads to the same side — every single time? →

The catastrophe: sorted input collapses the tree into a list

Everything above assumed the tree is bushy — short and wide. But nothing in insert guarantees that. The shape is decided entirely by the order keys arrive in. Feed a BST already-sorted data and watch what happens: insert 1, it's the root. Insert 2 — it's bigger, go right. Insert 3 — bigger than 1, go right; bigger than 2, go right again. Every new key is the largest so far, so every insert goes right, right, right. The tree grows a single right-leaning limb with no left children at all. We ran it and measured the heights:

# insert 1,2,3,4,5,6,7 in that order → height = 7   (a chain of 7)
# insert 4,2,6,1,3,5,7 (jumbled)      → height = 3   (a bushy tree)

#        n   sorted-insert height   random-insert height   log2(n)
#       15                     15                      8      3.9
#     1000                   1000                     20     10.0
#    10000                  10000                     30     13.3
#    30000                  30000                     36     14.9

Read the columns of horror. Sorted insertion gives height exactly n — every node has one child, a straight line. It is no longer a tree; it is a linked list that happens to store its "next" pointer in the right field. And a linked list means search is O(n): to find the last key you walk all n nodes. The BST's entire reason for existing — O(log n) — is gone. The random column shows what balance would give you: 1000 keys in height 20, 30000 keys in height 36, hugging log₂ n. Same keys, same code, same invariant — a 50× difference in height, decided only by arrival order.

We even timed the collapse, searching for the deepest key in each tree:

#   n     degenerate (chain)   balanced (random)
#  1000        115 µs               1.06 µs
#  2000        231 µs               1.06 µs
#  4000        462 µs               0.55 µs

The degenerate column doubles as n doubles — the fingerprint of O(n) — while the balanced column just sits near a microsecond no matter the size, the fingerprint of O(log n). At n=4000 the balanced tree answers roughly 800× faster for the same keys. (Timings are from this machine and will vary run to run; the shapes — one line climbing, one flat — are the invariant truth.)

A structure whose whole value can be destroyed by sorted input is a structure begging for a guardian. Humans built one →

The fix humans invented: trees that rebalance themselves

The degeneracy problem has a clean statement: after enough one-sided inserts, the tree gets tall. So the fix is a structure that notices when it's leaning and straightens itself back out — a self-balancing tree. The key mechanical trick is the rotation: a small, local rewiring of three or four pointers that lifts a deep subtree up and pushes a shallow one down, without breaking the left<node<right invariant. A rotation is O(1) — it touches a constant number of pointers — and it changes the tree's shape but not its sorted meaning.

Two famous designs wrap rotations in a self-balancing policy — you use their descendants constantly, so meet them by name. An AVL tree keeps every node's two subtree heights within 1 of each other; the moment an insert violates that, it rotates. It's the strictest, so it's the shortest and the fastest to search. A red-black tree is looser — it colours nodes red or black and enforces rules that keep the longest path at most twice the shortest — which means fewer rotations on insert/delete, a better all-round trade. (We stay at the concept here: the promise is "height stays O(log n)"; the exact rotation cases are a topic of their own.) Red-black trees are not academic trivia — they are the ordered map and ordered set in your standard library: C++'s std::map/std::set, Java's TreeMap/TreeSet, the Linux kernel's process scheduler and virtual-memory areas. Every time you iterate a Java TreeMap in sorted order, you are walking a balanced BST in-order.

Why fat nodes for disk? This is mandate #3 — how the machine gets the benefit — and it's the same cache story from Vol 3 ch2, one level down. Reading from a disk (even an SSD) happens in fixed blocks — typically 4 KB or more — and a single disk seek is glacial next to RAM: hundreds of thousands of times slower. A binary tree of a billion keys is ~30 levels deep, so a lookup could be 30 separate disk seeks — catastrophic. A B-tree sizes each node to fill exactly one disk block, packing perhaps 100–500 keys into it. Now the tree is only 3–4 levels deep for a billion keys, because each level branches 100+ ways instead of 2. A lookup is 3–4 block reads instead of 30 seeks. The design move: match the node to the transfer unit of the storage. Pointer-chasing a skinny binary tree wastes almost the entire block it drags in; a B-tree makes every expensive block read carry hundreds of useful keys.

Search, insert, and balance handle growing the tree. One operation is still missing, and it's the only one with a genuine puzzle in it: taking a node out →

Delete: the operation with a twist

Deleting from a BST has to preserve the invariant, and that makes it the one operation with real cases. Find the node (an O(h) search), then handle three situations by how many children it has:

• No children (a leaf). Easiest: just null out the parent's pointer to it. The node vanishes; refcount drops to zero; Python reclaims it (Vol 1).
• One child. Splice it out — connect the node's parent directly to the node's single child. The subtree slides up one level, order intact.
• Two children. The puzzle. You can't just remove it — two subtrees would be orphaned. The classic fix: don't remove the node, overwrite its key with its in-order successor — the smallest key in its right subtree, which is exactly the next value in sorted order — then delete that successor (which, being leftmost, has at most one child, reducing to an easy case).

Why the successor works: the smallest key on the right is larger than everything on the left and smaller than everything else on the right, so it's the unique value that can sit in the vacated spot without breaking left<node<right. We ran all three cases and checked the in-order output stayed sorted after each:

def delete(root, key):
    if root is None: return None
    if key < root.key:   root.left  = delete(root.left,  key)
    elif key > root.key: root.right = delete(root.right, key)
    else:                                     # found the node to remove
        if root.left  is None: return root.right   # 0/1 child
        if root.right is None: return root.left    # 1 child
        succ = root.right                          # 2 children:
        while succ.left is not None:               #   find in-order successor
            succ = succ.left                       #   (leftmost of right subtree)
        root.key = succ.key                        # overwrite, don't unlink
        root.right = delete(root.right, succ.key)  # delete the successor
    return root

Line by line: the first two branches are just search, recursing left or right and re-linking. Once found: if a child is missing, return the other child (covering the leaf and one-child cases in two lines). With two children, walk right then left-to-the-end to reach the successor, copy its key up into the current node, and delete the successor from the right subtree. The output confirmed order held through every case:

# start:            [1, 2, 3, 4, 5, 6, 7, 8, 9]
# delete leaf 1:    [2, 3, 4, 5, 6, 7, 8, 9]
# delete 7 (1 child)[2, 3, 4, 5, 6, 8, 9]
# delete 3 (2 kids) [2, 4, 5, 6, 8, 9]   ← 3 replaced by successor 4
# delete root 5     [2, 4, 6, 8, 9]      ← new root is successor 6

Every line is still perfectly sorted — the invariant survived deletion of a leaf, a one-child node, a two-child node, and even the root. All of it is O(h): a search to find the node, plus a walk to the successor, both bounded by the height. In a balanced tree, O(log n); in that degenerate chain, O(n) — the same tax hangs over delete as over everything else.

That question is the whole point of learning structures. The answer is the last idea in the chapter →

When to reach for a tree — the access pattern is the answer

A hash table wins on a single point lookup — "is key X here, and what's its value?" — hands down, O(1) versus O(log n). If that is all you do, use the dict; don't reach for a tree to feel clever. The tree earns its keep the moment your questions become ordered ones — the exact questions a hash table, which scatters keys to random slots, physically cannot answer without scanning everything:

• Range queries. "All keys between 100 and 200." In a balanced BST: find 100 in O(log n), then walk in-order until you pass 200. A hash table would have to examine every key.
• Order statistics & neighbours. Smallest key, largest key, the next key above X, the previous key below X — all O(log n) in a tree, all impossible-without-a-scan in a hash.
• Sorted iteration. "Give me everything in order." An in-order walk, O(n) with no separate sort. A hash table would need to extract and sort, O(n log n).

That's the transferable move, mandate #5: choosing the structure is choosing which questions are cheap. Point lookup only → hash. Ordered questions on changing data → balanced tree. Ordered questions on data that rarely changes → don't even use a tree; sort an array once and binary-search it (Vol 3 ch12), because a contiguous array streams through cache far faster than a tree of scattered nodes. The decision table:

A BST spends O(log n) to keep total order — every key rank exact. But a huge class of problems doesn't need the whole order — only "what's the most extreme one right now?" Give up full sorting, keep just that, and you get a structure so lean it lives in a flat array with no pointers at all. That's the heap, chapter 10 →

10The heap — a tree that lives in an array

The last two chapters gave a tree two pointers per node and let it scatter across the heap. This chapter takes one of those pointers away — both of them, actually — and something strange happens: the tree keeps its shape but loses its scatter. A heap is a binary tree with a rule so tight it needs no pointers at all; it folds flat into one contiguous array, and pure arithmetic navigates it. After this chapter you'll see why the smallest item in a million is always sitting at index 0, why pulling it out costs only ~20 hops, and why every priority queue, scheduler, and shortest-path frontier you've ever used is this one array underneath.

A whole tree, and not one pointer

Two words first, each defined the moment it appears. A complete binary tree is a binary tree that is filled level by level, top to bottom, and each level left to right — every level is full except possibly the last, and the last is packed to the left with no gaps. That "no gaps" rule is the whole secret; hold it. The second word is the heap property: in a min-heap, every parent is less than or equal to both of its children. Not sorted — just parent-below-children, everywhere. Two consequences fall straight out: the smallest value in the entire tree has nobody smaller above it, so it must sit at the root; and the arrangement is a partial order, so the root's two children can be in any order relative to each other.

Now the memory picture — this volume's obsession. A plain binary tree (chapter 8) had to store, in every node, two pointers just to remember where its children live, because the nodes sat at unrelated heap addresses. A complete tree has no gaps, so number its nodes in reading order — root 0, then 1, 2, then 3, 4, 5, 6 — and those numbers are dense: 0, 1, 2, 3, … with nothing missing. Dense integers starting at zero are exactly what an array index is. So drop the values into a flat array in that order and the tree is gone as a scatter and present as an array. The shape isn't stored anywhere — it's implied by position. That is the human insight this whole chapter rests on.

So how heavy is it? Weightless, by tree standards — measure, don't guess. A heap of n items is one list of n references: about 8 bytes per element of structure, plus one small header. A pointer-based tree node (chapter 8) spent 56 bytes per node just to hold a header and two child pointers — and the heap pays none of that.

import sys
heap = [1, 3, 6, 5, 9, 8, 7]          # a heap is just a list
print(sys.getsizeof(heap))            # 120  → header + 7 eight-byte references

big = list(range(100_000))            # 100k-element heap
print(sys.getsizeof(big))             # 800056  → 8.00 bytes/element of structure
print(sys.getsizeof(big) / 100_000)   # 8.00056

Line 3, on CPython 3.12.7: the seven-element heap weighs 120 bytes — a list header plus seven 8-byte slots. Line 6: a 100,000-element heap is 800,056 bytes, which is line 7's 8.00 bytes of structure per element. The pointer tree of chapter 8 needed 56 bytes per node for the same 100,000 nodes — 5,600,000 bytes, measured, 7× heavier. The heap is the lightest tree there is, because it is the only tree that stores zero shape. (As always, the values themselves are separate objects on the heap — the array holds references, exactly like any Python list.)

It turned into a calculation. When there are no gaps, the address of a child isn't stored — it's computed. →

The address of a child is a formula

Here is why "no gaps" buys everything. Number the tree in reading order and look at any node at index i. Its two children are the next two nodes to be laid down after all of i's left-neighbours filled their children — and because the tree is complete, "next two" lands at fixed offsets. The result is three formulas that never change:

• left child of i is at 2*i + 1
• right child of i is at 2*i + 2
• parent of i is at (i - 1) // 2 (integer division — the two child formulas run backwards)

Check it against the figure. Node [1] holds 3; its children should be at 2·1+1=3 and 2·1+2=4 — indices 3 and 4 hold 5 and 9, the two nodes drawn beneath it. Correct. Node [5] holds 8; its parent is at (5-1)//2 = 2 — index 2 holds 6, drawn directly above it. Correct. No search, no pointer dereference: navigating the tree is doubling and halving an integer. That is O(1) per hop, and it is the cheapest kind of O(1) — a shift and an add, no memory touched to find the address.

def left(i):   return 2*i + 1
def right(i):  return 2*i + 2
def parent(i): return (i - 1) // 2

h = [1, 3, 6, 5, 9, 8, 7]
print(h[left(1)], h[right(1)])   # 5 9   → the children of node 3
print(h[parent(5)])              # 6     → the parent of node 8

Those three one-liners are the complete navigation system of a heap — no Node class, no .left/.right fields, nothing on the heap but the array. Lines 6–7 ran on CPython 3.12.7 and printed exactly 5 9 and 6, matching the diagram.

We can climb and descend for free. Now use it: to add a value and keep the heap a heap, you only ever walk one path — straight up. →

Insert = drop it at the end, then let it climb

Adding to a heap has to preserve two things at once: completeness (no gaps) and the heap property (parent ≤ children). Completeness pins the answer to where the new value goes: the only spot that keeps the tree gapless is the very next array slot — append it to the end. That is O(1) amortized, the list's own trick from Volume 1. But the newcomer may be smaller than its parent, breaking the heap property on that one edge. So we repair it by sift-up (also called bubble-up or percolate-up): compare the new value with its parent; if it's smaller, swap them; repeat from the new position, until either it's no longer smaller than its parent or it reaches the root.

Why is that correct, and why O(log n)? Correct because each swap fixes the only broken edge and can only create a new broken edge one level up — the disorder travels upward and nowhere else. Cheap because it walks a single root-ward path, and the tree's height is ⌊log₂n⌋ (a complete tree is as short as a tree can be). So a heap of a million items is 19 levels tall — an insert touches at most 19 slots. Watch it happen with a real value:

Insert 2 into [1, 3, 6, 5, 9, 8, 7] and this is exactly the trace CPython 3.12.7 produced: 2 is appended at index 7; its parent at (7-1)//2=3 is 5, and 2 < 5, so they swap; its new parent at index 1 is 3, and 2 < 3, so they swap; its next parent at index 0 is 1, and 2 ≥ 1, so it stops. Two swaps, final array [1, 2, 6, 3, 9, 8, 7, 5]. In real code you never hand-roll this — Python's heapq is the heap, operating in place on an ordinary list.

import heapq
h = [1, 3, 6, 5, 9, 8, 7]      # already a valid min-heap
heapq.heappush(h, 2)           # insert 2, sift-up runs internally
print(h)                       # [1, 2, 6, 3, 9, 8, 7, 5]
print(h[0])                    # 1   → the minimum, O(1), always at index 0

heapq.heappush (line 3) does the append-then-sift-up you just watched, in C, in place on the list h. Line 4 printed [1, 2, 6, 3, 9, 8, 7, 5] — the same array the trace produced. And line 5 is the quiet superpower: the minimum is always at h[0], so peeking at it is a single array read, O(1), no matter how many items the heap holds.

Peeking at the minimum is free. But a priority queue has to remove it and hand you the next-smallest — and the root is the one slot you can't just delete without tearing a hole in the tree. →

Extract-min = promote the last, then let it sink

To remove the minimum you can't simply erase index 0 — that would orphan its two subtrees. The trick mirrors insert. Take the root's value to return it. Now you need to fill the hole at the top and keep the tree complete, and there's exactly one value whose removal keeps it gapless: the last one in the array. So move the last element up to the root, shrinking the array by one. That almost certainly violates the heap property — a leaf value now sits at the top — so repair it downward with sift-down (bubble-down): compare the value with its smaller child; if it's larger, swap with that child; repeat, until it's ≤ both children or reaches a leaf. Comparing against the smaller child is the subtle, essential detail — swap with the larger and you'd just recreate the violation.

That figure is the exact run from CPython 3.12.7: pop 1; move last value 7 to the root; 7 > 3 (the smaller of children 3 and 6) so swap; 7 > 5 (its new smaller child) so swap; now a leaf — stop. Final heap [3, 5, 6, 7, 9, 8], and the new minimum 3 has surfaced at index 0. The whole operation walked one path down, so it is O(log n) — 19 steps for a million items.

import heapq
h = [1, 3, 6, 5, 9, 8, 7]
heapq.heapify(h)               # make sure it obeys the heap property
smallest = heapq.heappop(h)    # remove & return the min; sift-down runs internally
print(smallest)                # 1
print(h)                       # [3, 5, 6, 7, 9, 8]

heappop (line 4) performs the promote-last-then-sift-down you just traced and hands back the minimum. Line 5 printed 1; line 6 printed [3, 5, 6, 7, 9, 8] — matching the figure exactly. Push and pop together give you a priority queue: a bag you throw items into in any order and always draw the smallest (or highest-priority) out, each operation O(log n), the peek free.

Push, pop, peek — the whole priority queue. But there's a faster way in than pushing one at a time. Handing a heap a whole array at once costs less than you'd ever guess. →

Building a heap in O(n) — the pleasant surprise

You have an array of a million values in random order and you want a heap. The obvious way: start empty and heappush each item — n inserts, O(log n) apiece, so O(n log n) total. But there's a better way, and its cost is a genuine surprise. Heapify works bottom-up, in place: skip the leaves (the second half of the array — they're already valid one-element heaps), and run sift-down on every internal node from the last one back to the root. When you fix a node, its two subtrees are already heaps, so one sift-down settles it.

Now the surprise — and it's worth deriving, because the intuition "n nodes times log n each = O(n log n)" is exactly the trap. That estimate assumes every node sinks the full height. It doesn't. Half the nodes are leaves and do zero work. A quarter sit one level up and sink at most one step. An eighth sink at most two. In general, the many nodes near the bottom have almost no distance to fall, and only the lone root can fall the full ⌊log₂n⌋. Sum the real work — n·(1/2·0 + 1/4·1 + 1/8·2 + 1/16·3 + …) — and the series in parentheses converges to a constant (it's under 1). Total work is proportional to n. Heapify is O(n): you can turn a raw array into a heap in linear time.

import heapq, random
data = [random.randint(0, 10**9) for _ in range(1_000_000)]

# way 1: push one at a time — O(n log n)
h1 = []
for x in data: heapq.heappush(h1, x)

# way 2: heapify the whole array in place — O(n)
h2 = list(data)
heapq.heapify(h2)              # ~2.3x faster here, and the gap widens with n

Timed on this machine (CPython 3.12.7 — timings are machine-dependent): building the million-item heap by repeated heappush took about 65 ms; heapify on the same data took about 28 ms — roughly 2.3× faster, both producing a valid heap with the same minimum. The measured gap here is modest because Python's per-operation overhead dominates, but the asymptotic difference — O(n) versus O(n log n) — only grows as the data does. When you have all the items up front, always reach for heapify.

Peek in O(1), push and pop in O(log n), build in O(n), sort in O(n log n) — all from one flat array. Now the only question left is the one that matters most: when, on sight, is a heap the right container? →

When to reach for a heap

The heap answers one access pattern, and it answers it better than anything else: "give me the most extreme item, over and over, while items keep arriving." Not "sort everything" — that's a one-shot. Not "look things up by key" — that's a hash map (chapter 6). The heap's home is the running extreme: a set that changes under you, from which you repeatedly pluck the min or max. The instant a problem sounds like "always process the smallest / largest / nearest / highest-priority next," the heap is the answer, and choosing it on sight is most of what "good at data structures" means.

The clean way to feel the win is top-k. To find the 10 largest of a million numbers, you do not sort the million (O(n log n)) — you keep a heap of just 10 and let each new number bump the smallest survivor (O(n log k)).

import heapq, random
scores = [random.randint(0, 10**6) for _ in range(1_000_000)]

top10 = heapq.nlargest(10, scores)     # a size-10 heap sweeps the stream once

Measured on this machine: heapq.nlargest(10, scores) over a million values took about 14 ms, against about 149 ms for sorted(scores, reverse=True)[:10] — the same ten numbers, roughly 10× faster, because the heap never pays to order the 999,990 items you were going to throw away. That is the whole art: the heap sorts nothing; it just keeps the boundary.

Finally, the boundary that trips people — heap versus the binary search tree of chapter 9. Both are binary trees; they are opposites in purpose. A BST enforces a total order (left < node < right) so it can find any value and walk everything in sorted order — but it's a pointer structure that must fight to stay balanced. A heap enforces only a partial order (parent ≤ children) so it can find one value — the extreme — and it lives pointerless in an array, always perfectly balanced by construction. Ask "is 42 in here?" and the heap is useless (O(n) — it must scan). Ask "what's the smallest?" and the BST is merely fine while the heap is instant.

That is the 1% move in one line: match the question to the layout. "Any key, in order" → a BST or a hash map. "The extreme, repeatedly, as data streams" → a heap. Recognising which of those two questions a problem is really asking — before you type — is the whole skill; import heapq is the easy part that follows.

Next (chapter 11): we've keyed data by number and by hash, and ordered it by comparison. But some data is made of sequences of symbols — words, IP addresses, DNA — and there's a tree that branches not on "bigger or smaller" but on the next character, turning "find every word starting with str" into a walk of three steps. That's the trie, the structure behind autocomplete, spell-check, and how a router decides where your packet goes next. →

11The trie — a tree indexed by letters

Every tree so far stored a value in each node. A trie does something stranger: it stores the value in the path. A word isn't kept in a box — it's spelled by the walk from the root, one letter per edge, and any words that begin the same way share the same first steps. This chapter builds the prefix tree from its scattered heap nodes up. After it you'll see a word as a route, know exactly why finding cat takes three steps whether the trie holds ten words or ten million, and be able to do the one thing a hash map simply cannot — ask for every key that starts with cu.

A word is a path, not a payload

The words first, each pinned down as it appears. A trie (from retrieval — many say it "try" to keep it distinct from "tree") is a tree whose edges are labelled with symbols — here, letters. A node holds two things and, remarkably, not the letter: a children map that sends a next-symbol to the child node it leads to, and a boolean end-of-word flag that says "a stored word finishes exactly here." The letter lives on the link, not in the node. So a key is the sequence of edge-labels you cross from the root down to an end-flagged node. The root spells the empty string; walk c, then a, then t, land on a node whose flag is true, and you have read the word cat off the edges.

The magic is what happens when two words agree at the start. cat and car share c-a, so they share those two nodes and only split at the third step. This is the defining move of the structure: a shared prefix is a shared path. Store a thousand words beginning auto… and the a-u-t-o spine exists exactly once, with a thousand routes fanning out past it.

Now the memory picture — this volume's obsession. Nowhere in RAM is there a lattice of letters. On the heap a trie is a scatter of tiny node objects, each one a record of two fields: a reference to its children map (itself a hash table, chapter 6) and a one-byte-ish flag. The root is just a name holding a single 8-byte reference (Volume 1). Every edge is a key in some node's children dict pointing at another scattered node. Follow the keys and you are the trie; the shape exists only as pointers, exactly as it did for the binary tree in chapter 8 — only now each node branches by label, not by fixed left/right.

How heavy is one node? Measure, don't guess. Give the class __slots__ (Volume 1) so its two fields pack straight into the object.

import sys

class TrieNode:
    __slots__ = ('children', 'is_end')   # pack the 2 fields INTO the object
    def __init__(self):
        self.children = {}                # a dict: letter -> child TrieNode
        self.is_end   = False             # does a stored word end here?

n = TrieNode()
print(sys.getsizeof(n))                    # 48  → node record itself
print(sys.getsizeof(n.children))           # 64  → its (empty) children dict

Line 4 is the shape of the whole structure: a node is a map plus a flag. Ran on CPython 3.12.7, sys.getsizeof(n) returns 48 bytes for the node record, and the empty children dict it points at is another 64 — so a bare node costs about 112 bytes before it holds a single child. That dict is the trie's whole personality: it's how one node branches into many. Hold that number; the next two sections are a fight over it.

Start with the thing it does faster in a way you can feel: its lookup cost doesn't depend on how much you've stored. Let's derive that from the layout. →

Why lookup costs the word's length, not the dictionary's size

Reading a word out of a trie is a walk, and the walk writes itself: stand on the root, and for each character of the key, follow the child link for that character. If the link is missing, the word isn't stored — stop. If you run out of characters, check the end-flag on the node you're standing on. That's it.

def insert(root, word):
    cur = root
    for ch in word:                       # one step per character
        if ch not in cur.children:
            cur.children[ch] = TrieNode()  # carve a new path node when needed
        cur = cur.children[ch]            # descend the link labelled ch
    cur.is_end = True                     # plant the flag where the word ends

def contains(root, word):
    cur = root
    for ch in word:
        cur = cur.children.get(ch)        # follow the link, or None if absent
        if cur is None:
            return False                  # fell off the tree → not stored
    return cur.is_end                     # arrived → is a WORD only if flagged

Read contains as the cost model. The loop runs once per character of the key, and each pass does exactly one dict lookup and one pointer hop. So a key of length L costs L steps — the operation is O(L). Look at what's not in that count: the number of words already stored, N, appears nowhere. Whether the trie holds ten words or ten million, cat is three links from the root and no more. The last line earns its keep: arriving at a node isn't enough — ca is a real node on the way to cat, but it's a word only if its flag is set. The end-flag is what separates a prefix from a word.

I built tries of 1,000, 100,000, and 1,000,000 random 8-letter words and timed 200,000 lookups of the fixed word cat at each size. Machine-dependent, so hedge the nanoseconds — but the shape is the point:

N=    1000: nodes=     6538   lookup('cat') ~ 163 ns
N=  100000: nodes=   507662   lookup('cat') ~ 160 ns
N= 1000000: nodes=  4381570   lookup('cat') ~ 161 ns   # 1000x the words, same time

The trie grew by a factor of a thousand — from 6,538 nodes to 4.4 million — and the lookup didn't move: ~161 ns, three hops, flat. That flatness is O(L) with no hidden N. Now the honest comparison the scope demands. A hash map (chapter 6) is also O(L) in the key, because its hash function must read every one of the L characters to compute a bucket, and a match re-checks all L on the hit. So both structures touch all L characters — the "trie is O(L), dict is O(1)" line you'll hear is a half-truth. The real difference is how they touch them: the trie consumes the key one character at a time along a path, so it can quit at the first missing link and, crucially, every prefix it passes through is a real, addressable place; the hash map grinds the whole key into a single number and jumps to one bucket, so it has no idea that car lies on the road to card.

That flat, N-independent cost sounds like a free lunch. It isn't — you paid for it up front, in bytes. Time to open the children map and count. →

The space bill: prefixes shared, alphabets paid

Here is where most people's intuition about tries is upside down. "It shares prefixes, so it must save memory," the story goes. Let's measure it instead of believing it. I stored 1,600 words that overlap heavily (roots like auto, inter, under crossed with common stems and suffixes) and compared a dict-node trie against a plain Python set of the same strings.

1600 words · 15,600 characters if written out end to end
trie nodes ............ 3,523     # prefix sharing folded 12,078 char-slots away
trie total bytes ...... 676,224   # ≈ 423 bytes / word
set-of-str bytes ...... 212,488   # ≈ 133 bytes / word

Both halves of that are true and both matter. Prefix sharing is real: 15,600 characters collapsed into 3,523 nodes — twelve thousand repeated character-positions simply vanished onto shared paths. And yet the trie weighs three times as much as the set. Why? Because every one of those 3,523 nodes drags a children dict behind it — that 64-plus-byte map from the last section — and 48 more for the node object. You saved on character-slots and then paid it all back, with interest, in per-node overhead. The sharing bought fewer boxes; each box is expensive.

It gets worse in the textbook version. The classic trie doesn't use a dict per node — it uses a fixed array, one slot per possible symbol: 26 for lowercase letters, 256 for bytes. That array is the same size whether the node has one child or twenty-five.

So the trie is heavier and its lookup is no faster in Big-O than a hash. If that were the whole story, no one would build one. But there's a query it answers that a hash map cannot even attempt — and it's the reason you meet tries every single day. →

The superpower: every word beneath a point

Ask a hash map "give me every key that starts with cu." It can't. A hash function deliberately scatters keys so that cup, cur, and cute land in unrelated buckets with nothing between them — the whole design goal is to destroy any relationship between similar keys. To answer the prefix question it would have to scan all N keys and test each one: O(N).

A trie answers it structurally, because it never destroyed the relationship in the first place. Every word starting with cu lives in the subtree hanging below the cu node. So the query is two moves: walk to the prefix node (O(length of the prefix)), then collect every end-flag in the subtree below it. You visit only the words that match — nothing else in the trie is touched.

def starts_with(root, prefix):
    cur = root
    for ch in prefix:                     # 1) walk to the prefix node — O(len prefix)
        cur = cur.children.get(ch)
        if cur is None:
            return []                     # nothing in the trie starts this way
    out = []
    def collect(node, path):              # 2) gather every end-flag below it
        if node.is_end:
            out.append(path)
        for ch, child in node.children.items():
            collect(child, path + ch)
    collect(cur, prefix)
    return out

The first loop is the ordinary descent — reach the node that spells the prefix, or bail if the path dies. The nested collect is a plain tree walk (chapter 8) rooted at that node: whenever it meets an end-flag it records the word built up so far, and it only ever descends links that exist. Run on our small trie, starts_with(root, "ca") returned ['cat', 'car', 'card', 'care'] and starts_with(root, "do") returned ['do', 'dog'] — exactly the words on those paths, gathered without looking at a single unrelated key. On the 1,600-word trie, starts_with(root, "auto") found all 160 matches by touching only the auto subtree.

You've now seen the trie's soul: a prefix is a place. But its Big-O advantage hides a cost the machine charges at runtime that the exponent never shows — the same one every pointer structure pays. →

The pointer tax, one hop per letter

Big-O counts steps; the machine bills by the cache line (Volume 3's memory hierarchy). And a trie is one of the most pointer-heavy structures in this book: every single character of a lookup is a dict probe followed by a jump to a fresh, unrelated heap address — the scattered 0x7f… nodes from the first diagram. The CPU's prefetcher, which makes a contiguous array fly by guessing the next address, is blind here: it cannot predict where the a-link of this node lands. So each letter risks a cache miss and a stall on RAM. Reading a 10-letter word can mean ten dependent misses in a row — each jump's address only known after the previous load returns. The O(L) is honest; the constant hidden inside it is large and set entirely by that scatter.

This is why serious trie implementations rarely look like the teaching version. The first fix is path compression: if a run of nodes each has exactly one child, they carry no branching decision, so merge them into one edge labelled with the whole substring. That's a radix tree (or Patricia trie) — the same structure the Linux kernel uses for IP routing and that databases use for index keys. The second fix is layout: pack the nodes into one contiguous array (a double-array trie) so that following a link is arithmetic into a block the prefetcher loves, not a jump to the unknown. Both attack the constant, not the O — because on this structure the constant is where the pain lives.

You now have the whole trie: a path per word, O(L) reads, a heavy per-node bill, and a prefix superpower no hash can match. The only skill left is the one that matters most — knowing, on sight, when this is the shape to reach for. →

When to reach for a trie

Strip it to the trigger. A trie earns its keep when your keys are sequences — strings, IP addresses, DNA, sequences of moves — and you query them by prefix or by best-match, not just by exact equality. That second clause is the whole decision. If all you ever do is "is this exact key present?" and "give me its value," a hash map is lighter, simpler, and just as fast — use it. The moment the question becomes "what completes this?", "what's the longest stored key that's a prefix of this?", or "iterate everything under this branch in order," the hash map goes quiet and the trie is the answer, because it alone kept prefixes as structure.

That is the 1% move again, and by now it's a refrain across this whole volume: match the access pattern to the layout. The trie's access pattern is unmistakable once you can name it — keys that share heads, questioned by their heads. When a router asks "which of my routes is the longest prefix of this address," when a search box asks "what have people typed that starts like this," when a spell-checker asks "what real words are one edit from this path," they are all asking the same question, and the trie is the same answer: descend by symbol, and let the shared paths do the work. Knowing that on sight — before you write a line — is most of what "good at data structures" means. The code, as always, is the easy part that follows.

Next (chapter 12): a trie is still a tree — one path to every node, no cycles, strictly top-down. Tear off that last rule. Let any node point to any node, let paths loop back on themselves, and the tree opens into the most general shape in this book: the graph, where a friendship, a road map, a web link, and a git history are all the same two sets — nodes and edges — and the only real question left is how you store the tangle. →

12The graph — the structure that models everything

A graph is the most general shape in this whole volume: a set of nodes and a set of edges between them, and almost nothing you care about isn't secretly one — maps, friendships, web links, git history, the tasks a build must run in order. The abstract idea you may already have met (Vol 3 ch13, where BFS and DFS run on it); this chapter builds the thing itself, from memory up. After it you'll be able to look at a real problem, name its nodes and edges, and — the part that separates good from lost — pick the one of two storage layouts that decides whether it fits in RAM at all.

Two sets — and suddenly everything is one shape

The definition is almost insultingly small. A graph is a set of nodes (also called vertices — the things) and a set of edges (connections between pairs of things). That is the whole contract. And because the definition says nothing about what the things are, anything can be a node: a city, a person, a web page, a commit, a chemical, a state of a game. Cities-and-roads, people-and-friendships, pages-and-links, tasks-and-"must-come-before" are not like graphs — they are graphs, same structure, same code.

Edges come in two flavours you'll keep meeting. An undirected edge is a two-way street (Ada ⇄ Bex: if she's your friend, you're hers). A directed edge points one way (page A → page B; "socks before shoes" is not "shoes before socks"). An edge may also carry a weight — a number on the connection: minutes of drive, cost of a flight, strength of a bond. Four words — node, edge, direction, weight — and you can describe a road atlas, a social network, and a compiler's build order in one breath. The vocabulary was Vol 3's job; here we ask the brutally practical question it skipped past: a machine can't store a drawing. It stores bytes. So how does a graph actually sit in RAM?

There are exactly two honest ways to write adjacency down, and they sit at opposite ends of a memory tradeoff. The first spends nothing on connections that don't exist. →

The adjacency list — pay only for the edges that exist

The adjacency list is the layout in the figure above: for each node, keep a list of its neighbours. In Python that's a dict-of-lists — a hash table (Vol 1 ch7) whose values are dynamic arrays (Vol 1 ch6, our chapter d1). To find node 2's neighbours you hash the key 2, land on its slot, and read the list — the neighbours are right there. To store the whole graph you spend one dict entry per node, plus one reference slot for every edge-endpoint. Count it: V nodes and E undirected edges cost V + 2E slots, because each edge is written at both of its ends. That is O(V + E) space — you pay only for connections that are real.

import sys
graph = {                    # a hash table (Vol1) whose values are dynamic arrays
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2],
}
sys.getsizeof(graph)         # -> 224   the dict itself: 4 keys in a hash table
sys.getsizeof(graph[2])      # -> 88    node 2's list: 56-B header + 8 B per ref slot

Line by line: graph is the entire structure — a dict whose four keys are the nodes and whose four values are neighbour lists. getsizeof(graph) returns 224 bytes: that's the hash table's own machinery for four keys (Vol 1's sparse-table overhead), and crucially it does not include the lists — getsizeof measures one object, not what it points at. getsizeof(graph[2]) is 88 bytes: a list's ~56-byte header plus 8 bytes for each neighbour reference (a real run measured a marginal 47 B per undirected edge once list over-allocation is amortised in). The headline: nothing here scales with V²; it scales with the edges you actually have.

So the list is thrifty. Why would anyone ever choose the other layout — the one that reserves a box for every possible connection in the universe? Because it buys something the list can't. →

The adjacency matrix — a box for every possible edge

The adjacency matrix is a V×V grid of 0s and 1s where cell [i][j] = 1 means "there's an edge from i to j." Memory is one-dimensional (Vol 1), so — exactly like the matrix of chapter d7 — this grid is flattened row-major: row 0's V cells, then row 1's V cells, laid end to end, and cell (i, j) lives at base + (i·V + j)·slot. That flat formula is the whole point: to ask "is i linked to j?" the machine does one multiply-add and reads one cell — O(1), no list to scan. The adjacency list makes you walk a neighbour list to answer that (O(degree)); the matrix answers it in a single indexed jump.

The catch is the flip side of the same coin. The grid has V² cells whether or not the edges exist, so it costs O(V²) space always, sparse or not. And in pure Python a "cell" isn't a bit — a list-of-lists stores an 8-byte reference per cell (measured: 8.06 B/cell). A true packed matrix (NumPy uint8, or a stdlib bytearray) drops that to 1 byte, and a bit-packed one to 0.125 B/cell — but even at one bit, V² grows quadratically and swallows the list long before your data does.

Here are the two layouts of the same six-node graph, side by side. Flip the toggle and watch the memory story change: the list writes down only the edges that exist; the matrix reserves all V² boxes the instant you create it.

For six nodes the gap is 20 versus 36 — a shrug. But watch what happens to that gap as the graph grows and stays sparse, the way every real graph does. →

Sparse or dense — the choice that decides whether it fits in RAM

This isn't an academic preference; it's the difference between fitting in memory and not. Real graphs are overwhelmingly sparse: a person has hundreds of friends, not millions; a web page links to dozens of pages, not billions; a road touches a handful of intersections. For sparse graphs, V+2E and V² live in different universes. Take a million users, each with about ten friends, and just count the storage:

V, deg = 1_000_000, 10
E = V * deg // 2            # 5,000,000 undirected edges

cells = V * V              # 1,000,000,000,000   (a trillion)
slots = V + 2 * E          #        11,000,000   (eleven million)
cells // slots             # -> 90909   the matrix is ~90,909x bigger
cells // 8                 # -> 125,000,000,000 bytes = 125 GB  at 1 bit/cell

Line by line: V and deg fix the scale; E halves the endpoint count because each friendship is one shared edge. cells is V² — a trillion boxes. slots is V+2E — eleven million. The ratio is 90,909×. And cells // 8 is the kindest possible matrix — one bit per cell — still 125 GB (≈116 GiB) just to record who-knows-whom. The adjacency list of the same graph is about 88 MB at 8 bytes a slot, or 44 MB packed. One representation needs a data-centre; the other fits in a laptop. Same graph.

Slide the edge count on a fixed 16-node graph and watch the two costs pull apart. The matrix line never moves — it reserved V² up front. The list rises one honest step per edge. They only meet at the far right, where the graph is complete (every pair connected) — the one regime where the matrix's fixed price is finally fair.

You now know which to store. But there's a second, quieter reason the list usually wins that has nothing to do with byte counts — and one clever repacking that makes it win even harder. This is where the metal speaks. →

How the metal feels a graph — pointer-chasing, and the CSR trick

Two structures with the same Big-O can run at wildly different real speeds, because the CPU reads memory in cache lines, not bytes (Vol 3 ch2). A contiguous scan streams — the prefetcher sees the pattern and pulls the next line before you ask. A jump to an unrelated address stalls — the core waits ~100 cycles for RAM. Look back at Fig 1: our dict-of-lists puts every neighbour list at a scattered heap address. Walking node u's neighbours means following a reference off the dict to wherever that list happens to live — a cache miss — and if the neighbour data itself is objects, another miss per element. It's the pointer-chasing of the linked list (d2) wearing a graph's clothes: correct O(V+E), but stall-prone.

Here's the human insight that fixes it — the same "a tree can live in a flat array" move you saw the heap make back in d10. Take the adjacency lists and concatenate them all into one flat array, indices, and keep a second small array, indptr, whose entry i says where node i's neighbours begin. Node i's neighbours are then the contiguous slice indices[indptr[i] : indptr[i+1]]. No dict, no scattered lists — two straight runs of memory. This is CSR (compressed sparse row), and it's how NetworkX-scale libraries, SciPy, and GPU graph engines actually store graphs.

from array import array                 # packed 4-byte ints, not boxed objects
indptr  = array('i', [0])               # where each node's neighbours begin
indices = array('i')                    # every neighbour, concatenated
for u in range(V):
    for nb in adjlist[u]:
        indices.append(nb)
    indptr.append(len(indices))         # ...node u's slice ends here

# node u's neighbours, no dict, no scattered list:
indices[indptr[u] : indptr[u+1]]        # a contiguous slice

Line by line: indptr and indices are array('i') — packed 4-byte integers laid contiguously (d1), not Python objects with 28-byte headers. The loop walks the dict-of-lists once, appending each neighbour to the flat indices and recording the running boundary in indptr. The last line is the payoff: to iterate node u's neighbours you take one contiguous slice — for the 1000-node graph this whole structure measured 28,816 bytes against the dict-of-lists' 308,888, about 11× smaller, and it streams through cache instead of chasing pointers.

Layout settled, the metal appeased — now the reason any of this exists: asking the graph questions. And it turns out you've been living inside the answers all day. →

Asking the graph questions — and where you already live inside one

Once the graph is in memory, every question is a walk over it, and the two fundamental walks were Vol 3 ch13's subject, so a sentence each. BFS — breadth-first — spreads like a ripple in a pond using a queue (d4): it visits everything one hop away, then two, then three, so its first arrival at a node is the shortest unweighted path. DFS — depth-first — plunges down one path to the end using a stack (d3, often the call stack via recursion), backing up only at dead ends; it's the tool for cycles, connectivity, and ordering. Both are O(V + E) precisely because the adjacency list lets each of them "scan every node's neighbour list once" — the structure and the traversal cost are the same fact seen twice. Add weights and BFS's equal-hop assumption breaks; Dijkstra (Vol 3) patches it with a heap (d10).

A graph whose directed edges never loop back is a DAG — a directed acyclic graph — and it's quietly one of the most useful shapes in computing. "Must-happen-before" relations are DAGs, and a DFS over one yields a topological order: a linear sequence respecting every dependency. That single idea is your build system deciding compile order, your package manager installing libraries before the things that need them, and a spreadsheet recalculating cells in the right sequence.

Which brings us to the 1% move. "Good at data structures" is not knowing graph trivia — it's the reflex, on a brand-new problem, to ask "what are the nodes, what are the edges?" and then "do I need every pairwise lookup (matrix) or just each node's neighbours (list)?" Answer those two and half the problem dissolves: the model tells you it's a graph, and the access pattern tells you how to lay it out. The graph is the most general container in this volume because it makes the fewest assumptions — and that generality is exactly why recognising one is the highest-leverage pattern-match you can train.

We can now store any web of relationships and walk it. But one specific question — "are these two nodes in the same connected blob?" — comes up so often, and can be answered so much faster than a fresh traversal each time, that it earned its own razor-sharp structure. Next: Union-Find, a forest of parent-pointers that answers "connected?" in almost constant time. →

13Union-Find — are these two connected?

Some structures store data; this one stores a single relationship — "who is grouped with whom" — and answers two questions about it faster than anything else can: are A and B in the same group? and merge A's group with B's. It's the specialist that closes Volume 3's graph work (ch13): where a fresh BFS re-explores the whole blob every time you ask "connected?", Union-Find remembers. After this chapter you'll be able to build the entire thing in a dozen lines, explain why it runs in effectively constant time, and recognise the surprising number of famous problems that are secretly just "merge groups and ask if two things landed in the same one."

One question, asked a billion times

Picture a set of things — pixels, computers, people, cities — that start out as n separate islands, each in a group of one. Now relationships arrive one at a time: this pixel matches that pixel, this wire connects those two machines, these two people are friends. Each relationship merges two islands into one. And interleaved with the merges, someone keeps asking: are these two particular things now in the same island? That's it. That's the entire job. The formal name for the groups is disjoint sets — a family of sets with no overlap, where every element belongs to exactly one — and the structure that maintains them is the disjoint-set union, or Union-Find after its two operations.

You could answer "connected?" with a graph traversal (d12): store every relationship as an edge, and each time someone asks, run a BFS from A and see if you reach B. But that's O(V+E) per question — you re-walk the whole component every single time, and you throw the answer away when you're done. Union-Find makes a different deal with memory: it doesn't remember how A and B are connected — no path, no route — only that they're in the same group, boiled down to one number. Forget the route, keep the label, and the question that cost a full traversal collapses to comparing two integers.

So each group needs a single label every member agrees on. Where does that label come from, and how does it live in memory? The answer is the cleverest small idea in this volume: a whole forest of trees, folded flat into one integer array. →

The parent array — a forest hiding in a flat array

Here's the trick that makes the label cheap: don't store a label at all — store a parent. Give every element one pointer, up toward the "representative" of its group. Follow those parents and you climb a tree; the element at the very top — the one that points at itself — is the root, and the root's own index is the group's label. Every element in a group climbs to the same root, so "same group?" becomes "same root?". A group is a tree; the whole collection of groups is a forest of these upward-pointing trees.

Now the memory move. A tree usually means scattered heap nodes joined by real pointers — 28-byte object headers, cache-missing pointer-chasing, the whole tax we paid for the linked list (d2) and the graph (d12). Union-Find pays none of it, because the elements are the integers 0..n-1, and an integer can be an index. So the entire forest collapses into one flat array, parent, where parent[i] holds the index of i's parent. No nodes, no heap pointers — the "pointer up the tree" is just a number you use to index back into the same array. A tree, living inside a contiguous block, exactly the way d10's heap folded a tree into an array. The root is any i where parent[i] == i.

import sys
from array import array

n = 1_000_000
parent = list(range(n))          # start: everyone is their own root (n islands)
sys.getsizeof(parent)            # -> 8,000,056   bytes  (8.00 B per element)

parent = array('i', range(n))    # same forest, packed 4-byte ints
sys.getsizeof(parent)            # -> 4,091,948   bytes  (4.09 B per element)

Line by line: the initial state is list(range(n)) — every element is its own parent, so every element is a root and the forest is n single-node trees. As a plain list it's a contiguous array of 8-byte references (Vol 1) — measured 8,000,056 bytes for a million elements, a flat 8.00 B per element. Swap in array('i') and the same information packs into raw 4-byte integers — 4,091,948 bytes, 4.09 B each — because there are no boxed int objects to reference, just the numbers themselves. Either way the cost is O(n), one slot per element, and that's the whole structure: no per-edge storage, no node headers. Union-Find is one of the lightest containers you'll ever meet.

One array, one rule ("roots point at themselves"). From those, both operations fall out almost for free — and one of them has a hidden performance trap that a person had to be clever to escape. →

find and union — follow the parents, repoint a root

Two operations, and the array makes both obvious. find(x) answers "which group?" by climbing: start at x, hop to parent[x], then parent[parent[x]], and keep going until you reach the element that points at itself — the root. Return that root. union(a, b) merges two groups: find a's root, find b's root, and if they differ, set one root's parent to the other. That single write — parent[rootA] = rootB — staples two trees into one, and instantly every element under rootA now climbs to rootB. "Connected?" is just find(a) == find(b).

def find(parent, x):
    while parent[x] != x:        # climb until a self-pointer (the root)
        x = parent[x]
    return x

def union(parent, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra != rb:                 # different groups?
        parent[ra] = rb          # one write staples them together

def connected(parent, a, b):
    return find(parent, a) == find(parent, b)

That's a fully working Union-Find. find is a loop that follows parents until the self-pointer; union calls it twice and, if the roots differ, does one assignment; connected is a one-liner on top. It's correct — but read find again with a suspicious eye. Its cost is the height of the tree: how many parent-hops from x up to the root. Nothing here controls that height. If unions keep stapling roots into a straight line — 0 under 1 under 2 under 3 — the tree becomes a chain of length n, and find degrades to O(n), a linked list wearing a forest's clothes.

Play with it. Click any two circles below to union their groups; the parent-arrows rewire and the parent array updates live. Click two that are already in the same tree and it tells you they were already connected — that's connected() answering without a single merge.

A person stared at that O(n) chain and asked: on the way up to the root, I touch every node on the path anyway — why not fix them while I'm here? That one thought is worth a 19,000× speedup. →

Path compression — flatten the trail on the way up

Here's the first great optimization, and it's almost embarrassingly cheap. When find(x) climbs to the root, it walks past every node on the path from x upward. Those nodes now know who the root is. So on the way back, re-point every one of them straight at the root. The next time you call find on any of them, it's one hop. You did the walk anyway; flattening the path is free work that permanently shortens the tree. This is path compression, and it turns a tall spindly tree into a flat bush after a single query.

def find(parent, x):
    root = x
    while parent[root] != root:      # pass 1: climb to the root
        root = parent[root]
    while parent[x] != root:         # pass 2: bend every node on the path to root
        parent[x], x = root, parent[x]
    return root

Pass one finds the root as before. Pass two walks the same path a second time and rewrites each node's parent to be the root directly — the tuple assignment saves the old parent before overwriting it so the walk can continue. Two cheap passes instead of one, and the tree collapses. The payoff, measured on that same 200,000-node chain: the first compressed find still pays O(n) to climb (about 10 ms, one time), but it flattens everything, so every subsequent find of that node drops to about 0.20 µs — versus 3,793 µs naive. That's roughly a 19,000× speedup per query, and it came from noticing you were already standing on those nodes.

Watch it happen. Below is a deliberately tall chain, 5 hanging under 4 under 3 … under root 0. Press find(5) and the path folds flat — every node on it re-points directly at 0. The hop-count for a future find(5) drops from 5 to 1.

Compression fixes trees after they grow tall. But there's a second, complementary idea that stops them growing tall in the first place — and it's just as simple. →

Union by size — never hang the big tree off the small one

The second optimization attacks the problem at union time. When you merge two trees, you choose which root becomes the child of the other — and that choice decides the new height. Attach the bigger tree's root on top and hang the smaller under it, and the combined tree stays as short as possible; do it backwards and you risk stacking height on height. Keep a size array (how many elements each root owns) and always point the smaller root at the larger. This is union by size (its cousin, union by rank, tracks tree height instead — same spirit). Alone, it guarantees no tree is ever taller than O(log n), because a tree can only get taller when two equal-size trees merge, and that can happen at most log₂n times on the way from 1 to n.

def union(parent, size, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb:
        return
    if size[ra] < size[rb]:          # ensure ra is the LARGER root
        ra, rb = rb, ra
    parent[rb] = ra                  # small tree hangs under big root
    size[ra] += size[rb]             # big root absorbs the count

The extra machinery is one comparison and one addition. If ra's tree is smaller, swap the labels so ra is always the bigger root; then hang rb under ra and fold the sizes together. The cost is one more n-length array (the size counts), doubling the structure's footprint to about 8 B/element as two packed int arrays — still gloriously light. And now, crucially, height never exceeds log n on its own.

Union by size caps height at log n; compression crushes it further toward 1. Put them together and the per-operation cost sinks to a number so small it has a famous, almost unbelievable name. →

α(n) — the cost that never reaches 5

With both optimizations, a Union-Find operation runs in O(α(n)) amortized time, where α is the inverse Ackermann function. The Ackermann function A(m,n) is the standard example of something that grows faster than any tower of exponentials — it explodes so violently that its inverse crawls upward almost imperceptibly. How slowly? α(n) stays ≤ 4 for every n up to a number with roughly 19,729 digits. The observable universe has about 10⁸⁰ atoms — an 81-digit number. So for any Union-Find you will ever build — indeed for any that could physically exist — α(n) is a small constant no bigger than 4. It is not literally O(1), but the gap is philosophical, not practical.

The proof is in a stopwatch. Here's a full Union-Find with both tricks, run on a million elements, counting the real parent-hops per operation:

# n = 1,000,000 elements, 1,000,000 random unions, both optimizations on
avg_parent_hops_per_find  = 1.11     # after all unions, averaged over n finds
amortized_hops_per_union  = 1.34     # total climbs / total unions across the run

# the same worst-case chain of 200,000 nodes:
naive_find_deepest        = 3793.0   # microseconds, O(n)
compressed_find_after     = 0.20     # microseconds, effectively O(1)
speedup_per_find          = 18965    # times faster

These are measured, not quoted. After a million random unions on a million elements, an average find climbs just 1.11 parent-hops to reach its root — and that number barely budged (it was 1.11 at n=100,000 too), which is exactly what "independent of n" looks like in the wild. The amortized cost across a whole run is about 1.34 hops per union. And on the pathological chain, compression turns a 3,793 µs climb into a 0.20 µs one — the ~19,000× we promised. (Timings are machine-dependent — yours will differ in absolute terms; the ratio and the flatness are the structural facts.)

And the 1% move, the transferable one: "good at data structures" is mostly matching a structure to an access pattern on sight. When you see a problem that's incremental merging plus "same group?" queries — and only that, no paths, no members, no deletions — the reflex should fire: this is Union-Find. Recognising it saves you from reaching for a heavyweight graph and re-traversing forever. The skill isn't memorising α(n); it's feeling the shape of "merge and ask" and knowing there's a near-free tool built for exactly it.

Thirteen structures down — arrays, lists, stacks, queues, deques, hash maps, matrices, trees, BSTs, heaps, tries, graphs, and this connectivity specialist. Each was the right answer to one access pattern. The last chapter steps back and turns that whole collection into a single decision: given a new problem, how do you pick the right container on sight? Next: the chooser's map — matching the operation you do most to the structure that makes it cheap. →

14The decision map — pick the right structure on sight

Thirteen structures, thirteen chapters, one skill. This capstone doesn't add a fourteenth container — it teaches you to choose among the thirteen you already have, on sight, the way a doctor reads a chart. We'll put all of them on a single master table, draw the decision flowchart that turns an access pattern into a structure, and then throw the table away — because the real move isn't memorising it, it's deriving it from one question. After this you'll look at a fresh problem, name the operation you do most, and know which layout makes that operation free. Then we close the series: from a single bit in Volume 1 to the containers that organise a program's whole world.

Every 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. Every chapter was the same deal signed differently. The array (d1) 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 (d6) 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 (d10) folded a tree into a flat array so the minimum sits at index 0. Union-Find (d13), which 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. →

The 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 from d1, 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. →

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

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

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

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