Data structures explained
Every program keeps data somewhere, and how it keeps it decides what is quick and what is slow. A list of a million names can be searched one by one, or arranged so that twenty comparisons find any name. Data structures are those arrangements: a handful of ideas, most of them older than the personal computer, that sit inside every database, operating system, browser and game.
What a data structure is for
A data structure is chosen for the questions it has to answer. A phone's call log needs the latest call first, a printer's jobs the oldest first, a dictionary the meaning of one word among a hundred thousand, a route planner the nearest unvisited crossing. Each structure makes some operations fast by giving up others, and big-O notation describes the trade: O(1) means the time does not grow with the number of items n, O(log n) that doubling n adds one more step, and O(n) that the time grows in proportion to n.
Stacks, queues and deques
A stack adds and removes at the same end: last in, first out. Undo histories, the back button and the calls of a running program are stacks. A queue adds at the back and removes at the front: first in, first out, like keyboard input or a print queue. A deque allows both at both ends. All three take constant time per operation. A queue is often kept in a circular buffer, a fixed array in which the front and back wrap around the end; when it fills up, the items are copied into an array twice the size. Copying costs O(n), but it happens so rarely that each operation still costs O(1) on average, which is called an amortized bound.
Linked lists
A linked list stores each value in a node with a pointer to the next node. Inserting or deleting only rewires a pointer or two, with nothing to shift, but there is no way to jump to the tenth node: you follow the links from the head. A list that keeps only its head reaches the tail in O(n) steps; real lists usually keep a tail pointer too, and doubly linked lists a pointer back, which is how a browser history or an LRU cache is built.
Binary search trees
A binary search tree keeps, at every node, smaller values in the left subtree and larger ones in the right. A search compares and goes left or right, and an in-order traversal reads the values in sorted order. Deleting a leaf just removes it, a node with one child is replaced by that child, and a node with two children is replaced by its in-order successor, the smallest value in its right subtree. All of this takes time proportional to the height of the tree: about log n when the tree is bushy, but n when values arrive in sorted order and the tree degenerates into a list.
AVL and red-black trees
Self-balancing trees repair their shape after every change. An AVL tree, invented by Adelson-Velsky and Landis in 1962, keeps the heights of the two subtrees of every node within one of each other; when the balance factor of a node reaches ±2, one rotation (the LL and RR cases) or two (LR and RL) restore it. A red-black tree colours its nodes so that the root is black, no red node has a red child and every path down passes the same number of black nodes, which keeps the longest path at most twice the shortest. It fixes itself by recolouring and at most a few rotations, and it is the tree inside Java's TreeMap, C++'s std::map and the Linux scheduler.
Heaps and priority queues
A binary heap is a complete binary tree stored in an array without any pointers: the children of position i sit at 2i + 1 and 2i + 2. In a min-heap every parent is at most as large as its children, so the smallest value is always at the root. A new value goes at the end and sifts up past larger parents; extracting the root moves the last value to the top and sifts it down. Both take O(log n), and a whole array can be turned into a heap in O(n). Heaps run priority queues in Dijkstra's shortest paths, event simulations and operating system schedulers, and they give heap sort.
Hash tables
A hash table turns a key into an array index with a hash function and goes there directly. Different keys can land on the same index, a collision. Chaining keeps a small list in each bucket; open addressing, such as linear probing, tries the next slots until it finds a free one and must leave a tombstone when a key is deleted, so that later searches keep probing. With a good hash function and a load factor (keys per bucket) kept low by growing the table, insert, search and delete take O(1) on average. A poor function, like adding the character codes of a word, sends anagrams to the same bucket. Hash tables are behind Python's dict, JavaScript objects and database indexes.
Tries and union-find
A trie, or prefix tree, stores strings one character per level, so words with a common beginning share a path and a node marks where a word ends. Finding a word of length L takes L steps however many words are stored, and every word with a given prefix sits in one subtree, which is how autocomplete and spell checkers work. Union-find keeps elements in disjoint sets, each a tree whose root names the set. Find follows the parent links to the root; union hangs one root under another. With union by rank and path compression, a long run of operations costs almost constant time each, the inverse Ackermann function α(n), which is at most 4 for any realistic n. Kruskal's minimum spanning tree algorithm relies on it.
Frequently asked questions
What is the difference between an array and a linked list?
An array keeps its items side by side in memory, so any position can be reached at once, but inserting in the middle means shifting everything after it. A linked list can insert anywhere by changing pointers, but reaching a position means walking from the head. Arrays also use the processor's cache far better, which is why they are usually faster in practice.
What does amortized time mean?
The average cost per operation over a long sequence, even if a single operation is sometimes expensive. A circular buffer that doubles when full copies all n items once in a while, but because the copies get rarer as the buffer grows, n additions cost O(n) in total, so O(1) each on average.
Is a heap the same as a binary search tree?
No. A binary search tree orders every left subtree before its node and every right subtree after it, so it can list all values in order and find any value quickly. A heap only promises that each parent comes before its children, which is enough to find the minimum or maximum at once but not to search for an arbitrary value.
How does union-find know whether two elements are connected?
It follows the parent links from each element up to the root of its tree. If both arrive at the same root, they are in the same set. Path compression then points every node on the way straight at the root, so the next question about them takes a single step.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Open the data structure visualizer