Skip Lists Explained: A Probabilistic Alternative to Balanced Trees
A sorted linked list is easy to write and easy to reason about, but searching it means walking every node until you find the target: O(n). Skip lists keep that simplicity while getting search down to expected O(log n), by layering shortcut lanes on top of the sorted base list and deciding each node's height with a coin flip.
Published July 6, 2026The Problem: Fast Search Without Rebalancing
Balanced binary search trees (AVL, red-black) get O(log n) search, insert, and delete by keeping the tree's height bounded, but they do it through rotation logic that is notoriously easy to get subtly wrong, and that logic gets substantially harder again once you need the structure to be safely modified by multiple threads at once. A sorted array gives fast binary search but O(n) insertion because of shifting. A plain sorted linked list gives O(1) insertion at a known position but O(n) search, since you cannot binary search a structure you can only walk one node at a time.
William Pugh introduced skip lists in 1990 as a way to get expected logarithmic time for all three operations using randomization instead of the deterministic rebalancing that trees require.
How the Layers Work
- Bottom layer, level 0: A standard sorted singly linked list containing every element. This is the ground truth — every other layer is a shortcut on top of it.
- Higher layers: Each layer above level 0 contains a subset of the elements below it, still in sorted order, acting as an "express lane" that lets a search skip over many elements at once.
- Random level assignment: When a new element is inserted, its height is chosen randomly — commonly by flipping a coin repeatedly and stopping at the first tails, so a node reaches level k with probability roughly (1/2)k. This means about half of all nodes exist only at level 0, a quarter also reach level 1, an eighth reach level 2, and so on, without the structure ever needing to look at the rest of the list to decide.
Searching a Skip List
Start at the topmost, sparsest layer at the leftmost node. At each step, look at the next node on the current layer: if its key is less than or equal to the target, move right; otherwise, drop down one layer and repeat from the current node. This continues until you reach level 0, where the search either lands on the target or on the position just before where it would be inserted. Because each layer has roughly half as many nodes as the one below it, this walk touches an expected O(log n) nodes total — the same bound a balanced tree gives, achieved here purely through the probability of how nodes were promoted to higher layers rather than through any invariant the structure has to actively maintain.
Insertion follows the same downward path to find where the new node belongs at each layer it participates in, splicing it into the linked lists at those layers. Deletion is the mirror image: find the node at every layer it appears on and unlink it. Neither operation requires the rotations or rebalancing a tree needs, because there is no height invariant to restore — the random level assignment already handles balance in expectation.
Why Systems Choose Skip Lists Over Trees
Beyond simpler code, skip lists have a practical advantage for concurrent access: because insertion and deletion only ever touch pointers at the specific layers a node participates in, and do not require rotating or restructuring nodes elsewhere in the tree, it is comparatively easier to design a lock-free or fine-grained-locking version of a skip list than of a balanced tree. That property is a large part of why skip lists show up in production systems that need concurrent sorted access.
| System | How It Uses Skip Lists |
|---|---|
| Redis | The sorted set (ZSET) type is backed by a skip list combined with a hash table, giving fast score-ordered range queries and O(1) key lookup together |
| LevelDB and RocksDB | The in-memory memtable that buffers recent writes before they are flushed to disk is implemented as a skip list, chosen partly for its concurrent-read-friendly structure |
| Java's ConcurrentSkipListMap | Provides a lock-free, sorted, concurrent map in the standard library, built directly on the skip list design |
Conclusion
Skip lists are a reminder that randomization can substitute for careful bookkeeping and still deliver the same expected performance guarantees. Instead of a tree's invariant-preserving rotations, a skip list leans on the statistics of repeated coin flips to keep the express lanes sparse enough to be useful and dense enough to be fast. That trade — simpler code and easier concurrency in exchange for expected rather than guaranteed bounds — has been enough to make skip lists the backing structure for sorted sets and memtables in some of the most widely deployed storage systems in use today.
Pugh's original paper, "Skip Lists: A Probabilistic Alternative to Balanced Trees," lays out the full expected-time analysis and is short enough to read in one sitting if you want the proof behind the O(log n) claim.