The Skip List

A linked list can keep a million keys in order and still take half a million comparisons to find one. The ordering is there, but each node only knows its immediate neighbour.

A skip list adds the missing shortcut: a few nodes get links that jump much farther ahead.

Picture an ordinary sorted list on the bottom row. Above it, add a sparser row whose links skip several nodes, then another row with longer jumps.

Search from the top. Move right while it is safe; drop down when the next jump would overshoot. The structure remains a linked list, but the route through it starts to resemble a balanced tree.

A skip list is that stack of linked lanes. Taller nodes provide longer shortcuts for later searches.

Coin flips decide each tower’s height. Every item joins level 0; heads promotes it, and flipping continues until tails. Randomness creates the hierarchy that a balanced tree maintains with rotations and other bookkeeping.

William Pugh introduced skip lists in the 1989 paper “Skip Lists: A Probabilistic Alternative to Balanced Trees.”

Balanced trees use rotations and structural invariants to maintain logarithmic height. Skip lists use randomly selected node heights to provide the same expected asymptotic performance with simpler update logic.

Arrays support binary search but require shifting elements for middle insertions. Linked lists support constant-time insertion once the position is known, but locating that position is linear.

Balanced trees address both operations with structural invariants. A skip list instead uses random node heights to provide fast expected search and localized updates.

Each node stores a key, perhaps a value, and one or more forward pointers. Every node appears at level 0; roughly half reach level 1, a quarter reach level 2, and an eighth reach level 3.

A keyless sentinel at the far left has a pointer on every level. Searches begin there, moving right on the highest useful lane and dropping whenever the next key would be too large.

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 a promotion probability of one half, approximately half the nodes reach level 1, one quarter reach level 2, and one eighth reach level 3. The expected maximum height among n nodes is proportional to log₂ n.

The distribution develops independently across insertions. Unbalanced outcomes are possible, but their probability decreases exponentially with their severity.

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.

A skip list’s answers are exact: it either finds the key or proves it absent at level 0. The probability applies to performance, not correctness.

A balanced tree guarantees logarithmic height by construction; a skip list achieves it with high probability. In return, it offers simpler code, practical concurrent variants, ordered iteration, and range scans.

Deletion first searches for the key and records its predecessor at each level. If the key exists, each predecessor is updated to point to the deleted node’s successor at that level.

No other nodes need to move. If the highest levels become empty, the list reduces its recorded maximum height.

The first parameter is the promotion probability p. A value of p = 1/2 halves the expected node count at each level. Some implementations use p = 1/4 to reduce pointer usage and improve cache behaviour at the cost of more horizontal traversal.

The second parameter is the maximum level, which is selected from the expected capacity. A few dozen levels are sufficient for typical large data sets.

Every node has one pointer at level 0. With p = 1/2, each node has an expected total of two forward pointers.

A skip list generally uses more pointer memory than a balanced tree but has simpler update operations. The appropriate choice depends on memory constraints, concurrency requirements, and access patterns.

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-list updates modify a small set of predecessor links. They do not require root rotations or changes to entire subtrees.

This locality supports practical concurrent implementations. Fraser’s work on lock-free data structures and Java’s ConcurrentSkipListMap use ordered pointer updates rather than structural rebalancing.

Storage engines often use a skip list as the memtable, which is the mutable in-memory structure that receives writes before they are flushed to disk.

LevelDB uses this approach. Writes enter both a log and the memtable, reads search the memtable, and flushes iterate entries in key order to create an immutable file. These operations match the requirements of an LSM-tree write buffer.

Skip lists generally have simpler implementations and can support localized concurrent updates. Balanced trees provide worst-case performance guarantees and may offer more compact, cache-efficient representations.

A skip list relies on a probabilistic height distribution rather than explicit rebalancing after each update.

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.

A search moves right while the next key remains below the target, then descends when the next step would pass the target. The search completes at level 0.

Random node heights create the higher-level links without a separate rebalancing operation.

A skip list is a sorted linked list with additional forward pointers at randomly selected levels. Search, insertion, and deletion each take expected O(log n) time.

Its probabilistic structure replaces the explicit rotations and balance invariants used by balanced search trees.