Recipe

Skip list primer

Skip lists are probabilistic data structures that deliver O(log n) search, insert, and delete on average without the balancing ceremony of red-black or AVL trees. They're a favorite in distributed systems, in-memory stores, and any place a sorted set needs to be cheap to maintain under heavy concurrent writes.

1. Why probabilistic balance

A skip list stacks multiple linked lists on top of each other. Each node is promoted to a higher level with probability p (commonly 0.5). On average half the nodes live on level 2, a quarter on level 3, and so on, which gives the structure its logarithmic search depth without ever rotating a subtree.

2. Search, insert, delete

Search walks the top level until the next pointer would overshoot, then drops down a level and repeats. Insert reuses that descent to capture an update vector, picks a random level, and splices new forward pointers. Delete is the same descent followed by unlinking forward pointers up to the node's height.

3. Reference implementation

The TypeScript sketch below covers the insert path. The comparator keeps the structure generic, and randomLevel caps height at maxLevel so a single unlucky promotion chain can't blow up memory.

// Skip list node
type Node<T> = {
  value: T;
  forward: Array<Node<T> | null>;
};

function randomLevel(maxLevel: number, p = 0.5): number {
  let lvl = 1;
  while (Math.random() < p && lvl < maxLevel) lvl++;
  return lvl;
}

class SkipList<T> {
  head: Node<T>;
  level = 1;
  constructor(public maxLevel = 16) {
    this.head = {
      value: null as unknown as T,
      forward: new Array(maxLevel).fill(null),
    };
  }

  insert(value: T, cmp: (a: T, b: T) => number) {
    const update: Array<Node<T>> = new Array(this.maxLevel).fill(this.head);
    let x: Node<T> = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (x.forward[i] && cmp(x.forward[i]!.value, value) < 0) {
        x = x.forward[i]!;
      }
      update[i] = x;
    }
    const lvl = randomLevel(this.maxLevel);
    if (lvl > this.level) {
      for (let i = this.level; i < lvl; i++) update[i] = this.head;
      this.level = lvl;
    }
    const node: Node<T> = { value, forward: new Array(lvl).fill(null) };
    for (let i = 0; i < lvl; i++) {
      node.forward[i] = update[i].forward[i];
      update[i].forward[i] = node;
    }
  }
}