Start here: the problem it solves#
TL;DRthe 30-second version
- A skip list is a sorted linked list with extra levels on top. Each node gets a tower of forward pointers, and coin flips decide how tall the tower is.
- Search starts at the top left. Move right while the next key is smaller than the target, and drop a level when it would overshoot. That gives expected O(log n).
- Insert and delete run the same search, then splice or unlink one tower. No rotations, no rebalancing, so the code is short and easy to make lock-free.
- It powers Redis sorted sets, the LevelDB/RocksDB memtable, and Java's ConcurrentSkipListMap. The bound is expected, not a hard worst case.
A sorted linked list is easy to insert into. But searching it is O(n), because you walk one node at a time and can't jump ahead. A sorted array fixes search with binary search, but then every insert shifts elements, which is O(n) again. Neither plain structure gives you fast ordered search and fast updates at the same time.
The textbook answer is a balanced binary search tree, red-black or AVL. It guarantees O(log n) search, insert, and delete. The catch is the machinery that keeps it balanced: rotations, recoloring, and case analysis that are fiddly to get right. Those rotations also move pointers far from the point of change. That makes the tree hard to update from several threads without a coarse lock.
The mechanism: stacked lists and coin-flip towers#
Picture several linked lists stacked on top of each other. The bottom level holds every node in sorted order. Each level above holds a sparse subset of the level below. Those are the express lanes. Every node carries a tower of forward pointers, one per level it reaches.
Heights come from coin flips, not from position. When you insert a node, it always sits at level 0. Flip a coin: heads, and it also joins level 1. Flip again for level 2, and so on until the first tails. With a fair coin, about half the nodes reach level 1, a quarter reach level 2, an eighth reach level 3. The upper lanes become a coarse index over the lanes below.
skim right while the next key is smaller than 30, then drop a level
A search starts at the head on the highest level. Move right while the next key is smaller than the target. When the next key would overshoot, drop down one level and keep going from the same node. When you fall off the bottom of level 0, the next node is either the target or something larger, which means the key is absent. Each high-level hop skips many base nodes at once, so the path stays short.
Insert and delete start with this same search. Along the way, record the predecessor at each level. Then splice the new tower in at those points, or unlink the old one. No other node moves, and a node's height never changes after it is inserted.
The numbers at p = 1/2: about log2(n) levels, about 2 forward pointers per node on average, and about 2·log2(n) steps per search.
PredictYou search for a key near the end of a 1,000,000-key skip list. Roughly how many nodes does the search visit, and why isn't it about 1,000,000?
Hint: How many levels are there, and how much does each express-lane hop skip?
About 40, not a million. At p = 1/2 the list has about log2(1,000,000) ≈ 20 levels, and the expected work is about 2·log2(n) ≈ 40 steps. Each high-level hop skips all the lower-level nodes between two express stops, so the search only walks node by node in the last short stretch near the target.
If this comes up in an interview#
Why use randomness instead of a balanced tree?
Same asymptotics, far less code. A skip list reaches O(log n) without the rotations and case analysis a red-black or AVL tree needs. Updates are local pointer splices, so it is much easier to make concurrent, even lock-free. The price is a probabilistic bound instead of a deterministic one.
Is the O(log n) guaranteed?
No. It is expected, and it holds with high probability. With terrible luck every coin lands tails, every node stays at level 0, and search degrades to O(n). But the chance of degrading by any constant factor falls off exponentially in n, so a large list effectively never misbehaves. The randomness is internal, so no key ordering can force the worst case.
Why p = 1/2, and why does Redis use 1/4?
At p = 1/2 the height is a single coin flip per level, with about 2 pointers per node and about 2·log2(n) search steps. Redis uses p = 1/4 to cut pointers to about 1.33 per node. That saves memory when a server holds millions of sorted-set members, at the cost of slightly longer walks per level.
How does a lock-free skip list delete safely?
In two phases. One compare-and-swap marks the node as logically deleted, so it becomes absent in a single atomic step. Physical unlinking from each level then happens lazily, and any thread that trips over a marked node helps finish it. Readers never see a half-removed node. Java's ConcurrentSkipListMap works this way.
When to reach for one
| Skip list | Balanced BST (red-black) | B-tree | Hash table | |
|---|---|---|---|---|
| Search / insert / delete | O(log n) expected | O(log n) worst case | O(log n) worst case | O(1) average |
| Ordered ops (range, rank, min/max) | Yes | Yes | Yes | No |
| Worst-case guarantee | Probabilistic | Deterministic | Deterministic | Probabilistic (O(n) on collisions) |
| Implementation | Simple, no rotations | Fiddly rotations/recoloring | Complex splits/merges | Simple |
| Concurrency | Easy, local CAS, lock-free exists | Hard, rotations touch far nodes | Hard, splits lock subtrees | Moderate, bucket locks |
| Memory locality | Poor, scattered towers | Poor, scattered nodes | Excellent, packed pages | Good, contiguous buckets |
| Best home | In-memory ordered + concurrent | In-memory ordered, strict bound | On-disk ordered indexes | Unordered key lookup |
Read it as: hash tables win when you don't need order. B-trees win on disk because of fan-out and page locality, which is why databases index on disk with B-trees, not skip lists. Balanced trees win when you need a hard bound in memory. Skip lists win for ordered, in-memory work with simple code that is easy to make concurrent.
Pugh's original motivation was not speed. A skip list and a balanced tree have the same asymptotics. It was that the skip list is far easier to implement, reason about, and parallelize.
Variants worth knowing
- Indexable skip lists store a span count on each forward pointer: how many base nodes it jumps. Summing spans along the search path gives a key's rank in O(log n). Redis ZRANK uses exactly this.
- Deterministic (1-2-3) skip lists replace the coin flips with a balance rule, giving a guaranteed O(log n) worst case at the cost of more bookkeeping. They are the skip-list analogue of a 2-3-4 tree.
- Concurrent, lock-free skip lists map the local pointer splices onto compare-and-swap. Java's ConcurrentSkipListMap is the standard example.
References
- William Pugh — Skip Lists: A Probabilistic Alternative to Balanced Trees (CACM, 1990) — the original paper: the structure, the search, and the expected-O(log n) analysis
- Java — ConcurrentSkipListMap (JDK API docs) — the standard-library lock-free concurrent sorted map
- Redis source — t_zset.c (skip list implementation) — real ZSKIPLIST with spans and back pointers; ZSKIPLIST_P = 0.25
- LevelDB source — skiplist.h (memtable skip list) — the in-memory write buffer that fronts the LSM tree