Skip List

How a skip list works

Imagine a sorted linked list. Each node points to the next. Searching for an item takes O(n) — walk from the start to the target. To speed this up, add an "express layer" on top: every other node has a forward pointer that skips over its neighbor.

Level 2: 1 -----------> 5 -----------> 9
Level 1: 1 ----> 3 ----> 5 ----> 7 ----> 9
Level 0: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

Searching for 7: start at the top. Go right at level 2 from 1 to 5; the next is 9, too big — drop down. At level 1 from 5, next is 7 — found.

That's two hops at level 2 plus one at level 1 instead of seven hops at level 0. With more levels, we save more.

The trick: random level assignment. Each new node decides its height by flipping coins. With probability 1/2 the node gets height 1; with 1/4 it gets 2; with 1/8 it gets 3; and so on. No global rebalancing needed — randomness alone keeps the structure balanced in expectation.

Searching the skip list

The search is the same idea at every level: go right while the next key is ≤ target, drop down when it's not.

function search(head, target) {
  let node = head;
  // Start at the highest level and walk down
  for (let level = head.maxLevel; level >= 0; level--) {
    while (node.forward[level] !== null && node.forward[level].key <= target) {
      node = node.forward[level];
    }
  }
  return node.key === target ? node.value : null;
}

Each level traversal halves the expected remaining range. After O(log n) levels and O(1) hops per level, we've narrowed in on the target.

Skip list vs balanced BSTs and hash tables

	Skip list	Red-black tree	Hash table
Lookup	O(log n) expected	O(log n) worst case	O(1) average, O(n) worst
Insert / delete	O(log n) expected	O(log n) worst case	O(1) average
Range queries	O(log n + k) — natural	O(log n + k) — in-order traversal	Not supported
Memory overhead	~2 pointers per element	2 pointers + color bit per element	Higher (sparse buckets)
Cache locality	Poor (linked structure)	Poor (linked structure)	Excellent (open addressing) or poor (chaining)
Concurrency	Easy — lock-free with CAS	Hard — multi-node locks	Easy — per-bucket locks
Implementation complexity	~80 lines	~250 lines	~50 lines (basic), ~200 (concurrent)
Best for	Concurrent ordered maps	Single-threaded ordered maps	Point queries, no ordering

For single-threaded code with ordered access, RB tree is the standard library default. For concurrent code, skip list dominates. For point-query-only data, hash table wins.

When to use a skip list

• Concurrent ordered maps. Java's ConcurrentSkipListMap, .NET's ConcurrentDictionary's ordered counterparts, Redis sorted sets — all use skip lists because lock-free implementations are tractable.
• Range queries on sorted data. Like B+trees and ordered BSTs, skip lists support O(log n + k) range scans. Walk down to the start, walk forward at level 0 until you reach the end of the range.
• Persistent on-disk indexes (sometimes). LevelDB and RocksDB use skip lists in their in-memory write buffer (memtable) before flushing to disk. The lock-free property matters when many writes hit the buffer concurrently.
• Education. Skip lists are dramatically easier to implement than balanced trees and use much simpler proof techniques. Often taught alongside or instead of red-black trees in algorithms courses.

JavaScript implementation

const MAX_LEVEL = 16;
const P = 0.5;

class SkipNode {
  constructor(key, value, level) {
    this.key = key;
    this.value = value;
    this.forward = new Array(level + 1).fill(null);
  }
}

class SkipList {
  constructor() {
    this.head = new SkipNode(-Infinity, null, MAX_LEVEL);
    this.level = 0;
  }

  randomLevel() {
    let lvl = 0;
    while (Math.random() < P && lvl < MAX_LEVEL) lvl++;
    return lvl;
  }

  search(key) {
    let node = this.head;
    for (let i = this.level; i >= 0; i--) {
      while (node.forward[i] && node.forward[i].key < key) {
        node = node.forward[i];
      }
    }
    node = node.forward[0];
    return (node && node.key === key) ? node.value : undefined;
  }

  insert(key, value) {
    const update = new Array(MAX_LEVEL + 1).fill(this.head);
    let node = this.head;

    for (let i = this.level; i >= 0; i--) {
      while (node.forward[i] && node.forward[i].key < key) {
        node = node.forward[i];
      }
      update[i] = node;
    }

    node = node.forward[0];
    if (node && node.key === key) {
      node.value = value;  // update existing
      return;
    }

    const lvl = this.randomLevel();
    if (lvl > this.level) {
      for (let i = this.level + 1; i <= lvl; i++) update[i] = this.head;
      this.level = lvl;
    }

    const newNode = new SkipNode(key, value, lvl);
    for (let i = 0; i <= lvl; i++) {
      newNode.forward[i] = update[i].forward[i];
      update[i].forward[i] = newNode;
    }
  }

  delete(key) {
    const update = new Array(MAX_LEVEL + 1).fill(null);
    let node = this.head;

    for (let i = this.level; i >= 0; i--) {
      while (node.forward[i] && node.forward[i].key < key) {
        node = node.forward[i];
      }
      update[i] = node;
    }

    node = node.forward[0];
    if (!node || node.key !== key) return false;

    for (let i = 0; i <= this.level; i++) {
      if (update[i].forward[i] !== node) break;
      update[i].forward[i] = node.forward[i];
    }

    while (this.level > 0 && this.head.forward[this.level] === null) this.level--;
    return true;
  }

  // Range scan: collect all (key, value) with key in [lo, hi]
  range(lo, hi) {
    let node = this.head;
    for (let i = this.level; i >= 0; i--) {
      while (node.forward[i] && node.forward[i].key < lo) {
        node = node.forward[i];
      }
    }
    const result = [];
    node = node.forward[0];
    while (node && node.key <= hi) {
      result.push([node.key, node.value]);
      node = node.forward[0];
    }
    return result;
  }
}

Why skip lists work — the probabilistic argument

Each node's height is geometrically distributed: P(height ≥ k) = 1/2^(k-1). The expected number of nodes at height k or higher is n / 2^(k-1). The maximum height is therefore O(log n) with high probability.

For a search: at each level, we traverse on average 2 forward pointers before dropping down. With O(log n) levels and 2 traversals per level, the total traversal is O(log n). The probability of significantly worse performance drops exponentially.

This is the same probabilistic argument behind hash tables — the worst case is bad but vanishingly rare. Unlike hash tables, skip lists guarantee O(log n) at the algorithmic level (not O(1)) — they're "balanced trees" in spirit.

Famous skip list deployments

• Redis sorted sets (ZSET). Each ZSET is a skip list keyed on score, with a hash map keyed on member for O(1) member-to-score lookup. Range queries on score (ZRANGEBYSCORE) traverse the level-0 list. Trivial to implement, fast in practice.
• Java's ConcurrentSkipListMap and ConcurrentSkipListSet. Lock-free ordered map. Used in concurrent code where the sorted-iteration property of TreeMap is needed but rebalancing locks would kill throughput.
• LevelDB and RocksDB memtables. Both store recent writes in an in-memory skip list before flushing to disk-resident SSTables. Concurrent writers can insert without coordination.
• Lucene's segment merging. Lucene uses skip lists in some posting list encodings to speed up multi-term query intersection.

Common skip list bugs

• Wrong update array size. The update array tracks the predecessor at each level. It must be sized to the maximum level the new node could reach — usually MAX_LEVEL, not the current tree's level.
• Forgetting to update the tree's level field. If a new node has a higher level than the current tree, you must increase the tree's level field (and initialize the new high-level pointers).
• Inconsistent random number generator. Using a poor RNG (Math.random in some browsers used to be biased) can cluster heights and degrade performance. For production, use a CSPRNG or at least Mulberry32.
• Memory leaks on delete. In manual-memory languages, deleted nodes must be freed. In garbage-collected languages, just dropping references is enough — but make sure no level still has a forward pointer to the deleted node.
• Concurrent skip list bugs. Lock-free skip lists are deceptively complex — getting the deletion order right (mark before unlink, ABA prevention) is hard. Use Java's ConcurrentSkipListMap or a vetted library; don't write your own concurrent version.