Skip Lists: Express Lanes over a Sorted Chain

A sorted linked list supports insertion and deletion in O(1) once the position is known, and search in O(n) because the only way to find a position is to walk to it. A balanced tree fixes the search by maintaining height invariants, at the cost of rotations that must be implemented correctly under every insertion and deletion case. A skip list fixes the search with a second set of pointers that skip over ranges, and it maintains its structure by coin flips rather than by invariants.

The result is a structure whose search, insertion, and deletion are all expected O(log n), whose implementation is a few dozen lines, and whose worst case is O(n) with a probability that falls exponentially. The trade is deterministic guarantees for simplicity and expected performance, and the analysis of why the expectation holds is the interesting part.

The two-level idea

Start with a sorted singly linked list at level 0. Add a second list at level 1 that contains every fourth element of level 0 and links those elements together. A search begins at the head of level 1, follows it while the next key is smaller than the target, then drops to level 0 at the last element that was not greater than the target and continues there.

With a uniform skip of k, the search touches about n/k nodes at the top level and k nodes at the bottom, so the total is minimised at k = √n and the cost is 2√n. That is better than linear and worse than logarithmic. Adding a third level with the same ratio gives a cube root, and with log₂ n levels the cost is logarithmic. The structure is a hierarchy of increasingly sparse chains over the same sorted elements, and a node participates in a prefix of the levels.

A skip list chooses the level of each node randomly rather than maintaining exact skips. Each node is promoted to the next level with probability p, independently, so the expected fraction of nodes at level i is pⁱ. With p = 1/2 the expected number of levels is log₂ n, and the expected number of nodes at the top level is 1.

The node and the search

A node carries a key, a value, and an array of forward pointers, one per level it participates in.

#define MAXLEVEL 32

struct snode {
    int key;
    int value;
    struct snode *forward[MAXLEVEL];   /* forward[i] skips 2^i-ish nodes */
};

struct skiplist {
    int level;                         /* current highest level in use */
    struct snode *head;                /* sentinel with MAXLEVEL pointers */
};

A fixed MAXLEVEL array per node is the simple layout and it wastes memory: a node at level 1 carries 31 unused forward pointers. With 8-byte pointers, MAXLEVEL 32, and a 4-byte key and value, every node is at least 272 bytes. Production implementations allocate the array with the node’s actual level, either as a variable-length trailing array in the same allocation or as a separate block, which reduces the average node to about twice the level-0 size because the level distribution is geometric.

Search descends from the top:

struct snode *search(struct skiplist *l, int key) {
    struct snode *x = l->head;
    for (int i = l->level; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->key < key)
            x = x->forward[i];
    }
    x = x->forward[0];
    return (x && x->key == key) ? x : NULL;
}

The loop invariant is that x is the last node visited at level i whose key is less than the target. Each level’s inner loop advances as far as possible without overshooting, and the descent to level i−1 resumes from the same node, which is exactly the node whose forward pointer at the lower level covers the range that was skipped. This is the same descent as a search in a balanced tree, expressed with arrays of pointers instead of left and right children.

Why the expected bound holds

The analysis is a backward argument, which is easier than the forward one. Consider the search path in reverse: start at the node where the search ended and walk back to the head. A node that appears at level i also appears at level i+1 with probability p, so at each backward step the previous step came from above with probability p and from the left at the same level with probability 1 − p. The expected number of steps to climb one level is therefore 1/p, and the number of levels to climb is log₁/ₚ n, giving an expected path length of (1/p) log₁/ₚ n plus the final descent term of at most 1/(1 − p).

That expression is worth reading carefully, because the leading coefficient 1/(p ln(1/p)) is not monotone in p. It is minimised near p = 1/e, and it takes the same value at p = 1/2 and at p = 1/4: both give about 2.9 ln n, which is 2 log₂ n. Reducing p below 1/2 therefore does not shorten the search; it reduces memory. The expected number of pointers per node, counting the level-0 link, is 1/(1 − p), so p = 1/2 costs two pointers per node on average and p = 1/4 costs 1.33. Pugh’s analysis gives the same conclusion, and the practical reading is that p = 1/4 is the better default: nearly the same search cost for a third less pointer storage.

Pugh’s concentration bound shows that the probability the search exceeds c times the expectation decays exponentially in c, so the expected bound is not a fragile average: the tail is thin. Redis uses p = 1/4, which is documented in its sorted-set implementation, together with a maximum height; the fixed maximum caps the worst-case search length in pointer steps, and the number of elements a list can hold is limited by memory rather than by the level cap.

Insertion and the update array

Insertion needs to modify the forward pointers of every node that the search passed at each level. The standard implementation records those nodes in a small array during the descent.

void insert(struct skiplist *l, int key, int value) {
    struct snode *update[MAXLEVEL];
    struct snode *x = l->head;
    for (int i = l->level; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->key < key)
            x = x->forward[i];
        update[i] = x;
    }
    int lvl = random_level();
    if (lvl > l->level) {
        for (int i = l->level + 1; i <= lvl; i++) update[i] = l->head;
        l->level = lvl;
    }
    struct snode *n = alloc_node(lvl, key, value);
    for (int i = 0; i <= lvl; i++) {
        n->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = n;
    }
}

The update array is the mechanism that makes the whole structure simple: the descent already determined, for every level, the last node that should point at the new one, so insertion is a loop of pointer writes with no rebalancing. There are no rotations, no split cases, and no invariant to restore beyond the ordering. This is the practical advantage over a balanced tree, and it is why skip lists appear in codebases where the tree implementation was judged too error-prone to maintain.

random_level draws from a geometric distribution. The listing below declares its node after a statement, so it needs C99 or later; the preceding listings rely on the same rule:

static int random_level(void) {
    int lvl = 0;
    while (lvl < MAXLEVEL - 1 && (rand() & 1) == 0) lvl++;   /* p = 1/2 */
    return lvl;
}

The generator must be fast and independent across nodes. A poor generator that correlates levels with insertion order can produce a degenerate structure; a deterministic generator seeded per structure makes the structure reproducible, which is useful for testing and dangerous for adversarial inputs. An adversary who knows the seed and the key sequence can choose keys that all land at low levels, degrading search to O(n). Skip lists are therefore not a defence against adversarial keys in the way that a randomised hash table is, unless the level draw is seeded from a source the adversary cannot predict.

Deletion mirrors insertion with the same update array: descend, record the predecessors, then unlink the node at every level where it appears. The level of the list is decremented when the top level’s forward pointer becomes null.

Comparison with the balanced tree

The two structures answer the same problem with different guarantees, and the comparison is specific.

Property	Skip list	Balanced tree
Search worst case	O(n)	O(log n)
Search expected	O(log n)	O(log n)
Insertion code	pointer writes	rotations, split cases
Ordered iteration	follow level 0	in-order traversal
Concurrent update	local pointer CAS	rotations touch several nodes
Memory per element	1–2 extra pointers expected	2–3 pointers plus balance bits

The concurrency row is the one that matters most in practice. A skip list insertion modifies one pointer per level, and each modification is an independent CAS on a single field. A red-black tree insertion rotates, and a rotation changes three pointers that must appear to change together. This is why concurrent ordered maps are frequently built as skip lists: the update is a sequence of single-word atomic operations with a localised conflict footprint, and the lock-free techniques in Lock-Free Linked Lists apply to each level independently.

The cost is the worst case. A balanced tree guarantees O(log n) for every input; a skip list guarantees it only in expectation. For a structure where a single slow operation is unacceptable, such as a real-time index, the tree’s determinism is worth the implementation complexity. For a structure where the average matters and the code must be maintainable, the skip list is usually the better engineering choice.

Cache behaviour and the constant factor

A skip list search touches one node per step, and each step is a dependent load: the next address comes from the current node. The expected number of steps is logarithmic, but each step is a cache miss on a large structure, so the constant is the DRAM latency rather than the comparison count.

Two layout choices reduce this. The first is to allocate nodes with their forward array inline, so the level-0 pointer and the key share a line; a node whose key is on a different line from its pointer pays two misses per step instead of one. The second is to place the higher levels’ pointers in the same allocation as the lower ones, which they are by construction, so a descent through several levels at the same node reads one line. The same packing argument, applied to a single chain rather than a hierarchy, is what motivates Unrolled Linked Lists.

A B-tree’s advantage over a skip list is precisely here: a B-tree node holds many keys and many child pointers, so one cache miss resolves a whole fan-out, and the tree height is log₃₂ n rather than log₂ n. For an index that lives on disk or in a large in-memory dataset, the B-tree’s per-node density beats the skip list’s per-node sparsity. For an in-memory index that fits in cache, the difference is small and the skip list’s simpler update path dominates.

Where the level bookkeeping breaks

The defects in skip list implementations are concentrated in the level bookkeeping.

Level overflow. random_level must be clamped to MAXLEVEL, and the clamp must be enforced before the forward array is written. A level beyond the array’s capacity writes past the allocation.

Stale level after deletion. Removing the only node at the top level must decrement the list’s level. The head sentinel always has an array at every level, so a stale level does not dereference an empty slot; it makes each search start one level above the highest populated one, paying one extra comparison and, in implementations that size the head dynamically, reading a pointer that no node uses.

Duplicate keys. The comparison in the descent and the comparison in the final check must agree. Searching with < during the descent and testing == at the end yields insertion before equal keys; searching with <= and testing == yields insertion after them. Mixing the two produces a structure whose duplicate keys are neither all before nor all after the existing ones, which breaks any code that assumes one of the two.

Recursive descent. A search written as a recursion over levels has its depth bounded by MAXLEVEL, which is smaller than any default thread stack by a wide margin; the accumulation that matters is the call overhead, not the stack. The iterative form above is the usual implementation for that reason.

Unbounded level with an adversarial generator. As noted, a predictable level draw lets an adversary force a degenerate structure. Seeding from a per-structure random source removes the predictability at the cost of reproducibility.

The structure’s simplicity is real, and it is worth stating what it buys: the invariant is only that level i’s list is a subsequence of level i−1’s, and no operation can violate it. That is a much smaller invariant than a red-black tree’s colour rules, and the smaller invariant is why the implementation is short and why the bugs that remain are in the bookkeeping rather than in the rebalancing. The same question of what a list can guarantee against the best fixed order appears in Introduction to Algorithms, chapter 27, which analyses maintaining a search list as an online problem.