48What a data structure really is

In Volume 3 we learned to count the work an algorithm does. We could stare at a loop and know how its cost grows. Now we turn to the thing that cost is really made of: the data structure. There are thirteen structures ahead of us, and they're all carved from one idea. A structure is two things welded together. First, a way of arranging data in memory. Second, the set of operations that arrangement makes cheap. That's the whole subject. And the whole way through, we keep asking the one question that decides everything: where do the bytes physically sit, and what does that force each operation to cost? By the end you'll be able to pick up any structure and size it up fast. It might be one you've used for years, or one you meet cold on page 200. Either way you ask the three questions that 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.

01A data structure is a deal you strike with memory

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

To make the deal concrete, you have to see the arrangement in memory. Remember from Volume 1: RAM is one enormous row of numbered boxes, each holding a byte, each with an address. A value never floats 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 that points at the next. Same three songs; two completely different deals with memory.

Look at what the picture already tells you, before a single line of code. In the array, item #3 sits 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've no choice but to walk the chain. Two arrangements of identical data, and one made "jump to position k" instant while the other made it a walk. That gap isn't a Python quirk. It's forced by where the bytes physically sit.

Let's put real numbers on that leap, because the whole chapter turns on it. Say the array's first slot lives at address 1000, and each slot holds one 8-byte reference. Then item #1 is at 1000, item #2 at 1008, and item #3 at 1000 + 2×8 = 1016. Notice what you did to reach item #3. You multiplied once and added once, and it didn't matter whether you wanted item #3 or item #3000. The same two-step calculation lands you on any slot. The linked chain can't do this, because its nodes sit at addresses that have no pattern. There's nothing to compute, so you follow pointers one by one until you arrive.

Now put the same kind of number on the walk, so the contrast is exact. Suppose you want node #500 in the linked chain. The only route is through the 499 pointers ahead of it, so you make 500 hops to arrive. Want node #3000 instead? That's 3000 hops, and there is no shortcut to skip them. The array reached any slot with one multiply and one add, a fixed two steps, while the chain's cost is the position itself. That is the difference between O(1) and O(n), written in hops you can count.

import time

rows  = [(f"user{i}", i * 7) for i in range(10_000)]   # 10,000 rows, arranged two ways
index = dict(rows)                                     # the SAME rows, keyed by name
wanted = [f"user{i}" for i in range(0, 10_000, 5)]     # the SAME 2,000 lookups

t = time.perf_counter()
a = [next(v for k, v in rows if k == name) for name in wanted]   # scan for the name
scan = time.perf_counter() - t

t = time.perf_counter()
b = [index[name] for name in wanted]                             # hash the name to a slot
keyed = time.perf_counter() - t

print("identical answers:", a == b)
print(f"list of rows : {scan*1000:9.2f} ms")
print(f"dict         : {keyed*1000:9.2f} ms")
print(f"same 2,000 lookups: {scan/keyed:,.0f}x apart")

identical answers: True
list of rows :    226.24 ms
dict         :      0.13 ms
same 2,000 lookups: 1,691x apart

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

02Memory 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. Writing x = song doesn't copy the song. It stores the song's address, and that address is 8 bytes because this is a 64-bit machine. Two: every Python object carries a header before its actual data. The header is a reference count and a pointer to its type, roughly 16 bytes of pure bookkeeping on top of whatever it holds. Three: objects live scattered on the heap. The things that organize them, like lists and 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 yourself. sys.getsizeof reports an object's byte cost, and the numbers come back 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. 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, but 8 bytes, the size of one reference. The list stores addresses, and 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.

Where does that 28 for an int come from? It's worth breaking open, because it's the same header you'll meet on every object. 16 of those bytes are the header we just named: 8 for the reference count and 8 for the pointer to its type. That leaves 12 bytes, and those hold the integer's actual value plus a small record of how many digits it needs. Add them up: 16 + 12 = 28. So even a plain number is mostly bookkeeping, with the value tucked in at the end. That's the tax Python pays to make every object self-describing, and it's exactly why a list of numbers stores 8-byte addresses instead of the numbers themselves.

Here's the test that proves the point. Put the number 5 and the number 10**100 — a googol, 101 digits long — into the same list. The googol is a far heavier object out on the heap, yet each one costs the list the same 8 bytes, because the list only ever stores the address of a value, never the value itself. Swap a tiny int for that monster and the list's own size doesn't move a byte. That is what "a list of 8-byte references" really means, and it's why sys.getsizeof on the list stays flat while the objects it points at vary wildly in size.

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 even 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 its slots in batches rather than 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 the very next chapter on the array takes it apart bolt by bolt.

Those jumps aren't random, and the arithmetic tells the story. Empty, the list is 56 bytes with zero slots. The first append pushes it to 88, and (88 − 56) / 8 = 4 — it grabbed room for four references at once, not one. It then holds at 88 through the next three appends, spending slots it already owns. When it fills, it leaps to 120, another four slots, then to 184, which is eight more (184 − 120 = 64, and 64 / 8 = 8). Each time it runs out, it roughly doubles the spare room. So appends feel free on average: you pay for a big batch once, then coast.

So why does doubling make appends average out to cheap? Follow the copies. Growing a full list of n items means allocating a bigger block and copying those n across, which is real work, O(n) for that single append. But it only happens when the list doubles: at sizes 1, 2, 4, 8, and so on. Add up every copy you'll ever pay across n appends and it comes to n + n/2 + n/4 + … ≈ 2n, which is about two copies per append. A rare big cost, spread thin over many cheap ones, lands at amortized O(1). That is exactly what the word amortized is doing.

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

03The 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 just three of them: push (add to the top), pop (remove the top), and peek (look at the top). It also swears the last thing in is the first thing out, and that's the whole promise. Notice that the contract says nothing about memory. The implementation is the arrangement that actually keeps that promise. You can back a stack with a contiguous array or with scattered linked nodes: same contract, but different pictures in RAM. And here's the whole point — those different pictures mean 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 →

04We 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. 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.

Access was one operation of the four. Insert and delete are where the two layouts really trade places, so let's derive them the same way. To insert at the front of a contiguous array, every existing item has to shift up one slot to make room, so the cost grows with the count: O(n). The linked chain does the opposite. To splice a new node in at the front, you point it at the old head and move the head, and nothing else budges: O(1). Delete flips the same way. The array closes the gap by shifting everything back down, while the chain just re-points one pointer. So neither layout wins outright. The array is fast to reach into and slow to reshape, and the chain is exactly the reverse.

That leaves the fifth thing we grade: space. Line the two layouts up for n items and the numbers fall out. The contiguous array is a block of n references, so its slots cost 8n bytes and nothing more. The linked chain stores the same n references, but each one now lives inside a node that also holds a next pointer, another 8 bytes. So every element carries 16 bytes of structure instead of 8, and the chain spends roughly double the memory to buy its cheap front-insert. Nothing here is free — the pointer you follow is a pointer you also paid to store.

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, which is O(n). Asking the same of a set instead means computing x's hash into an address and looking in exactly one spot, which is O(1). Different arrangement — a sparse hash table from the set/dict internals in Volume 1 — asks the same identical question and gets a radically different cost. Timed on this machine:

How does a key "become an address"? Here's the move in miniature, with small numbers to make it checkable. Say the set has 8 slots, and you ask whether the number 91 is present. Python runs 91 through a hash function and then folds the result down to a slot with %, the remainder operator. Take the simplest case, where the hash of 91 is just 91: then 91 % 8 = 3, because 8 goes into 91 eleven times with 3 left over. So the set looks only in slot 3. It doesn't scan slots 0, 1, 2, and onward. It computes the one address that could hold 91 and checks that single spot. That's why the size of the set barely changes the cost. The answer is a calculation, not a search.

One fair question before we move on: what if two numbers want the same slot? Ask for 99 in that same 8-slot set, and 99 % 8 = 3 too, because 8 goes into 99 twelve times with 3 left over — the very slot 91 wanted. That's a collision, and the set handles it by checking slot 3, seeing the wrong value there, and stepping to the next slot until it finds the number or hits an empty gap. The trick that keeps this fast is keeping the table sparse: Python grows it well before it fills, so those little walks stay a step or two long, and the lookup is still O(1) on average.

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, and only the arrangement differs. The membership test reads identically in code (target in …), so the contract is the same, yet the list must walk its slots while the set jumps to a hashed address. The stopwatch reports the difference bluntly: about half a millisecond versus about fifty nanoseconds, which is roughly eleven thousand times faster. The exact ratio is machine-dependent, but the shape, O(n) versus O(1), is not. You didn't write smarter code here — you picked a smarter arrangement, and 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 →

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

Why exactly elements 1 through 7, and not 1 through 20? Do the division. A cache line is 64 bytes, and each reference in the array is 8 bytes, so one line holds 64 / 8 = 8 references. Reach for element 0 and the hardware hauls in that whole 64-byte line, which is elements 0 through 7 in one trip. The next seven reads are already sitting in fast memory, paid for. That's the free ride a contiguous layout buys you. The scattered chain gets none of it, because its next node is off at some unrelated address that the line you just loaded almost certainly doesn't cover.

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. 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 the matrix and heap chapters.

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? That question gave us the hash table. 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. That gave us the heap, the fast thing it is today. 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 →

06The one skill: match the access pattern to the layout

Everything so far collapses into a single move. You have a problem, and 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? That's KEYED, the hash map. Always need the smallest or largest next? That's HIERARCHY, the heap, a tree in an array. Data that's a grid of rows and columns? That's GRID, the matrix. Things defined by their connections? That's NETWORK, the graph. Five families, five access patterns, and the thirteen structures are all variations within them.

Try the move once, on something real. Say you're counting how often each word appears in a book, and the operation you do millions of times is this: take a word, find its running count, add one. That's a lookup by a key, the word, done over and over, so the map points you straight at KEYED, and you reach for a dict mapping each word to its count. You didn't weigh thirteen structures against each other — you just named the dominant operation and let it choose. That's the skill working exactly as advertised.

INPUTimport timeit
n = 100_000
# drain 100,000 items from the FRONT -- same job, two tools
tl = min(timeit.repeat("while L: L.pop(0)",
         setup=f"L = list(range({n}))", number=1, repeat=5))
td = min(timeit.repeat("while D: D.popleft()",
         setup=f"from collections import deque; D = deque(range({n}))",
         number=1, repeat=5))
print(f"list.pop(0)     x{n:,}: {tl*1000:8.1f} ms")
print(f"deque.popleft() x{n:,}: {td*1000:8.1f} ms")
print(f"same job, one import apart: {tl/td:.0f}x")

OUTPUTlist.pop(0)     x100,000:   3005.3 ms
deque.popleft() x100,000:     10.3 ms
same job, one import apart: 291x

One honest edge, so you don't over-trust the map. Real problems often have two hot operations that pull toward different families. When that happens you either compose structures, like a dict of lists or a heap beside a hash map, or you 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.

import random, time
from collections import Counter

class Pool:
    """insert, delete, random_one -- all O(1), by letting a list and a dict
       hold each other's missing half."""
    def __init__(self):
        self.items = []                     # dense block: index k is one address away
        self.where = {}                     # value -> its index inside items

    def insert(self, x):
        if x in self.where:
            return False
        self.where[x] = len(self.items)     # the newcomer lands on the end
        self.items.append(x)
        return True

    def delete(self, x):
        i = self.where.pop(x)               # the dict knows WHERE -- no scan
        last = self.items.pop()             # the tail is the only slot free to lose
        if i < len(self.items):             # x wasn't the tail: move last into the hole
            self.items[i] = last
            self.where[last] = i            # and tell the dict where last went
        return True

    def random_one(self):
        return self.items[random.randrange(len(self.items))]


K = 100_000                                 # the SAME op counts at both sizes
def price(n):
    p = Pool()
    for x in range(n): p.insert(x)
    newcomers, doomed = range(n, n + K), random.sample(range(n), K)
    t = time.perf_counter()
    for x in newcomers: p.insert(x)
    ins = (time.perf_counter() - t) / K * 1e9
    t = time.perf_counter()
    for _ in range(K): p.random_one()
    rnd = (time.perf_counter() - t) / K * 1e9
    t = time.perf_counter()
    for x in doomed: p.delete(x)
    return ins, rnd, (time.perf_counter() - t) / K * 1e9

def list_delete(n, k=1_000):                # what the first instinct charges
    L, doomed = list(range(n)), random.sample(range(n), k)
    t = time.perf_counter()
    for x in doomed: L.remove(x)            # find it (scan), then close the gap (shift)
    return (time.perf_counter() - t) / k * 1e9

small, big = price(100_000), price(1_000_000)
ls, lb = list_delete(100_000), list_delete(1_000_000)
for n, (i, r, d) in (("100,000", small), ("1,000,000", big)):
    print(f"pool  n={n:<11} insert {i:4.0f} ns | random {r:4.0f} ns | delete {d:4.0f} ns")
print(f"list  n=100,000     delete {ls:>12,.0f} ns   (scan, then shift)")
print(f"list  n=1,000,000   delete {lb:>12,.0f} ns   (scan, then shift)")
print(f"10x the data ->  pool delete x{big[2]/small[2]:.1f}  |  list delete x{lb/ls:.1f}"
      f"  |  pool is {lb/big[2]:,.0f}x cheaper")

p = Pool()                                  # and the swap must not bias the draw
for c in "ABCDEF": p.insert(c)
p.delete("B"); p.insert("B")                # force the swap-with-the-tail shuffle
print("600,000 draws from 6:", sorted(Counter(p.random_one() for _ in range(600_000)).items()))

pool  n=100,000     insert  151 ns | random  369 ns | delete  224 ns
pool  n=1,000,000   insert  133 ns | random  499 ns | delete  540 ns
list  n=100,000     delete      402,533 ns   (scan, then shift)
list  n=1,000,000   delete   11,185,804 ns   (scan, then shift)
10x the data ->  pool delete x2.4  |  list delete x27.8  |  pool is 20,715x cheaper
600,000 draws from 6: [('A', 100126), ('B', 99986), ('C', 99882), ('D', 99996), ('E', 100055), ('F', 99955)]

import heapq

# 1 LEADERBOARD - dominant op: "who is top right now?"  -> heapq (HIERARCHY)
#   heap[0] is the smallest, so push -score and the top scorer is always slot 0.
board = []
for name, score in [("ana", 40), ("bo", 91), ("cy", 77)]:
    heapq.heappush(board, (-score, name))          # O(log n) per arrival
print("1 leader:", board[0][1], -board[0][0], " peek O(1), push O(log n)")

# 2 SPELL-CHECK - dominant op: "is this word in the dictionary?" -> set (KEYED)
words = {"cat", "hat", "the", "quick"}             # hashed: the word IS the address
print("2 in set:", "hat" in words, "| 'hta'", "hta" in words, " membership O(1)")

# 3 UNDO HISTORY - dominant op: "take back the most recent thing" -> list as a stack
undo = []
undo.append("draw line"); undo.append("fill red")  # push O(1)
print("3 undo  :", undo.pop(), "-> left", undo, " push/pop at the END, O(1)")

# 4 VIDEO FRAMES - dominant op: index by frame number, scan in order -> list (LINEAR)
frames = [f"f{i}" for i in range(5)]               # built once, never spliced
print("4 frame :", frames[3], "| in order", frames[:3], " index O(1), append O(1)")

# 1 leader: bo 91  peek O(1), push O(log n)
# 2 in set: True | 'hta' False  membership O(1)
# 3 undo  : fill red -> left ['draw line']  push/pop at the END, O(1)
# 4 frame : f3 | in order ['f0', 'f1', 'f2']  index O(1), append O(1)

# AND WHAT EACH ONE COST YOU -- the half people skip:
# 1  heap: h[0] is instant, but the full ranking is NOT in there. A heap is
#    ordered, not sorted; asking for 2nd place costs a pop, or an nlargest.
# 2  set: membership is instant, and order plus duplicates are gone forever.
#    "the 5th word in the dictionary" is a question a set cannot answer.
# 3  stack: the top is instant, and everything under it is unreachable
#    without popping. Searching an undo history is a full O(n) walk.
# 4  list: index and in-order scan are instant, and inserting a frame in the
#    MIDDLE shifts every frame after it -- O(n). Dashcams never do that.

Enough framework. Time to build. The next chapter 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. →