Skip Lists

July 2026 · 24 min read

A sorted array supports binary search: you jump to the middle, compare, and discard half the range in O(log n). A sorted linked list holds exactly the same keys in exactly the same order and yet its search is O(n), because there is no middle to jump to — you can only reach element k by walking through elements 0 through k−1. The skip list is the structure that buys back binary search for a linked list, and it does so with a trick that feels illegal the first time you see it: it replaces careful rebalancing with a coin toss.

The Problem: A Sorted List Cannot Binary Search

Here is the whole difficulty in one line. Binary search needs random access — the address of the middle element computed by arithmetic. In a linked list the address of element k+1 lives inside element k, so you cannot compute a midpoint without first walking to it. Sorting the list did not help: a sorted singly linked list still costs O(n) to search, the same as an unsorted one. All the order bought you is an early exit once you pass the key.

So the question is not "how do I sort the list" but "how do I add a way to skip forward without walking every node". The answer is to build extra lanes above the base list — express lanes that stop at only some of the nodes — and to descend into the slow lane only near the target.

One Express Lane: O(√n)

Start with two levels. Keep the full sorted list on the bottom (level 0). Above it, build a second list (level 1) that contains every k-th node and links those nodes together. Each level-1 node also carries a down pointer to its twin on level 0. To search, ride level 1 until the next express node would overshoot the key, drop down, then walk level 0.

Count the work. The express lane has n/k nodes, so you take at most n/k hops up top. Once you drop down, you walk at most k−1 nodes before hitting the key or passing it, because consecutive express nodes are k apart. Total: n/k + k comparisons. Calculus (or the AM–GM inequality) minimises n/k + k at k = √n, giving O(√n). For a million keys that is a thousand steps instead of a million — a 1000× win from a single extra lane.

More Lanes: O(log n), But Insertion Breaks

If one express lane gives O(√n), an express lane over the express lane gives more. Promote every 2nd node to level 1, every 4th to level 2, every 8th to level 3, and so on. Now each level has half the nodes of the one below it, there are log₂ n levels, and each level costs you at most one or two hops before you drop. Search becomes O(log n) — you have rebuilt a balanced binary search tree lying on its side. Every "drop down one level" is a "go to a child", every "hop right" is a "the key is larger, keep looking".

And there the clean deterministic version dies. This perfect ½/¼/⅛ structure is only balanced if the promoted nodes stay exactly every-other. Insert one key into the middle and the "every 2nd node" property shatters: to restore it you would have to re-promote and re-link roughly half the list, an O(n) rebuild per insert. Deterministic multi-level lists are gorgeous to search and catastrophic to update — the same reason a plain sorted array is O(1) to read and O(n) to insert into.

Randomised Promotion: Flip a Coin

Pugh's 1990 insight was to stop trying to keep the levels perfect. Instead of deciding a node's height from its position, decide it when the node is born, by flipping a coin:

int random_level() {
    int lvl = 0;
    while (coin_flip_is_heads() && lvl < MAX_LEVEL)
        ++lvl;               // keep promoting while the coin comes up heads
    return lvl;              // height 0 with prob 1/2, 1 with 1/4, 2 with 1/8 ...
}

A new node is always on level 0. With probability p = 1/2 it is promoted to level 1; if promoted, with probability p again to level 2; and so on. A node ends at height h with probability (1−p)·ph — a geometric distribution. Crucially, no node's height depends on any other node's height or position. That independence is the entire point: an insert never invalidates the height of an existing node, so there is nothing to rebalance. The structure is not kept balanced — it is kept balanced in expectation, which for random inputs is just as good and requires no maintenance code at all.

Half the nodes sit only on level 0, a quarter reach level 1, an eighth reach level 2. On average each level holds half the nodes of the one below, exactly the deterministic ideal — but achieved without any node ever knowing where it "should" be. Randomisation replaced rebalancing with nothing.

Why It Works: The Expected-Cost Analysis

Four numbers make the skip list trustworthy. Take p = 1/2 throughout; the general forms are in parentheses.

Expected node height. The number of promotions is a geometric random variable; its expectation is p/(1−p) = 1 extra level, so a node spans 1/(1−p) = 2 levels on average.

Expected number of levels. Level i holds about n·pi nodes. The highest level with any node is where that count drops to one, i.e. i ≈ log1/p n = log₂ n. That is why MAX_LEVEL = 16 comfortably covers 65 536 keys and MAX_LEVEL = 32 covers four billion.

Expected space. Total pointers is n times the expected height, n/(1−p) = 2n. A skip list costs about two pointers per node on average — the same order as a doubly linked list, and less than a red–black tree's two child pointers plus parent plus colour bit.

Expected search cost. This is the one worth proving, and the cleanest proof runs the search backwards. Stand on the target node and climb toward the head sentinel, retracing the search path in reverse. At each node on that reversed path you either rose into it from a higher level or arrived from the left along the current level. Because a node's presence on the next level up is an independent coin flip, at every step of the climb you go up with probability p and left with probability 1−p. Let C(k) be the expected number of steps to climb k levels:

C(k) = 1 + (1 - p)·C(k) + p·C(k - 1)
  =>  p·C(k) = 1 + p·C(k - 1)
  =>  C(k) = 1/p + C(k - 1)  =  k / p

The climb spans k = log1/p n levels, so the expected path length is (log1/p n)/p. For p = 1/2 that is 2·log₂ n — O(log n) expected comparisons, with a small, tunable constant. Lowering p to 1/4 makes nodes shorter (less space, ~1.33n pointers) at the cost of more horizontal walking; p = 1/2 is the usual sweet spot and p = 1/4 is what Redis chose.

A Complete C++ Skip List

Each node stores its key and a vector of forward pointers — one per level it participates in. A single head sentinel of full height anchors every level.

#include <vector>
#include <cstdlib>
#include <climits>

struct SkipNode {
    int key;
    std::vector<SkipNode*> forward;      // forward[i] = next node on level i
    SkipNode(int k, int height)
        : key(k), forward(height + 1, nullptr) {}
};

class SkipList {
    static const int MAX_LEVEL = 16;      // covers ~2^16 keys at p = 1/2
    SkipNode* head_;                       // sentinel: -inf key, full height
    int level_;                            // highest level currently in use

    int random_level() {
        int lvl = 0;
        while ((std::rand() & 1) && lvl < MAX_LEVEL)   // flip while heads
            ++lvl;
        return lvl;
    }

public:
    SkipList() : head_(new SkipNode(INT_MIN, MAX_LEVEL)), level_(0) {}

    ~SkipList() {
        SkipNode* p = head_->forward[0];
        while (p) { SkipNode* nx = p->forward[0]; delete p; p = nx; }
        delete head_;
    }

Search is the analysis made literal: at each level walk right while the next key is smaller than the target, then drop. When you can descend no further, the very next node on level 0 is the only possible match.

    SkipNode* search(int key) const {
        SkipNode* x = head_;
        for (int i = level_; i >= 0; --i)
            while (x->forward[i] && x->forward[i]->key < key)
                x = x->forward[i];         // ride the express lane
        x = x->forward[0];                 // step into the slow lane once
        return (x && x->key == key) ? x : nullptr;
    }

Insert is where the crux lives: the update[] array. As you descend, update[i] records the last node you stood on at level i — that is, the node whose forward[i] pointer would need to change if a new node were spliced in at this level. It is exactly the predecessor of the insertion point on every level at once. After the walk, splicing the new node is a per-level forward rewrite using those saved predecessors — the same "save, rewire" surgery as an ordinary list, done height + 1 times.

    void insert(int key) {
        std::vector<SkipNode*> update(MAX_LEVEL + 1, head_);
        SkipNode* x = head_;
        for (int i = level_; i >= 0; --i) {
            while (x->forward[i] && x->forward[i]->key < key)
                x = x->forward[i];
            update[i] = x;                 // predecessor on level i
        }
        x = x->forward[0];
        if (x && x->key == key) return;     // keys are unique

        int lvl = random_level();
        if (lvl > level_) {                 // taller than anything so far
            for (int i = level_ + 1; i <= lvl; ++i)
                update[i] = head_;         // new levels start at the head
            level_ = lvl;
        }
        SkipNode* n = new SkipNode(key, lvl);
        for (int i = 0; i <= lvl; ++i) {   // splice on every level it reaches
            n->forward[i]      = update[i]->forward[i];
            update[i]->forward[i] = n;
        }
    }

Erase reuses the identical update[] walk, then unlinks the victim on each level it appears, and finally demotes the list's top level if the tallest lanes are now empty.

    void erase(int key) {
        std::vector<SkipNode*> update(MAX_LEVEL + 1, head_);
        SkipNode* x = head_;
        for (int i = level_; i >= 0; --i) {
            while (x->forward[i] && x->forward[i]->key < key)
                x = x->forward[i];
            update[i] = x;
        }
        x = x->forward[0];
        if (!x || x->key != key) return;   // not present

        for (int i = 0; i <= level_; ++i) {
            if (update[i]->forward[i] != x) break;   // x rose no higher
            update[i]->forward[i] = x->forward[i];
        }
        delete x;
        while (level_ > 0 && head_->forward[level_] == nullptr)
            --level_;                       // demote now-empty top levels
    }
};

Watch a Search Descend

The animation below searches for 19 in a four-level skip list. Follow the cursor: at each level it hops right only while the next key is still smaller than 19, then drops. Notice the two express-lane jumps — the top lane leaps straight from the head to 25, and level 2 leaps from the head over 3 and 6 to 9 — each skipping nodes a plain list would have been forced to visit.

The same descent as a static trace, if you prefer to read it without the animation:

L3:  head.forward = 25   ->  25 >= 19   ->  drop to L2
L2:  head.forward =  9   ->   9 <  19   ->  move right to 9   (skips 3, 6)
L2:     9.forward = 25   ->  25 >= 19   ->  drop to L1
L1:     9.forward = 17   ->  17 <  19   ->  move right to 17  (skips 12)
L1:    17.forward = 25   ->  25 >= 19   ->  drop to L0
L0:    17.forward = 19   ->  19 !< 19   ->  stop; candidate = forward[0] = 19
=>   19 == 19  :  FOUND   (7 moves, 6 comparisons)

Seven cursor moves reached a node six positions deep. A plain sorted list would have compared against 3, 6, 9, 12, and 17 — five wasted comparisons — before arriving at 19. The express lanes turned a linear scan into a logarithmic descent.

Skip List vs. the Alternatives

A skip list competes with balanced BSTs, sorted arrays, and hash maps. It rarely wins on raw speed; it wins on engineering. The honest scorecard:

Read the last two rows together with the rest. A skip list matches a balanced tree on every complexity column, loses the worst-case guarantee, and wins decisively on implementation effort and concurrency. That trade — give up a guarantee you rarely need, gain code you can actually get right and parallelise — is why skip lists show up in production far more than their textbook prominence suggests.

Why Real Systems Reach for Them

Redis sorted sets. A Redis ZSET pairs a skip list with a hash map, and the split of duties is the whole design. The hash map maps member → score so ZSCORE is O(1); the skip list keeps members ordered by score so ZRANGE, ZRANK, and score-range queries are O(log n + m). Neither half alone suffices — the hash gives point lookups but no order, the skip list gives order but slower point lookups — so Redis keeps both in sync. Antirez chose a skip list over a balanced tree explicitly for implementation simplicity and because ordered range iteration falls out for free, using p = 1/4 to save memory.

LevelDB and RocksDB memtables. The in-memory write buffer that absorbs incoming writes before they are flushed to disk is a skip list. It has to accept concurrent inserts while being scanned, and a skip list's inserts are purely local pointer splices — no rotation ever touches a distant node — which makes a lock-free implementation tractable. A red–black tree's rotations reshape whole subtrees and are far harder to make concurrent.

java.util.concurrent.ConcurrentSkipListMap. The JDK ships a lock-free ordered map built on a skip list for exactly this reason: it is the ordered container that parallelises cleanly. There is no ConcurrentTreeMap in the standard library, and the absence is not an oversight.

Check Yourself

Each item gives a situation; pick the statement that is actually true of a randomised skip list.

Practice

• LeetCode 1206 — Design Skiplist core implement search, add, and erase with the update[] array exactly as above.
• Read Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees (CACM 1990). source reproduce the backward-analysis argument for p = 1/4 and confirm the expected cost is (log₄ n)·4.
• Instrument random_level() to log heights over a million inserts. distribution verify roughly half the nodes are height 0, a quarter height 1, and plot the geometric tail.
• LeetCode 2590 — Design a Todo List ordered build the ordered-by-priority view on a skip list and compare against a std::multiset.
• Add a rank(key) query by storing a span (number of level-0 nodes skipped) on each forward pointer. indexable this is the augmentation Redis uses for ZRANK.
• Combine a skip list with a hash map to build a miniature ZSET. systems support O(1) score lookup and O(log n + m) range queries, keeping both halves consistent.