Data structures,
from zero to fluent.

Imagine a phone book with a million names in it, and someone asks for "Zimmerman." If the names were in random order, you would have no choice but to read from the first page and keep going until you found it, potentially a million comparisons. Because the names are sorted, you flip to the middle, see you have gone too far or not far enough, and throw away half the book in a single glance. Twenty flips settles a million names.

Nothing changed about the data. The names are the same names. What changed is the arrangement, and the arrangement decided whether the job took twenty steps or a million. That is the entire subject in one sentence.

A sorted array supports binary search: halve the search space with each comparison. An unsorted pile supports only linear search: check every element until you get lucky. The model below runs both, for real, on the same array. Pick a target and watch how many comparisons each strategy actually makes.

To compare structures we need a way to talk about cost that does not depend on the laptop, the language, or the day. Counting seconds fails all three. So instead we count how the number of basic steps grows as the input grows, and we keep only the part that dominates when the input gets large. That is Big-O notation.

Picture a birthday party. Doubling the guest list does not change how long the oven takes to preheat: flat cost, no matter how many people show up. It does double how long it takes to plate everyone's food: linear cost, one unit of work per guest. But if you insist on introducing every guest to every other guest, the introductions do not double, they quadruple: quadratic cost. How a cost reacts to more input is exactly what Big-O is built to describe.

Why drop the constants? Because growth rate wins every race eventually. An O(n²) method that is cleverly optimized still loses to a sloppy O(n) method once n is big enough, and "big enough" is usually smaller than you would guess. The comparator below plots the five classes you will meet over and over. Drag n and read the actual operation counts: watch the gap between the flat lines and the quadratic one explode.

The counts on the right are computed, not drawn: log₂n rounded up, n, n·log₂n, and n². At n = 64, constant time is 1 operation and quadratic time is 4096. That factor of four thousand is the difference between instant and unusable, and it is the reason a professional's first question about any operation is "what is its Big-O?"

There are two fundamentally different ways to store a sequence, and almost every structure ahead is built from one of them. The choice comes down to a single question: are the elements sitting next to each other in memory, or are they scattered and stitched together with pointers?

An array is a parking garage with numbered spaces: knowing the number sends you straight to spot 42, no searching required. A linked list is more like a treasure hunt, where each clue only tells you where the next clue is, so reaching the 42nd clue means finding all 41 before it.

An array is one contiguous block. Element i lives at base + i × size, so the computer jumps straight to any index with one multiply and one add. That is O(1) random access, and it is arrays' superpower. The cost: to insert in the middle, everything after it must shuffle over to make room.

A linked list stores each element in its own node, and each node holds a pointer to the next. The nodes can live anywhere. To reach index i you must start at the head and follow i pointers, one hop at a time: that is O(n) access. The payoff: once you are holding a node, splicing a new one in is O(1) pointer surgery, no shuffling.

Ask the model for a given index under both layouts and count the memory touches. The array lands in one step every time. The list walks.

Arrays have one awkward feature: their size is fixed when you make them. But the lists you actually use (a Python list, a Java ArrayList, a C++ vector, a JavaScript array) grow on demand. How? They wrap a fixed array and, when it fills up, allocate a bigger one and copy everything over.

The clever part is how much bigger. If you grew by one slot each time, every single append would copy the whole thing: that is O(n) per append and O(n²) to build a list. Instead, dynamic arrays double the capacity when full. Doubling is the difference between a disaster and one of the most-used structures in computing.

Here is why doubling works. To reach size n, the resizes copy 1 + 2 + 4 + … + n/2 elements, which sums to less than n. Add the n placements themselves and total work is under 2n: a constant per append. Press the button and watch it: most appends cost one unit, and every so often a tall rose spike marks a resize. The amber line is the running average cost, and it stays flat and low no matter how far you go.

Think of a linked list as a train: each car is coupled only to the next one. Adding a new car at the front is one coupling, and nothing else in the train has to move. But reaching the tenth car means walking the couplings from the front, one at a time.

A linked list is the pointer-spine sequence from Chapter 3, made concrete. Each node holds a value and at least one pointer. In a singly linked list every node points only to the next; in a doubly linked list each node also points back to the previous, so you can walk in both directions and delete a node you are standing on without hunting for its predecessor.

The reason to reach for a linked list is cheap splicing. Inserting at the head is pure pointer work: make the new node point at the old head, then move the head pointer. No element ever moves in memory. The model animates the surgery: watch the pointers rewire as you insert and delete.

A stack is the most disciplined structure there is: you may only add to the top, and only remove from the top. Last in, first out (LIFO), like a stack of plates. That single restriction is exactly what you want for anything that nests: function calls, undo history, matching brackets, the back button, depth-first search.

The call stack your program runs on is literally this: each function call pushes a frame, each return pops one. Push and pop touch only the top, so both are O(1). Drive it below and watch LIFO order fall out: the last thing you push is the first thing that comes back.

Flip the stack's rule and you get a queue: add at the back, remove from the front. First in, first out (FIFO), like a line at a counter. Queues model anything served in arrival order: print jobs, task schedulers, request pipelines, breadth-first search.

The naive way to build one on an array is to dequeue by removing element 0 and shifting everything left, which is O(n) every time. The professional way is a ring buffer: a fixed array with two indices, head and tail, that wrap around modulo the capacity. Nothing shifts. Enqueue writes at tail and advances it; dequeue reads at head and advances it; both wrap to 0 when they run off the end. Both operations become O(1).

Everything so far has been about arranging data so you can find things. Hashing is the idea that gets you the holy grail: finding a value in constant time on average, no matter how many values there are. The trick is to compute where something should live directly from the value itself.

A hash function takes a key of any size (a string, say) and grinds it into a fixed-size integer. Good hash functions have two properties: they are deterministic (the same key always produces the same number) and they spread keys evenly (small changes in the key scatter the output). To turn that big number into an array index, take it modulo the table size.

Think of a valet who has to find your car in a giant lot. A valet who just remembers every car as it arrives has to scan the whole lot looking for yours. A smarter valet computes your spot from your license plate the moment you hand over the keys, then walks straight to it. That calculation, an address computed from the content itself, is what a hash function does.

The model runs exactly that polynomial hash (the one Java's String.hashCode uses). Type a key and watch the integer accumulate character by character, then collapse to a bucket index. Type the same key twice and you land in the same bucket every time: that determinism is what makes lookup possible.

Picture a wall of PO boxes. Your key decides which box your mail goes into. Two different keys can land on the same box, a collision, and there are two ways to handle it: chaining stuffs both people's mail into that one box, open addressing walks down the row and hands the second person the next open box instead.

A hash table is an array of buckets plus a hash function that says which bucket a key belongs in. Insert, look up, and delete all compute the bucket in O(1) and go straight there. This is the structure behind Python's dict, JavaScript's Map and objects, database indexes, and caches everywhere.

The complication is collisions: two different keys can hash to the same bucket. There are two classic fixes. Chaining stores a little linked list in each bucket and appends colliders. Open addressing (linear probing) keeps one item per slot and, on a collision, walks to the next empty slot. Toggle between them below and watch collisions resolve two different ways.

Insert keys one at a time. The collision counter ticks when a key lands on an occupied bucket, and when the load factor crosses 0.75 the whole table doubles and rehashes. That resize is why average-case lookup stays O(1): a bounded load factor means the average chain is a constant length, no matter how many keys you store.

Hash tables are unbeatable for exact lookup, but they scatter keys into buckets in no useful order. The moment you need sorted order, ranges ("all names between H and P"), or the next-largest key, you want a tree. The workhorse is the binary search tree (BST).

Think of the number-guessing game: I am thinking of a number between 1 and 100, you guess and I tell you higher or lower. You would not guess 3, then 4, then 5. You would guess 50, then 25 or 75, cutting the range in half every time. A binary search tree bakes that exact strategy into how it stores data.

The ordering rule is the whole trick. To search, start at the root and compare: smaller goes left, larger goes right. Each comparison discards an entire subtree, exactly like binary search on the phone book, except the structure is explicit and stays cheap to update. Insert follows the same path and hangs the new node where the walk falls off. Reading the tree left-to-right (an in-order traversal) always yields sorted keys.

Drive the real tree below. Search animates the path down and lands on the answer in amber; insert and delete restructure it live.

A BST's operations cost O(height), and the previous chapter quietly assumed height is about log n. That is only true if the tree stays balanced. Feed a plain BST keys that are already sorted and something ugly happens: every new key is larger than the last, so it hangs off the right side, and the tree degenerates into a linked list of height n. Search is back to O(n). All the cleverness is gone.

The model proves it. Insert 15 keys in sorted order and the height is 14, a straight diagonal. Insert the same 15 keys shuffled and the height collapses toward log₂15 ≈ 4, a bushy tree. Same keys, same structure, wildly different shape and cost, decided entirely by insertion order.

This is why production code rarely uses a plain BST. Self-balancing trees (AVL trees, red-black trees) do a little extra pointer rotation on each insert to guarantee the height stays O(log n) no matter what order keys arrive in. B-trees extend the same idea to wide, shallow trees tuned for disk and are what SQL databases and filesystems index with. The balancing details differ, but the mission is identical: never let the tree become a list.

Sometimes you do not need everything sorted, you just need the most urgent thing next, over and over: the shortest task, the closest point, the highest-priority packet. That is a priority queue, and the structure that implements it beautifully is the binary heap.

Two operations keep the heap property. Insert drops the new value at the end of the array and sifts it up, swapping with its parent while it is smaller. Extract-min removes the root, moves the last element to the top, and sifts it down, swapping with its smaller child until order is restored. Each is O(log n) because the tree is only log n tall. The model shows both the tree and its backing array, and extract-min repeatedly gives you a perfectly sorted sequence.

Trees are a special case of the most general structure of all: the graph, a set of vertices connected by edges. Roads between cities, friendships in a social network, links between web pages, dependencies between build steps: all graphs. A tree is just a graph with no cycles and a single path between any two nodes.

There are two ways to store the edges, and the choice drives everything. An adjacency matrix is a V × V grid where cell (i,j) is 1 if an edge exists. Checking "is there an edge from i to j?" is instant, but it always costs V² memory even if the graph is nearly empty. An adjacency list stores, for each vertex, a list of its neighbors: memory is V + 2E (each undirected edge listed twice), which is tiny for the sparse graphs that dominate the real world.

The model also runs breadth-first search (BFS), which explores a graph level by level using the queue from Chapter 7. From the start vertex it visits all neighbors, then all their unvisited neighbors, and so on, giving the shortest path in edges. BFS is the bridge from data structures to graph algorithms: once you can store a graph, the queue and the stack unlock traversal, shortest paths, connectivity, and much more.

Some data has structure a hash table throws away. Words share prefixes: "car," "card," and "care" all begin with "car." A trie (prefix tree) exploits that. Instead of storing whole keys, it stores one character per edge, so every shared prefix is stored exactly once and each word is a path from the root.

The payoff is prefix queries. "Give me every word starting with 'ca'" is just: walk to the "ca" node, then collect everything below it. That is how autocomplete, spell-checkers, IP routing tables, and search suggestions work. Insert words below and search by full word or by prefix; the walk animates character by character.

You now have the whole toolbox. Fluency is not memorizing every structure, it is matching the structure to the operations you will actually perform. The question is never "what is the best data structure?" It is "what do I do to this data most often, and which layout makes that cheap?"

Here is the cost map for the operations that decide most choices. Colors run from cheap through logarithmic and linear to quadratic-ish, so you can read the trade-offs at a glance.

* amortized. † average case; worst case O(n). ‡ extract-min only. L is key length.

The decision, distilled

• Index by position, iterate a lot? Dynamic array.
• Constant splicing at the ends or a known node? Linked list.
• Strict nesting (LIFO) or arrival order (FIFO)? Stack or queue.
• Exact-match lookup by key, order irrelevant? Hash table.
• Need sorted order, ranges, or nearest key? Balanced BST.
• Always want the most extreme element next? Heap.
• Prefix queries over strings? Trie.
• Arbitrary relationships between things? Graph.

Data structures are the nouns of computing. The natural next step is the verbs: algorithms that act on them. You are already primed for it, because half of algorithm design is picking the right structure.

• Sorting: mergesort and quicksort (O(n log n)), and how heaps give heapsort. The array is the stage.
• Graph algorithms: Dijkstra and A* (a heap plus a graph), topological sort, minimum spanning trees, union-find.
• Dynamic programming: turning exponential recursion into polynomial tables, memoized with arrays and hash maps.
• Balanced trees in depth: red-black trees, B-trees, and the log-structured merge trees inside modern databases.
• Probabilistic structures: Bloom filters, skip lists, and HyperLogLog, where a little randomness buys huge memory savings.

The canonical text is Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms. For a gentler, code-first route, Sedgewick and Wayne's Algorithms pairs well with everything here. But the fastest way to make these permanent is to implement each structure once, from scratch, and watch it run. You just did that fourteen times.