Skip Lists | mysimulator.uk

The idea: express lanes over a sorted list

A sorted singly linked list makes search O(n): you can only walk forward one node at a time. William Pugh's skip list (1989) fixes this by building extra "express lane" layers on top of the base list. A node that lives at level k has a forward pointer that can skip past every level-(k-1)-and-below node in front of it, letting a search descend from a high, sparse level down to level 1, moving mostly in wide jumps and only in narrow steps near the target.

Building levels with a coin flip

Every node's height is decided independently, at insert time, by repeated coin flips: with probability p (usually 1/2) it is promoted to the next level up, and this repeats until a flip fails. No global rebalancing, no rotations, no colours — the structure's balance emerges purely from probability.

randomLevel(p = 0.5, maxLevel):
  level = 1
  while random() < p and level < maxLevel:
    level += 1
  return level

insert(key):
  level = randomLevel()
  find the predecessor node at each level 1..level (search path)
  splice the new node into the forward pointers at each of those levels

live demo · a probabilistic hierarchy of express lanes● LIVE

Why the expected search time is O(log n)

With p = 1/2, roughly half the nodes on any level get promoted to the next level up, so the expected number of nodes at level k is n/2^(k-1) — and the expected top level is about log2(n). A search that starts at the top level and moves right-or-down at each step takes an expected O(1) steps per level (a small geometric-series argument bounds the number of rightward moves before dropping a level), for a total expected cost of O(log n) across all levels. This mirrors the analysis of a balanced binary search tree almost exactly, but with randomness standing in for an explicit balancing invariant.

Skip lists vs balanced trees

The trade skip lists make is honest: they give up a worst-case guarantee for a much simpler implementation. Insertion and deletion in a skip list are just pointer splices along an already-found search path — no rotations, no recolouring, no cascading fixups. That simplicity matters most in concurrent code, where a lock-free or fine-grained-locking skip list is dramatically easier to implement correctly than a lock-free balanced tree, because updates at different levels can often proceed independently.

Where they run in production

Redis implements its sorted-set type (ZSET) with a skip list paired with a hash table, specifically because skip lists make range queries ("give me the top 10 scores") and rank lookups simple to implement alongside O(log n) insert and delete. Several LSM-tree storage engines, including the memtable in LevelDB and RocksDB, use a skip list as the in-memory sorted buffer that incoming writes land in before being flushed to disk, again favouring simple, lock-friendly concurrent writes over a marginally faster balanced tree.

Frequently asked questions

Is a skip list's O(log n) search guaranteed?

Only in expectation, not in the worst case. Because level promotion is a coin flip, an extremely unlucky run of flips could in principle leave every node on level 1 only, degrading search to O(n). In practice the probability of that happening is astronomically small and shrinks exponentially with n, which is why skip lists are treated as O(log n) for all practical purposes, with a small, well-understood constant-factor variance.

Why use a skip list instead of a balanced tree?

A skip list needs no rotations, no colour bits and no rebalancing logic — insertion and deletion are simple local pointer updates once the search path is found, which makes it dramatically easier to implement correctly, especially in a lock-free or concurrent setting where balancing a tree under concurrent modification is notoriously hard. The cost is a small amount of extra memory for the forward pointers on promoted nodes and probabilistic rather than guaranteed worst-case bounds.

What determines how many levels a skip list needs?

With promotion probability p = 1/2, the expected number of levels for n elements is about log2(n), since each level holds roughly half as many nodes as the one below it. Implementations cap the maximum level at something like log(1/p) of the expected maximum n (often 16 or 32) purely to bound memory, since levels beyond that are vanishingly unlikely to ever be used.

Try it live

Everything above runs in your browser — open Skip Lists and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Skip Lists simulation

Skip Lists: Express Lanes Over a Linked List