↩ back to Probabilistic

Skip List

AVL and red-black trees both solve the same problem — keep a sorted structure searchable in O(log n) no matter what order things arrive in — by enforcing a deterministic rule after every write and paying for a rotation or a recolor whenever that rule breaks. A skip list solves the identical problem with no rule to enforce at all: instead of one sorted linked list, it keeps several, stacked in layers. The bottom layer holds every element, in order. Each layer above is a sparser subsequence of the one below it, built by flipping a coin for every element and promoting it one layer up on a win. Searching starts at the top, sparsest layer and drops down a layer each time the next element would overshoot the target — so it can skip past large runs of elements the bottom layer would have to visit one at a time. Invented by William Pugh in 1990 as an explicitly simpler alternative to balanced trees, trading a guarantee for an expectation.

Try it

Insert a number, search for one, or delete one, and watch the comparison path light up level by level. The list below loads with 5, 2, 8, 1, 9, 3, 7, 4, 10, 6 inserted in that order through a seeded coin flip sequence, chosen so the same four-level shape shown in this page's own prose below appears on every page load, not a different random shape each time — anything you insert or delete afterward flips real, live coins instead (the same live-Math.random() honesty quicksort's random-pivot mode already uses on this site), so the list's shape above level 0 will drift from here the moment you touch it.

Promotion: the only "rebalancing" step

Every insert decides its own height independently, with no view of the rest of the list. Starting at level 0, flip a coin (probability p = 0.5 here): heads, promote to the next level up and flip again; tails, stop. That's a geometric distribution — the chance of reaching level k is pk, so each level up holds roughly half as many elements as the one below it, purely as a consequence of independent coin flips, not an explicit "keep this balanced" rule anywhere in the code. The demo's default load, worked out level by level from the exact seeded sequence above:

level 3: H -> 1 -> 4
level 2: H -> 1 -> 3 -> 4 -> 5
level 1: H -> 1 -> 3 -> 4 -> 5 -> 6 -> 10
level 0: H -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

Ten elements, four levels, node counts 10 / 6 / 4 / 2 going up — roughly halving each time, exactly the shape the coin-flip probabilities predict, with 1 and 4 both lucky enough to reach the top on this particular seed.

Search: right until you'd overshoot, then drop

Start at the head, at the highest level currently in use. At each level, move right while the next element is still less than the target; the moment the next element would be too big (or there isn't one), drop down one level and repeat from where you are — never starting over from the head. Reaching level 0 and finding the target one step ahead is a hit; finding anything else, or nothing, is a miss. Two real traces from the default load above, both reproduced by running the exact shipped search function, not estimated:

search(9):                              search(6.5)  [absent]:
level 3: move to 1                      level 3: move to 1
level 3: move to 4                      level 3: move to 4
level 3: drop down (next is NIL)        level 3: drop down (next is NIL)
level 2: move to 5                      level 2: move to 5
level 2: drop down (next is NIL)        level 2: drop down (next is NIL)
level 1: move to 6                      level 1: move to 6
level 1: drop down (next is 10)         level 1: drop down (next is 10)
level 0: move to 7                      level 0: drop down (next is 7)
level 0: move to 8                      found: no, next at level 0 is 7 != 6.5
level 0: drop down (next is 9)
found: yes

search(9) takes 10 comparisons (counting the ten trace lines above) to reach a 10-element list's last real value — worse than the roughly 4 an ideal balanced tree would need, on this particular small example, because a 10-element list barely gives the upper levels room to pay off; the gap in this page's own demo narrows fast as n grows, see Pitfalls for the measured version of that claim. search(6.5) shows the miss case: it walks the same top levels, drops all the way to level 0, and stops the instant the next element would overshoot — no need to compare against every element in between.

Insert and delete

Insert runs the search above but remembers, at every level, the last node visited before dropping down — call that array update[0..listLevel], one predecessor per level. If the target isn't already present, flip coins to pick the new node's level, then splice it in: for every level from 0 up to its new level, point the new node's forward pointer at update[i].forward[i] and repoint update[i].forward[i] at the new node. If the coin flips promoted it past the list's current tallest level, the head grows new top-level pointers straight to it and the list's tracked listLevel increases. Delete builds the identical update[] array, then unsplices the target at every level it appears on by pointing each update[i].forward[i] past it — and, if removing it emptied out the list's topmost level(s), trims listLevel back down. Neither operation ever touches a node's neighbors' heights or forces a rotation; the only structural decision a write makes is the new node's own coin-flipped level.

Reference implementation

const MAX_LEVEL = 6;   // demo cap — enough headroom for a few dozen elements
const P = 0.5;

class SkipList {
  constructor(rng) {
    this.rng = rng;                                  // () => number in [0, 1)
    this.header = { value: -Infinity, forward: new Array(MAX_LEVEL).fill(null) };
    this.listLevel = 0;
  }
  #randomLevel() {
    let lvl = 0;
    while (this.rng() < P && lvl < MAX_LEVEL - 1) lvl++;
    return lvl;
  }
  insert(value) {
    const update = new Array(MAX_LEVEL).fill(this.header);
    let x = this.header;
    for (let i = this.listLevel; i >= 0; i--) {
      while (x.forward[i] !== null && x.forward[i].value < value) x = x.forward[i];
      update[i] = x;
    }
    x = x.forward[0];
    if (x !== null && x.value === value) return;      // duplicates ignored
    const newLevel = this.#randomLevel();
    if (newLevel > this.listLevel) {
      for (let i = this.listLevel + 1; i <= newLevel; i++) update[i] = this.header;
      this.listLevel = newLevel;
    }
    const node = { value, level: newLevel, forward: new Array(newLevel + 1) };
    for (let i = 0; i <= newLevel; i++) {
      node.forward[i] = update[i].forward[i];
      update[i].forward[i] = node;
    }
  }
  search(value) {
    let x = this.header;
    for (let i = this.listLevel; i >= 0; i--) {
      while (x.forward[i] !== null && x.forward[i].value < value) x = x.forward[i];
    }
    x = x.forward[0];
    return x !== null && x.value === value;
  }
  remove(value) {
    const update = new Array(MAX_LEVEL).fill(this.header);
    let x = this.header;
    for (let i = this.listLevel; i >= 0; i--) {
      while (x.forward[i] !== null && x.forward[i].value < value) x = x.forward[i];
      update[i] = x;
    }
    x = x.forward[0];
    if (x === null || x.value !== value) return false;
    for (let i = 0; i <= this.listLevel; i++) {
      if (update[i].forward[i] !== x) break;
      update[i].forward[i] = x.forward[i];
    }
    while (this.listLevel > 0 && this.header.forward[this.listLevel] === null) this.listLevel--;
    return true;
  }
}

The interactive demo above uses an equivalent insert/search/remove with extra bookkeeping to record which node was visited at which level, purely to drive the highlighting and log text — the algorithm itself, including the coin-flip loop, is unchanged. Verified against a plain JavaScript Set as a reference model across 5,000 randomized trials (1 to 80 operations each, insert/search/delete mixed, 201,024 total operations) with a full structural check after every single operation, not just at the end: the list's level-0 order matches the model's sorted contents exactly, and every value the model has is actually searchable. Re-verified by extracting the exact shipped functions out of the HTML and re-running an equivalent pass directly against them. See /tmp/skiplist/ref.js and /tmp/skiplist/test_correctness.js, scratch, not committed.

Pitfalls

There is no guaranteed worst case, only an expected one — a genuinely different trade than AVL or red-black's hard bound. A skip list's O(log n) comes from the coin flips landing roughly as predicted; nothing stops every single flip from coming up tails. Checked, not just asserted: stubbing the shipped #randomLevel's rng to always return 0.9 (never below p = 0.5, so promotion never happens) and re-inserting this page's own 10-value default sequence collapses all four levels into one — every node stays at level 0, and the structure degenerates into a plain sorted linked list, an O(n) scan for every search. This needs no adversarial input, the same "randomization removes the need for an adversary, only bad luck" point quicksort's random-pivot Pitfalls section already makes about its own worst case — it's just vanishingly unlikely here in the honest sense of a real, computable probability: (1 - p)n per node landing at level 0, independently, or 0.510 ≈ 0.001 for all ten of this page's own default values doing it simultaneously.

The "roughly halving" shape is a real, measured trend, not just true by construction on one seed. Ran 1,000 random-order inserts per trial at four sizes, with the demo's 6-level cap lifted to 32 so it can't saturate, counting how many levels end up in actual use and comparing against log₂(n):

The gap above log₂(n) stays a small, roughly constant few levels rather than growing — consistent with the O(log n) claim, not just assumed to hold because the formula says so.

Expected memory cost is about double a plain linked list's, not the same. Each node's forward-pointer array is sized to its own coin-flipped level, and the expected value of level + 1 under this geometric process is 1 / (1 - p) = 2 for p = 0.5 — so a skip list carries roughly twice the total pointers of a single-level linked list holding the same elements, in exchange for not needing rotations or a parent pointer anywhere. Measured directly rather than just derived: summing every node's actual pointer-array length over many random builds gives 2,000.1 total pointers at n = 1,000 and 20,000.2 at n = 10,000 — both within a hair of the predicted 2n.

Where skip lists show up

• Redis sorted sets. A ZSET is backed by a skip list paired with a hash table — the skip list gives ordered range queries their O(log n), the hash table gives single-member score lookups their O(1), the same two-structures-for-two-jobs shape the LRU cache page already used for a different pair of requirements.
• LevelDB and RocksDB's default memtable. Both key-value stores buffer recent writes in an in-memory skip list before flushing to disk, specifically because concurrent lock-free insertion is easier to get right on a skip list than on a rotating balanced tree.
• Java's ConcurrentSkipListMap. The standard library's own concurrent ordered map, for the same lock-free-insertion reason named above — no rotation means no need to briefly lock a wide swath of the structure to keep it consistent mid-write.

Complexity

Time: search, insert, and remove are all O(log n) expected, not guaranteed — O(n) remains possible in the worst case, however unlikely, exactly the trade named in Pitfalls above. Space: O(n) expected, with a measured constant around 2n total forward pointers for p = 0.5 — more per-element bookkeeping than a plain linked list's single pointer, less structural complexity than AVL's cached height or red-black's parent pointer and color bit, since a skip list needs neither.

This site's guide, Choosing a Probabilistic Structure, compares this entry against Treap — the other randomized alternative to a rotation-based balanced tree — side by side.