48What a data structure really is

In Volume 3 we learned to count the work an algorithm does — to look at a loop and know how its cost grows. Now we turn to the thing that cost is really made of: the data structure. Before the thirteen structures ahead of us, there's one idea they all share. A 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. And all the 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 — one you've used for years, or one you meet cold on page 200 — and 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 have 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 field, and notice 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 it a number and ask whose it is, and the same book becomes painful — you'd have to read every line. Same data. Same paper. The arrangement — sorted by name — made one question instant and left the other nearly impossible. That trade is the whole 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'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 long 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" really means deciding which addresses hold what, and how the pieces find each other. Take three songs and store them two ways. You can pack them into one contiguous block — slot after slot, no gaps. Or you can 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 have no choice but to walk the chain. Two arrangements of identical data: one made "jump to position k" instant, the other made it a walk. That gap isn't 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 →

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. 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 around; the things that organize them, like lists and dicts, are just other objects holding references to them. So 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. 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; 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 comes up 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. It keeps 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.

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

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, 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 good part 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 no matter what k is. 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 follows 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 — the set/dict internals from Volume 1), 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 straight to a hashed address, and the stopwatch reports the difference plainly: about half a millisecond versus about fifty nanoseconds. That's roughly eleven thousand times faster. (The exact ratio depends on the machine, but the shape — O(n) versus O(1) — does not.) You didn't write smarter code. You picked a smarter arrangement. That is the whole 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.

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

None of these arrangements appeared on their own — a person had to see them, and 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's how 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 those 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. 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. 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. When that happens, 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. 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. →