Skip List Insert & Search

Start from brute force

The obvious structure is the bottom level alone: one sorted linked list. Insert walks from the head until the next value is not smaller and splices the node in; search walks the same way and checks the next node. It is correct, because the list is always sorted, and it uses O(n) space. But every operation walks node by node, so each costs O(n) and n inserts cost O(n²): a search for the last of a million values follows a million pointers. A sorted array with binary search fixes the search but not the insert, which still shifts O(n) elements. The skip list keeps the linked list and adds express lanes above it.

The approach

Each level is a sorted linked list over a subset of the level below, so a search covers ground on the sparse upper levels and refines on the dense lower ones. The rule on every level: move right while the next value is smaller than the target, then drop down. The node where you drop down on level i is the last node there that is smaller than the target, which is exactly where a new node must be spliced in on that level. With random heights each level holds about half the nodes of the one below, which gives expected O(log n) steps.

In the reference, a node is [value, forward] and head is a sentinel with MAX_LEVEL = 16 forward pointers. descend(value, update) runs that loop from level 15 down to 0 and, when given an update list, stores the drop-down node of each level. An insert builds node = [value, [None] * (height + 1)] and, for each level i up to height, sets node[1][i] = update[i][1][i] and then update[i][1][i] = node. A search calls descend(value) and checks whether the level-0 successor nxt holds value.

Walk through an example

Trace the first example, where the middle column shows the node at which descend drops down on levels 2, 1 and 0 (levels 3 to 15 stay empty, so it never leaves head there).

Complexity

Optimal: with random heights, expected O(log n) per insert and search, and expected O(n) space, about two forward pointers per node when each level keeps half the nodes. The reference also walks all 16 levels on every call, a constant, and with given heights its speed depends on them: all heights 0 is a plain list. Brute force (one sorted linked list): O(n) per operation, O(n) space.

Edge cases to test

• Searching an empty list: [["search",7]] → [False]. descend never leaves head, whose level-0 successor is None.
• Duplicate values: [["insert",10,3],["insert",10,0],["search",10],["search",9]] → [True, False]. Both nodes are kept, and because descend stops before any value that is not smaller, the second 10 is spliced in front of the first on level 0.
• A height of MAX_LEVEL or more: ["insert",1,16] raises IndexError in Python and a TypeError in TypeScript, because update has only 16 entries. Height 15 is the tallest that works; clamp or reject anything above it.
• All heights 0: every node lives on level 0 only, the express lanes stay empty, and each operation is a linear walk, which is the brute force again.
• Values at either end: inserting 1 after 5 finds update equal to head on every level and becomes the first node, so [["insert",5,0],["insert",1,0],["search",1],["search",99]] → [True, False]; the search for 99 ends at the last node, whose successor is None.

Common mistakes

• Not tracking the update/predecessor pointer for each level before splicing.
• Off by one on height: a node at height h lives on levels 0…h, so it needs h + 1 forward pointers and the splice loop is range(height + 1).
• Tracking the current top level instead of always starting at level 15, as the reference does, and forgetting to raise it when a taller node arrives, which leaves the new express lanes unreachable.
• Moving right while the next value is less than or equal to the target: the descent then steps onto the target itself, the level-0 successor is the node after it, and the search reports it missing.

Follow-ups an interviewer asks next

How do you choose heights when they are not given?

Flip coins: start at height 0 and add a level while a random draw is below p, up to MAX_LEVEL - 1. With p = 1/2, a node reaches height k with probability 2^-k, so each level holds about half the nodes below it. Redis uses p = 1/4 and up to 32 levels, which averages about 1.33 forward pointers per node instead of 2.

How would you delete a value?

Run the same descent to fill update. The node to remove is the level-0 successor of update[0], if it holds the value. Then, on every level i where update[i] points at that node, copy the node’s own forward pointer for that level into update[i]. It costs the same expected O(log n) as an insert.

How do you support range queries and rank?

For a range, descend to the first value at or above the low end, then walk level 0 until you pass the high end: O(log n + k) for k results. For rank, store on each forward pointer the number of level-0 nodes it skips, its span, and add the spans along the descent. Redis keeps exactly such spans, which is how ZRANK runs in logarithmic time.

Why are skip lists popular in concurrent code?

An insert only changes the forward pointers next to the new node, one level at a time, so it can be done bottom-up with one compare-and-swap per level, with none of the multi-node rotations a balanced tree needs. Java’s ConcurrentSkipListMap works this way, and LevelDB’s memtable is a skip list that readers traverse without locks while a single writer inserts.

Where this shows up

Skip lists are a simpler, more concurrency-friendly alternative to balanced trees — Redis sorted sets are built on them, and so is LevelDB’s memtable. Their randomized balancing achieves expected O(log n), matching what AVL or red-black trees guarantee in the worst case, without any of the rotation bookkeeping, which is why they are popular in lock-free designs.

Reference solution

MAX_LEVEL = 16

def skiplist_ops(ops):
    # a node is [value, forward-pointers]; the head sentinel has MAX_LEVEL forwards
    head = [None, [None] * MAX_LEVEL]
    out = []

    def descend(value, update=None):
        x = head
        for i in range(MAX_LEVEL - 1, -1, -1):
            while x[1][i] is not None and x[1][i][0] < value:
                x = x[1][i]                 # move right while smaller
            if update is not None:
                update[i] = x               # remember where we dropped down
        return x

    for op in ops:
        if op[0] == "insert":
            value, height = op[1], op[2]
            update = [head] * MAX_LEVEL
            descend(value, update)
            node = [value, [None] * (height + 1)]
            for i in range(height + 1):     # splice in on levels 0..height
                node[1][i] = update[i][1][i]
                update[i][1][i] = node
        else:  # search
            value = op[1]
            x = descend(value)
            nxt = x[1][0]                    # level-0 successor
            out.append(nxt is not None and nxt[0] == value)
    return out


print(skiplist_ops([["insert",5,1],["insert",3,2],["insert",8,0],
                    ["search",3],["search",4],["search",8]]))  # -> [True, False, True]

const MAX_LEVEL = 16;

function skiplistOps(ops: any[][]): boolean[] {
  // a node is { value, forward[] }; the head sentinel has MAX_LEVEL forwards
  const head: any = { value: null, forward: new Array(MAX_LEVEL).fill(null) };
  const out: boolean[] = [];

  function descend(value: number, update: any[] | null): any {
    let x = head;
    for (let i = MAX_LEVEL - 1; i >= 0; i--) {
      while (x.forward[i] !== null && x.forward[i].value < value) x = x.forward[i];
      if (update) update[i] = x;            // remember where we dropped down
    }
    return x;
  }

  for (const op of ops) {
    if (op[0] === "insert") {
      const value = op[1] as number, height = op[2] as number;
      const update = new Array(MAX_LEVEL).fill(head);
      descend(value, update);
      const node: any = { value, forward: new Array(height + 1).fill(null) };
      for (let i = 0; i <= height; i++) {   // splice in on levels 0..height
        node.forward[i] = update[i].forward[i];
        update[i].forward[i] = node;
      }
    } else {                                 // search
      const value = op[1] as number;
      const x = descend(value, null);
      const nxt = x.forward[0];              // level-0 successor
      out.push(nxt !== null && nxt.value === value);
    }
  }
  return out;
}

console.log(skiplistOps([["insert",5,1],["insert",3,2],["insert",8,0],
  ["search",3],["search",4],["search",8]])); // -> [true,false,true]