Skip Lists

A skip list is built from a base sorted linked list containing all elements, plus a hierarchy of additional sorted linked lists layered above it. Level 0 contains every element. Level 1 contains a random subset of the elements in level 0. Level 2 contains a random subset of level 1's elements, and so on. Each element that appears in level $i$ is linked to its neighbors in level $i$ via a "forward pointer" at that level, so a single node in memory can have several outgoing pointers — one per level it participates in. The topmost levels are sparse, "skipping" over many base-level nodes in a single hop, which is exactly why the structure supports fast search. The height of a node — how many levels it appears in — is decided independently at random when the node is inserted, typically via repeated fair (or biased) coin flips: start at level 1, and with probability $p$ promote to the next level, continuing until a flip fails. This process gives each node a height following a geometric distribution. No global rebalancing step ever runs; the randomness of insertion order and coin flips is what keeps the level structure statistically well-shaped, in the same probabilistic spirit as a randomized priority queue implementation such as a randomized heap. The key structural invariant, maintained automatically by construction, is: for every level $i > 0$, level $i$ is a sorted sublist of level $i-1$, and level 0 contains all $n$ elements in sorted order. This invariant is what makes the "drop down when you can't go further right" search strategy correct — dropping a level never skips past an element, because every element on a higher level is also present, in the same order, on every level below it.

Search, insertion, and deletion all share the same core traversal pattern, often called the search fingerpath: starting from the highest level of a special header node, repeatedly move right along the current level while the next node's key is less than the target, and drop down a level whenever moving right would overshoot or hit the end. This traversal touches at most one "wrong turn" per level in expectation, which is the source of the logarithmic bound.

Search. Begin at the top-left corner (the header at the highest level). At each level, scan rightward as long as the next node's key is strictly less than the target key. When the next node's key would be $\geq$ target, drop to the next level down from the current node, and repeat. When level 0 is reached and the immediate right neighbor's key equals the target, the search succeeds; otherwise the target is absent.

Insertion. First perform a search, but remember at every level the last node visited before dropping down — these are the update pointers, one per level, indicating exactly where a new forward link must be spliced in at that level. Then flip coins to decide the new node's height $h$. Create the new node with $h$ forward pointers, and splice it into levels $1$ through $h$ using the remembered update pointers. If $h$ exceeds the current maximum level of the list, extend the header with new empty levels first.

Deletion. Perform the same search-with-update-pointers procedure. If the target is found at level 0, remove it from every level in which it appears, by relinking each update pointer to skip over the deleted node. Optionally trim trailing empty top levels from the header afterward. ``` // Node: key, and an array forward[1..height] // header: a sentinel node with forward pointers up to maxLevel, key = -infinity // maxLevel: current highest level in use // p: promotion probability (typically 0.5), maxPossibleLevel: hard cap (e.g. log_(1/p) n) function randomLevel(): lvl = 1 while random() < p and lvl < maxPossibleLevel: lvl = lvl + 1 return lvl function search(list, targetKey): x = list.header for i = list.maxLevel downto 1: while x.forward[i] != NIL and x.forward[i].key < targetKey: x = x.forward[i] // invariant: x.key < targetKey <= x.forward[i].key at this level x = x.forward[1] if x != NIL and x.key == targetKey: return x else: return NOT_FOUND function insert(list, key, value): update = array of size maxPossibleLevel, all pointing to list.header x = list.header for i = list.maxLevel downto 1: while x.forward[i] != NIL and x.forward[i].key < key: x = x.forward[i] update[i] = x x = x.forward[1] if x != NIL and x.key == key: x.value = value // key already present: update in place return newLevel = randomLevel() if newLevel > list.maxLevel: for i = list.maxLevel + 1 to newLevel: update[i] = list.header list.maxLevel = newLevel newNode = makeNode(key, value, height = newLevel) for i = 1 to newLevel: newNode.forward[i] = update[i].forward[i] update[i].forward[i] = newNode function delete(list, key): update = array of size maxPossibleLevel, all pointing to list.header x = list.header for i = list.maxLevel downto 1: while x.forward[i] != NIL and x.forward[i].key < key: x = x.forward[i] update[i] = x x = x.forward[1] if x == NIL or x.key != key: return NOT_FOUND for i = 1 to list.maxLevel: if update[i].forward[i] != x: break // x does not appear on higher levels; stop early update[i].forward[i] = x.forward[i] while list.maxLevel > 1 and list.header.forward[list.maxLevel] == NIL: list.maxLevel = list.maxLevel - 1 // trim empty top levels ```

Search invariant. At the start of every iteration of the outer loop in `search`, the current pointer $x$ satisfies $x.key < \text{targetKey}$, and $x$ is the rightmost node at level $i$ with this property among nodes visited so far. This invariant is trivially true at the header (whose key is $-\infty$) and is preserved by the inner while-loop, which only advances while the next key is still less than the target. When the loop drops to level $i-1$, the invariant transfers because level $i-1$ is a superset of level $i$'s elements in the same sorted order — dropping down cannot skip any smaller key, since any node present at level $i$ is also present at level $i-1$ in the same relative position. By induction down to level 1, when the loop terminates, $x$ is the last node with key less than the target, so $x.forward[1]$ is the only candidate that could equal the target. This proves correctness of search, and insertion/deletion inherit it directly since they run the identical traversal to locate splice points.

Expected height and space. Each node's height is $1 + \text{Geometric}(1-p)$ truncated at $\text{maxPossibleLevel}$ (ignoring the cap for the moment), so a node reaches level $i$ independently with probability $p^{i-1}$. The expected number of nodes present at level $i$ is $n \cdot p^{i-1}$. The expected total number of forward pointers across all nodes is

so expected space is $O(n)$ regardless of $p$ (with constant factor $\frac{1}{1-p}$; at $p = 1/2$ this is $2n$). The expected height of the tallest node, and hence the expected number of levels actually used, is $O(\log_{1/p} n)$: the probability that any specific node reaches level $k$ is $p^{k-1}$, so by a union bound over $n$ nodes, the probability that some node reaches level $c \log_{1/p} n$ is at most $n \cdot p^{c \log_{1/p} n - 1} = O(n^{1-c})$, which vanishes for $c > 1$. This is why capping `maxPossibleLevel` at roughly $\log_{1/p} n$ costs essentially nothing in practice.

Expected search time — the backward analysis. The classical argument (due to Pugh) analyzes the search path in reverse: start at the node found at level 1 and walk backward toward the header, tracking how many levels have been climbed. At any point during this backward walk, the number of additional backward steps taken at the current level before climbing to the next level up is dominated by a geometric random variable with parameter $p$ (since climbing a level happens exactly when a coin flip "promotes" the current node, an event with probability $p$ independent of history). Since climbing occurs at most $O(\log_{1/p} n)$ times before reaching the maximum level (by the height bound above), and each level contributes an expected constant $\frac{1}{p}$ number of backward steps, the total expected path length is

for constant $p$. This gives expected $O(\log n)$ time for search, and since insertion and deletion perform one search plus $O(1)$ expected splice work per level touched, they are also expected $O(\log n)$.

Honest tradeoffs. These bounds are expected, not worst-case: an adversarial (or simply unlucky) sequence of coin flips can produce a degenerate list where every node has height 1, collapsing search to $\Theta(n)$. This happens with exponentially small probability, but it is not impossible, unlike the strict worst-case guarantees of AVL or red-black trees. In exchange, skip lists avoid all rotation logic, support easy concurrent lock-free implementations (because insertion only needs to splice pointers locally, not rebalance globally), and make order-statistics operations (like "find the $k$-th smallest element") easy to add by augmenting each forward pointer with a span count. This last technique is exactly how Redis implements the `ZRANK` command on sorted sets in $O(\log n)$.

Consider inserting the keys `10, 30, 20, 40, 60, 90, 70, 50` one at a time into an initially empty skip list with $p = 0.5$, using the (illustrative, fixed for reproducibility) coin-flip outcomes below. "H,H,T" means: flip succeeds (promote), succeeds again, then fails, giving height 3.

After all eight insertions, the list matches the structure shown in the figure above: level 1 has all eight keys, level 2 has {20, 40, 60, 90}, level 3 has {20, 40, 90}, and level 4 has {90}. (The figure's level 3 shows {40, 90} for compactness — either arrangement is a valid random outcome; what matters is that the invariant "each level is a sorted sublist of the one below" holds throughout.) Now trace `search(50)` on the figure's structure: 1. Level 4, at header: `forward[4]` points to 90. Is $90 < 50$? No. Drop to level 3, staying at the header. 2. Level 3, at header: `forward[3]` points to 40. Is $40 < 50$? Yes, advance to node 40. From 40, `forward[3]` points to 90. Is $90 < 50$? No. Drop to level 2, staying at node 40. 3. Level 2, at node 40: `forward[2]` points to 60. Is $60 < 50$? No. Drop to level 1, staying at node 40. 4. Level 1, at node 40: `forward[1]` points to 50. Is $50 < 50$? No (not strictly less). Drop is not possible (already at level 1), so the outer loop ends with $x =$ node 40. 5. Check `x.forward[1]`: it is node 50, whose key equals the target. Search succeeds, returning node 50. Total comparisons: 1 (level 4) + 2 (level 3) + 1 (level 2) + 1 (level 1) = 5 comparisons to search among 8 elements — consistent with the $O(\log n)$ bound ($\log_2 8 = 3$, and small constants dominate at this tiny scale). Inserting a new key, say 45, would perform this same traversal, record update pointers at each level (header at L4 and L3-after-40, node 40 at L2, node 40 at L1), flip coins for a new height, and splice the new node into exactly those recorded slots.

< /table> | Not capping `randomLevel` | Height is technically unbounded (geometric distributions have infinite support) | Cap at $O(\log n)$ in practice; astronomically tall nodes are vanishingly unlikely but must not overflow arrays | | Comparing with `<=` instead of `<` in search | Causes the traversal to stop one node too early or too late, breaking the "rightmost node less than target" invariant | Use strict `<` consistently when deciding whether to advance; use equality only for the final level-1 check | | Treating expected time as worst-case in latency-sensitive code | A rare bad coin sequence degrades to $\Theta(n)$, which can violate real-time guarantees | Acknowledge in SLAs that skip lists give expected, not guaranteed, bounds; use a balanced tree if hard worst-case latency is required |

Skip lists were invented as a deliberately simple alternative to balanced binary search trees, motivated by the observation that many balanced-tree implementations in production code were riddled with subtle rotation bugs. The design goal was explicit: get the same asymptotic guarantees as red-black trees or AVL trees, in expectation, using an algorithm simple enough that a competent programmer could implement it correctly on the first try, without needing to reason about rotations, rebalancing invariants, or tree-height bookkeeping.

Skip lists are a working part of production infrastructure, not merely a textbook curiosity. Redis implements its sorted-set type (`ZADD`, `ZRANGE`, `ZRANK`) with an augmented skip list that stores span counts on forward pointers, enabling both range queries and rank queries in expected $O(\log n)$ time. LevelDB and RocksDB, the storage engines underlying many key-value stores and used inside systems like CockroachDB, Cassandra's variants, and Bitcoin Core's on-disk indexing, use skip lists for their memtables — the in-memory buffer that absorbs writes before they are flushed to sorted files on disk — because skip lists tolerate concurrent readers during a single writer's insertion without complex locking. Concurrent and lock-free skip list variants are used in some Java concurrency libraries (`ConcurrentSkipListMap` and `ConcurrentSkipListSet` in `java.util.concurrent`) precisely because splicing a pointer locally is far easier to make lock-free than rebalancing a tree. Skip lists also serve as a standard teaching bridge between Linked Lists and more advanced balanced structures, and their level-count-by-coin-flip idea recurs in other randomized structures built on similar principles to a randomized priority queue.

Ask the tutor: How would you augment a skip list's forward pointers with span counts to answer "what is the rank of key k?" in expected O(log n) time?