Type three letters into your phone's contacts and the list narrows before your thumb lifts. Your contacts are probably a few hundred names, so that is no miracle. But the same trick works when the list is a billion long: a web search, a map lookup, a spell checker that underlines a word the instant you finish typing it. Nothing in your phone got a billion times faster. The data was arranged so that the answer does not require looking at everything.
That is the whole subject. A program is two things: the steps it takes, and the way it keeps its information. Change the second and the first often shrinks from "check every item" to "check a handful". A computer science graduate looks at any problem and asks, almost without noticing, what operations will I do most, and what shape of storage makes those cheap?
Who takes it: every computer science major in the first or second year, and many engineering, maths and data science students.
What it is for: learning the handful of standard containers every program is built from, and what each one is fast and slow at.
Comes after: Programming Fundamentals (34/09).
Leads to: Algorithms (34/24), Operating Systems (34/26), Databases (34/28), Programming Languages & Compilers (34/30).
What this piece gives you: you will not be able to implement a red-black tree from memory afterwards. You will see why a database index is a tree, why a dictionary lookup does not slow down as it grows, and which container to reach for first.
Arrays and linked lists: one street, two ways to number it
Memory is a very long street of numbered mailboxes. An array reserves a row of neighbouring boxes and stores one item per box. To find item number 500,000 you do arithmetic: start address plus 500,000 times the size of one item, and walk straight there. A linked list scatters its items anywhere, and each item carries a note saying where the next one lives. To reach item 500,000 you must read 500,000 notes in order.
Worked number: a million 4-byte integers. Insert one at the front of the array and all 1,000,000 must slide along one box. In the list it is a single new node pointing at the old head. Now read the middle one: the array jumps there in one step, the list takes 500,000 hops.
With one million items: reading the middle takes 1 step in an array and 500,000 hops in a list; inserting at the front takes 1,000,000 shifts in an array and 1 relink in a list.
Assumes a list with only a head pointer, and 4-byte items on 64-byte cache lines. The bar lengths use a log scale.
The last button hides the twist. Reading every item is the same number of steps either way, yet the array wins in practice. A processor does not fetch one box from memory; it fetches a whole cache line, commonly 64 bytes, which is sixteen of those integers at once. An array's neighbours arrive for free. A list's next node may sit in some unrelated line, so each hop can be a fresh trip. For a million integers that is about 62,500 trips against up to 1,000,000. This is why programmers who know the theory still reach for arrays first.
Stacks and queues: restricting yourself on purpose
A stack and a queue are not new storage. They are an array or list with a rule about the doors. A stack has one door: the last thing in is the first thing out, like plates in a cafeteria. A queue has two: you join at the back and leave from the front, so first in is first out.
Why would anyone give up freedom? Because the restriction is the meaning. Your program's function calls form a stack: when f calls g, g must finish before f resumes. The undo button is a stack. A printer's job list, a web server's waiting requests and the order a breadth-first search visits places are queues.
Whether (a[b]{c}) is balanced is a stack problem: push each opener; each closer must match the one on top. Pick a text and step through.
Without scripts: in (a[b]{c}) each closer meets its own opener on top of the stack, so it is balanced. In (a[b)] the closer ) meets [ on top, so it is not.
Add A, B, C to both. Taking one out gives C from the stack (newest) and A from the queue (oldest).
Hash tables: why lookup does not depend on size
Suppose you want to find "maple" among a million words without scanning. The idea: do not search, compute where it must be. A hash function chews the word into a number, and the number modulo the table size picks a bucket. Looking it up later repeats the same arithmetic and goes straight to that bucket. The cost is the arithmetic, which does not care whether the table holds a hundred words or a hundred million.
The catch is that different words can land in the same bucket: a collision. They are unavoidable, and surprisingly early. Drop 23 keys into 365 buckets at random and the chance that at least two share one is already 50.7%, which is the birthday paradox. The usual fix is chaining: each bucket holds a short list of everything that landed there. Another, open addressing, steps to the next free bucket.
Hash: start at 0; for each letter, multiply by 31 and add the letter's code; take the remainder after dividing by the number of buckets. Add words and drag the bucket count.
Example: the first eight words (maple, river, stone, cloud, tiger, piano, lemon, bridge) in 8 buckets put maple, stone and cloud in one bucket, piano and bridge in another, and leave 3 buckets empty. In 32 buckets the longest chain is 2.
Add eight words to eight buckets, then slide the bucket count up. Chains shrink and most lookups need a single glance. That trade, spending memory to buy speed, is the hash table in one sentence. It is also why Python's dict, JavaScript's objects and Maps, and the "dictionary" or "map" in nearly every language are hash tables inside.
Trees: sorted order you can search in a few hops
Hash tables are quick but forget order. Ask one for "the next word after maple" and it cannot say. A binary search tree keeps order. Each node holds a key; everything smaller hangs off its left side, everything larger off its right. To find a key, compare with the root, go left or right, repeat. Every comparison discards a whole branch, usually about half the remaining keys.
That last sentence is the trap. Insert 1, 2, 3, ... 15 in order into a plain tree and every new key is larger than all before it, so it goes right, and right, and right. The "tree" is a linked list leaning sideways, 15 levels deep. Fifteen keys inserted in a smart order (8, 4, 12, ...) give height 4.
In order, 1 to 15 makes a tree of height 15. The balanced order makes height 4, the minimum. Fifteen shuffled keys average height about 7 (from a simulation of 20,000 shuffles; the tallest seen was 12).
Now press the self-balancing button and insert 1 to 15 in order again. The height is 4. An AVL tree (named for its inventors, Adelson-Velsky and Landis, 1962) checks after each insertion whether one side has grown two levels taller than the other, and if so performs a rotation: a local re-hanging of three nodes that keeps the sorted order but shortens the tall side. Red-black trees, the kind inside many standard libraries, use a different bookkeeping for the same promise. B-trees, which have hundreds of children per node so that one disk read does a lot of narrowing, are what most database indexes and file systems use. The principle is constant: keep the height logarithmic, and search stays fast however big the data grows.
Heaps: the cheapest way to always know the biggest
Sometimes you do not need everything sorted, only the next most urgent thing: the next patient, the next road to explore, the next event in a simulation. That is a priority queue, and the standard way to build one is a heap. A heap is a tree with one rule only: every parent is smaller than its children (a min-heap). The smallest item is therefore always at the top, readable in 1 step. Nothing else is ordered.
The trick that makes it neat: a heap can be packed into a plain array. The children of position i sit at 2i+1 and 2i+2, with no pointers at all. Insert by adding at the end and letting the new item float up past any larger parent. Remove the smallest by taking the root, moving the last item to the top and letting it sink. Each trip is at most the height of the tree.
Starting from 42, 17, 63, 9, 88, 25, 51 inserted one by one, 9 ends up at the root. Removing it moves 51 to the top, which sinks 2 levels.
Graphs: when everything connects to everything
Roads, friendships, web links and flight routes are not lists or trees: items connect to many others and loops are normal. That shape is a graph: dots (vertices) and links (edges). (The library's Graph Theory: From Königsberg to Your GPS is an easier first read on the maths; here the question is storage.)
Two standard ways to store one. An adjacency matrix is a grid with one cell for every pair of vertices, marked if they are linked. Checking "are A and B linked?" is 1 step. An adjacency list gives each vertex a short list of only its actual neighbours. "Who are A's neighbours?" is quick, and nothing is stored for links that do not exist.
Worked number: a road network of one million intersections, each joining about 3 roads. The matrix needs a trillion cells, 125 gigabytes even at one bit each. The list needs about 4 million entries.
One million vertices with 3 links each: a matrix has 1,000,000,000,000 cells (125 GB at one bit each); an adjacency list has 4,000,000 entries.
Choosing: start from the operations
There is no best structure, only the best one for the operations you do most. Programmers pick by asking questions in this order: do I look things up by key? Do I need them in order? Do I always want the biggest or most urgent? Is the data links between things? Costs below are for n items, typical case.
| Structure | Strong at | Weak at |
|---|---|---|
| Array | Read by position, scan in order (1 step; cache-friendly) | Insert or delete in the middle (~n) |
| Linked list | Insert or delete at a known spot (1) | Read by position (~n); poor cache use |
| Stack / queue | Newest-first or oldest-first handling (1) | Anything else |
| Hash table | Find by exact key (1 on average) | Order; worst case ~n |
| Balanced tree | Find, insert, ordered range (~log n) | Slightly slower than hashing for exact keys |
| Heap | Peek at the minimum (1), insert and remove (~log n) | Searching for an arbitrary item |
| Graph | Connections: routes, networks | Needs algorithms (see 34/24) |
The choice often matters more than tuning code. Checking each of a million customers against a banned list of a million names, held as an array, takes about half a trillion comparisons on average. Make the banned list a hash table and it is a million lookups.
What a graduate just sees
- Memory is a street of numbered boxes; every structure is a policy for using it.
- Arithmetic on an address (arrays, hashing) beats following notes (lists, trees).
- Neighbours in memory are cheap: the cache makes arrays faster than their step counts suggest.
- A hash table spends memory to buy near-constant lookup, and collisions are a certainty.
- A tree's speed lives in its height, so the real question is whether it stays balanced.
- Heaps know the extreme, not the order, and that is why they are cheap.
- Real graphs are sparse, so store the links that exist.
- Ask "which operations?" before "which structure?".
Where it shows up next
- Algorithms (34/24) is the other half: an algorithm's speed is mostly the structure it runs on. Dijkstra's shortest path is a graph plus a heap.
- Databases (34/28): an index is a B-tree, and a "hash join" is a hash table.
- Operating Systems (34/26): process schedulers are priority queues, and the call stack is a literal stack.
- Compilers (34/30): your source code becomes a tree, and a compiler's symbol table is a hash table.
- In the world: your phone's contacts, a game's pathfinding, the autocomplete on a search box, and every "undo".
If you want to go deeper
- 📘 Textbook: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (MIT Press, 4th ed., 2022): the standard reference, deep and rigorous, with data structures in Part III.
- 📘 Textbook: Sedgewick and Wayne, Algorithms (4th ed., Addison-Wesley): code-first, with a companion site.
- 🌐 Free and gentle: Pat Morin, Open Data Structures (opendatastructures.org), free under a Creative Commons licence, with Java, C++ and pseudocode editions.
- 🌐 Free course: Harvard CS50x (cs50.harvard.edu/x) covers arrays, linked lists, hash tables and trees in Week 5, free; MIT OpenCourseWare 6.006 Introduction to Algorithms goes further.
Data structures are policies for arranging memory, and each is fast at some operations and slow at others. Arrays give direct access, lists give cheap insertion, hash tables give near-constant lookup, balanced trees give ordered search in logarithmic steps, heaps give the extreme at once, and graphs hold connections. Pick by the operations you will do most.
Try this: next time an app finds something instantly in a huge list, guess what structure sits behind it: hash for "exact", tree for "starts with" or "between", heap for "top ten". Then, in the tree demo above, find the order of inserts that keeps the plain tree at height 4 without turning on balancing.
Sources. Textbook material: Cormen et al., Introduction to Algorithms, 4th ed.; Sedgewick and Wayne, Algorithms. Hashing first described by Hans Peter Luhn in an IBM memo of January 1953 (Wikipedia, "Hash table"). AVL trees: Adelson-Velsky and Landis, 1962 (Wikipedia, "AVL tree"). The 64-byte cache line is typical of current x86 processors; some chips use other sizes. The step counts and simulations in the demos were computed in code.
Go deeper.
- 📘 Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein (MIT Press, 2022)
- 🌐 Open Data Structures (free)
- 🌐 Harvard CS50x (free)
- 🌐 MIT OpenCourseWare 6.006, Introduction to Algorithms (free)