A search walks a sorted linked list: compare the first key, then the next, then the next. Correct, and linear. A million sorted items can require half a million comparisons to find one value.
The list is ordered, but the search cannot use that order. It has a pointer to the next node and nothing else.
A skip list hands it the missing tool: some nodes get express lanes.
Take the bottom row as an ordinary sorted linked list: 3 to 7, 7 to 12, 12 to 19. Add a second row above whose links skip several nodes at a time, and a third above that which skips further.
The search changes shape. Start on the top row, move right while the next key is smaller than the target, and drop a level when moving right would overshoot. Right, right, down. Right, down. The structure is still a linked list, but the search path traces something close to a balanced tree.
That is a skip list: a sorted linked list with extra forward pointers layered above it. The taller a node, the further it lets later searches skip.
The towers are chosen by coin flip. There is no rotation, no recoloring, no split. Each item enters on level 0; heads promotes it one level, and it keeps flipping until tails. Randomness builds the hierarchy that a balanced tree maintains by bookkeeping.
William Pugh published “Skip Lists: A Probabilistic Alternative to Balanced Trees” in 1989. The title states the claim.
Balanced trees deliver good search times through case analysis: rotations, parent pointers, color invariants, height differences, rebalancing after every insert and delete. Pugh’s argument was that probabilistic balance gives the same expected performance from code that fits in your head.
The problem is sorted search under mutation. Arrays support binary search, but inserting in the middle shifts everything after it. Linked lists support cheap insertion once you know the position; finding the position is linear.
Balanced trees solve both and pay for it in invariants. A skip list keeps the linked list’s insertion and adds just enough height to avoid the linear walk. It does not guarantee a tree’s shape — only that random levels are good enough, with high probability.
Each node holds a key, possibly a value, and an array of forward pointers. Level 0 holds every node. Level 1 holds about half of them, level 2 about a quarter, level 3 about an eighth.
A sentinel head node sits at the far left with a pointer on every level. It carries no key; it is where searches start. From there a search moves right along the highest level until the next key would be too large, then drops a level and repeats.
Search for 42. Start at the head’s top pointer. If the next node’s key is less than 42, follow the link. If it is greater, drop a level. If it equals 42, the search is done.
Every move preserves order. Moving right never passes the target, because the move only happens while the next key is still smaller. Dropping down never loses ground, because the lower level contains everything the upper level skipped. On reaching level 0 you are either at the target or immediately before it.
To insert 42, run the same search — but record the last node visited on each level before dropping. That record is the splice map: the nodes whose forward pointers may need to change.
Then flip coins for 42’s height. If the coins grant levels 0, 1, and 2, the new node gets three forward pointers. On each of those levels, point 42 at whatever the recorded node pointed at, then point the recorded node at 42. It is the linked-list insert you already know, repeated once per level.
With promotion probability one half, about half the nodes reach level 1, a quarter reach level 2, an eighth reach level 3. The tallest tower among n nodes is around log₂ n.
No rebalance step enforces that distribution; it emerges one insert at a time. Bad luck is possible, and long runs of bad luck are exponentially unlikely. The structure is balanced the way a large number of coin flips is balanced: not exactly, but tightly enough to build on.
Search, insert, and delete each take expected O(log n). The search path drops one level at a time, and there are logarithmically many levels. At each level, the expected number of rightward hops before dropping is constant.
That constant is what makes the bound hold. An upper level could in principle force a long horizontal run, but the promotion probability keeps runs short on average. The result is tree-like time from a structure that never rotates anything.
The trade is not correctness. A skip list answers exactly: if a key is present, search finds it; if the search falls off the end of level 0, the key is absent.
The trade is certainty about performance. A balanced tree guarantees logarithmic height by construction. A skip list achieves it with high probability. In exchange it offers simpler code, workable concurrent variants, ordered iteration, and range scans.
Deletion is the splice in reverse. Search for the key, recording the predecessor on each level. If the key exists, walk its tower and bypass it wherever it appears: point each predecessor at the node’s next pointer on that level.
Nothing ripples upward, and no sibling cases arise. When the top levels empty out, the list can lower its current maximum height. The shape repairs itself by removing links rather than reorganizing subtrees.
Two knobs. The first is the promotion probability p. The classic choice is p = 1/2, halving the population at each level. Some implementations use p = 1/4, which reduces pointers and improves cache behaviour at the cost of more horizontal movement.
The second is the maximum level, fixed in advance from an expected capacity. For millions or billions of items, a few dozen levels makes the probability of needing more negligible.
Every node pays for one pointer on level 0, then buys each higher pointer only while the coin keeps coming up heads. With p = 1/2 the expected number of forward pointers per node is two.
So: two pointers per item, logarithmic search, insertion by splicing. Against a balanced tree, a skip list usually spends more pointer memory and less implementation complexity. Which of those is scarce depends on the machine and the workload, which is why engineers keep both.
An indexable skip list stores a span with each forward pointer: how many level-0 nodes that pointer skips over.
With spans, the list answers rank queries — find the 10,000th element, count the keys below x, page through a sorted set by offset. Redis uses this for sorted sets, pairing a hash table for direct lookup with a skip list for ordered traversal and rank.
Skip lists suit concurrent systems because their updates are local. Inserting or deleting a tower touches a small set of predecessor links. No root rotation changes the shape of a subtree out from under a concurrent reader.
That does not make lock-free code easy, but it makes it tractable. Fraser’s work on practical lock freedom and Java’s ConcurrentSkipListMap rest on the same property: the structure is updated through ordered pointer changes, not rebalancing.
In storage engines a skip list often serves as the memtable: the mutable, in-memory sorted structure that accepts writes before they are flushed to disk.
LevelDB does exactly this. Writes append to a log and enter the memtable; reads search it; flushes iterate it in key order to produce an immutable file. That is precisely what an LSM tree wants from its write buffer — fast inserts, ordered scans, and code that stays small under pressure.
Skip lists beat balanced trees on implementation simplicity and often on concurrency. Trees win where worst-case guarantees matter, or where compact nodes and cache-friendly B-tree pages matter more.
Neither replaces the other. What skip lists demonstrate is that balance can be a statistical property: instead of repairing the structure after every operation, arrange the probabilities so that it rarely needs repair.
Redis sorted sets. LevelDB memtables. Java’s concurrent navigable maps. In-memory indexes, priority queues, event schedulers.
The common requirement is not raw speed. It is that a single structure supply exact lookup, ordered iteration, range queries, and local updates at once. A skip list supplies all four without a rebalancing routine.
The search path does not branch left and right. It glides: right while safe, down when the next step would overshoot, until level 0 gives the answer.
The randomness is not decoration. It is what lets the express lanes exist without a planner deciding where they go. Each insert builds one private tower, and the skyline they form is good enough for logarithmic travel.
A sorted linked list, plus forward pointers chosen by coin flip. No rotations, no recoloring, no height invariant. Expected O(log n) for search, insert, and delete; two pointers per node; a worst case that is possible and improbable.
The balance is never repaired because it is never allowed to drift far. Sampling does the work that maintenance does elsewhere.