Pattern: Skip List

Advanced

One Liner

A probabilistic sorted data structure with O(log n) search, insert, and delete — simpler to implement than balanced trees with comparable performance.

▶ Interactive Demo ↓

Real-World Analogy

An express train system with local and express stops. The express line skips most stations, letting you jump ahead quickly. Once you're close to your destination, you switch to the local line for precise stops. Multiple express levels speed up long searches.

Core Idea

A skip list is a multi-level linked list where each level skips over more elements. The bottom level is a regular sorted linked list. Higher levels act as "express lanes" that allow binary-search-like behavior. Each node is randomly promoted to higher levels with probability p (typically 0.5).

  Level 3:  HEAD ─────────────────────────────── 30 ─ NIL
              │                                  │
  Level 2:  HEAD ─────── 10 ──────────────────── 30 ─ NIL
              │           │                      │
  Level 1:  HEAD ── 5 ── 10 ──── 20 ──────────── 30 ─ NIL
              │     │     │       │              │
  Level 0:  HEAD  3  5  7  10  15  20  25  30 ─ NIL
              │   │  │  │   │   │   │   │   │
              ▼   ▼  ▼  ▼   ▼   ▼   ▼   ▼   ▼

  Search(15): L3→30(far)↓ L2→10→30(far)↓ L1→20(far)↓ L0→15 ✓

Property	Value
Search	O(log n) average
Insert	O(log n) average
Delete	O(log n) average
Space	O(n) expected
Advantage	Simpler than red-black/AVL trees, lock-free variants possible

Try it yourself — insert values and search to see how express lanes speed up traversal:

Production Proof

Project	Source	Usage
Redis	t_zset.c#L70-L130	zskiplist / zskiplistNode — Redis sorted sets use a skip list (not a balanced tree) for O(log n) range queries. zslInsert creates nodes with random levels. Chosen by Antirez for its simplicity and cache-friendliness.
LevelDB	skiplist.h#L40-L90	SkipList class template — used as the in-memory sorted structure (MemTable) for LevelDB. Insert and Contains with compare-and-swap for concurrent reads. Foundation of LSM-tree architecture.

Implementation

TypeScript

class SkipNode {
  forward: (SkipNode | null)[];
  constructor(public key: number, public value: string, level: number) {
    this.forward = new Array(level + 1).fill(null);
  }
}

class SkipList {
  private maxLevel = 16;
  private level = 0;
  private header = new SkipNode(-Infinity, '', 16);

  private randomLevel(): number {
    let lvl = 0;
    while (lvl < this.maxLevel && Math.random() < 0.5) lvl++;
    return lvl;
  }

  insert(key: number, value: string): void {
    const update: (SkipNode | null)[] = new Array(this.maxLevel + 1).fill(null);
    let cur = this.header;
    for (let i = this.level; i >= 0; i--) {
      while (cur.forward[i] && cur.forward[i]!.key < key) cur = cur.forward[i]!;
      update[i] = cur;
    }
    if (cur.forward[0]?.key === key) { cur.forward[0]!.value = value; return; }
    const newLvl = this.randomLevel();
    if (newLvl > this.level) {
      for (let i = this.level + 1; i <= newLvl; i++) update[i] = this.header;
      this.level = newLvl;
    }
    const node = new SkipNode(key, value, newLvl);
    for (let i = 0; i <= newLvl; i++) {
      node.forward[i] = update[i]!.forward[i];
      update[i]!.forward[i] = node;
    }
  }

  search(key: number): string | undefined {
    let cur = this.header;
    for (let i = this.level; i >= 0; i--) {
      while (cur.forward[i] && cur.forward[i]!.key < key) cur = cur.forward[i]!;
    }
    return cur.forward[0]?.key === key ? cur.forward[0]!.value : undefined;
  }
}

Rust

const MAX_LEVEL: usize = 4;

struct SkipNode {
    key: i64,
    value: String,
    forward: Vec<Option<usize>>,
}

pub struct SkipList {
    nodes: Vec<SkipNode>,
    head: usize,
    level: usize,
    seed: u64,
}

impl SkipList {
    pub fn new() -> Self {
        let head = SkipNode { key: i64::MIN, value: String::new(), forward: vec![None; MAX_LEVEL] };
        SkipList { nodes: vec![head], head: 0, level: 0, seed: 42 }
    }

    fn random_level(&mut self) -> usize {
        let mut lvl = 0;
        while lvl < MAX_LEVEL - 1 {
            self.seed ^= self.seed << 13;
            self.seed ^= self.seed >> 7;
            self.seed ^= self.seed << 17;
            if self.seed % 2 == 0 { lvl += 1; } else { break; }
        }
        lvl
    }

    pub fn insert(&mut self, key: i64, value: &str) {
        let mut update = [0usize; MAX_LEVEL];
        let mut cur = self.head;
        for i in (0..=self.level).rev() {
            while let Some(nx) = self.nodes[cur].forward[i] {
                if self.nodes[nx].key < key { cur = nx; } else { break; }
            }
            update[i] = cur;
        }
        if let Some(nx) = self.nodes[cur].forward[0] {
            if self.nodes[nx].key == key {
                self.nodes[nx].value = value.to_string();
                return;
            }
        }
        let lvl = self.random_level();
        if lvl > self.level {
            for i in (self.level + 1)..=lvl { update[i] = self.head; }
            self.level = lvl;
        }
        let idx = self.nodes.len();
        self.nodes.push(SkipNode { key, value: value.to_string(), forward: vec![None; lvl + 1] });
        for i in 0..=lvl {
            self.nodes[idx].forward[i] = self.nodes[update[i]].forward[i];
            self.nodes[update[i]].forward[i] = Some(idx);
        }
    }

    pub fn search(&self, key: i64) -> Option<&str> {
        let mut cur = self.head;
        for i in (0..=self.level).rev() {
            while let Some(nx) = self.nodes[cur].forward[i] {
                if self.nodes[nx].key < key { cur = nx; } else { break; }
            }
        }
        if let Some(nx) = self.nodes[cur].forward[0] {
            if self.nodes[nx].key == key { return Some(&self.nodes[nx].value); }
        }
        None
    }
}

Go

type SkipNode struct {
	key     int
	value   string
	forward []*SkipNode
}

type SkipList struct {
	header   *SkipNode
	level    int
	maxLevel int
}

func NewSkipList() *SkipList {
	header := &SkipNode{forward: make([]*SkipNode, 17)}
	return &SkipList{header: header, maxLevel: 16}
}

func (sl *SkipList) Insert(key int, value string) {
	update := make([]*SkipNode, sl.maxLevel+1)
	cur := sl.header
	for i := sl.level; i >= 0; i-- {
		for cur.forward[i] != nil && cur.forward[i].key < key {
			cur = cur.forward[i]
		}
		update[i] = cur
	}
	if cur.forward[0] != nil && cur.forward[0].key == key {
		cur.forward[0].value = value
		return
	}
	lvl := 0
	for lvl < sl.maxLevel && rand.Float64() < 0.5 {
		lvl++
	}
	if lvl > sl.level {
		for i := sl.level + 1; i <= lvl; i++ {
			update[i] = sl.header
		}
		sl.level = lvl
	}
	node := &SkipNode{key: key, value: value, forward: make([]*SkipNode, lvl+1)}
	for i := 0; i <= lvl; i++ {
		node.forward[i] = update[i].forward[i]
		update[i].forward[i] = node
	}
}

func (sl *SkipList) Search(key int) (string, bool) {
	cur := sl.header
	for i := sl.level; i >= 0; i-- {
		for cur.forward[i] != nil && cur.forward[i].key < key {
			cur = cur.forward[i]
		}
	}
	if cur.forward[0] != nil && cur.forward[0].key == key {
		return cur.forward[0].value, true
	}
	return "", false
}

Python

import random

class SkipNode:
    def __init__(self, key: int, value: str, level: int):
        self.key = key
        self.value = value
        self.forward: list[SkipNode | None] = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level: int = 16, p: float = 0.5):
        self.max_level = max_level
        self.p = p
        self.level = 0
        self.header = SkipNode(-1, '', max_level)

    def _random_level(self) -> int:
        lvl = 0
        while lvl < self.max_level and random.random() < self.p:
            lvl += 1
        return lvl

    def insert(self, key: int, value: str) -> None:
        update = [self.header] * (self.max_level + 1)
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] and cur.forward[i].key < key:
                cur = cur.forward[i]
            update[i] = cur
        if cur.forward[0] and cur.forward[0].key == key:
            cur.forward[0].value = value
            return
        lvl = self._random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.header
            self.level = lvl
        node = SkipNode(key, value, lvl)
        for i in range(lvl + 1):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node

    def search(self, key: int) -> str | None:
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] and cur.forward[i].key < key:
                cur = cur.forward[i]
        if cur.forward[0] and cur.forward[0].key == key:
            return cur.forward[0].value
        return None

Exercises

Level	Exercise	File
Basic	Implement a skip list with insert/search/delete	exercises/typescript/skip-list/01-basic.test.ts
Intermediate	Skip list with range query	exercises/typescript/skip-list/02-intermediate.test.ts

Run exercises: pnpm test:exercises (TypeScript) · cargo test (Rust) · go test ./... (Go) · pytest (Python)

Exercise files: Rust exercises/rust/src/skip_list/mod.rs · Go exercises/go/skip_list/skip_list_test.go · Python exercises/python/skip_list/test_skip_list.py

When to Use

• In-memory sorted storage — when you need sorted iteration + fast point lookups (Redis sorted sets)
• Concurrent data structures — lock-free skip lists are simpler than lock-free balanced trees
• Database memtables — in-memory write buffer before flushing to disk (LevelDB, RocksDB)
• Range queries — efficient range scans on sorted data

When NOT to Use

• Pure key-value lookup — hash maps are O(1) average vs skip list's O(log n)
• Deterministic performance needed — skip list has probabilistic guarantees, not worst-case
• Memory-constrained — forward pointer arrays use more memory than a balanced tree
• Persistent storage — B-trees are better optimized for disk I/O patterns

More Production Uses

• RocksDB — InlineSkipList for concurrent MemTable
• CockroachDB — skip list-based memtable for Pebble storage engine
• Java ConcurrentSkipListMap — lock-free sorted map in JDK
• FoundationDB — skip list for in-memory sorted data

Related Patterns

Pattern	Relationship
LSM Tree (Log-Structured Merge Tree)	LSM trees use skip lists as their in-memory sorted buffer (memtable)
B+ Tree	B+ trees guarantee O(log n); skip lists achieve it probabilistically with simpler code
Bloom Filter	Both are probabilistic — bloom filters for membership, skip lists for ordering
Free List	Skip list nodes need allocation management; free lists provide O(1) alloc for fixed-size nodes
Merge Iterator	Merge iterators combine sorted output from multiple skip list levels or instances
Trie (Prefix Tree)	Both provide ordered key traversal — skip lists via probabilistic balance, tries via prefix structure

Challenge Questions

Q1: A skip list uses Math.random() to decide node promotion levels. Your colleague argues this makes skip list performance "unreliable" since a bad random sequence could produce O(n) search. Is this a real concern in production?

Answer: In theory yes, but in practice the probability is astronomically low — comparable to a hash table degenerating to O(n) from collisions.

With promotion probability p=0.5, the chance of a node reaching level k is (1/2)^k. The expected maximum level for n elements is O(log n). For a skip list to degrade to O(n), a large fraction of nodes would need to be at level 0 only — an event with probability so close to zero it's practically impossible. Redis chose skip lists over red-black trees for this reason: the average-case guarantees are strong enough, and the implementation is dramatically simpler. LevelDB uses skip lists for the same reasoning.

Q2: Redis uses a skip list (not a red-black tree or B-tree) for sorted sets. Both skip lists and balanced BSTs offer O(log n) operations. What makes skip lists preferable for Redis's use case?

Answer: Skip lists are simpler to implement correctly, support efficient range queries by following forward pointers, and are easier to make lock-free for concurrent access.

In a balanced BST, range queries require an in-order traversal that bounces between parent and child pointers. In a skip list, once you find the range start at level 0, you simply follow forward pointers — sequential and cache-friendly. Additionally, lock-free skip list algorithms (used in LevelDB and ConcurrentSkipListMap) are well-understood, while lock-free balanced tree algorithms are notoriously complex. Antirez (Redis creator) also cited implementation simplicity: skip list insert/delete code is straightforward compared to red-black tree rotations.

Q3: LevelDB's skip list supports concurrent reads without locks but requires external synchronization for writes. Why not make writes lock-free too?

Answer: LevelDB only has one writer thread (the memtable writer), so lock-free writes add complexity without benefit — the design constraint is concurrent readers, not concurrent writers.

LevelDB's LSM-tree architecture funnels all writes through a single write-ahead log and then into the memtable. Since there's only one writer, a mutex is trivial and adds no contention. The skip list uses atomic operations for the forward pointers so that the single writer and multiple reader threads can operate simultaneously without read locks. This is the SWMR (single-writer, multiple-reader) insight: optimize for the actual concurrency pattern, not the general case.

Q4: You're implementing a skip list for a leaderboard that needs the top-100 players by score. A naive approach iterates from the head of level 0. Your colleague says "just maintain a pointer to the tail for reverse iteration." Why doesn't this work as easily as it does in a doubly-linked list?

Answer: Skip lists are inherently forward-only structures. Adding backward pointers at every level doubles the pointer count and complicates insertion/deletion, negating the simplicity advantage over balanced trees.

In a doubly-linked list, maintaining a tail pointer and iterating backward is trivial. In a skip list, you'd need backward pointers at every level to get O(log n) reverse traversal — otherwise you'd fall back to O(n) at level 0. This essentially turns the skip list into a bidirectional skip list, which is significantly more complex. The practical solution for "top-K" queries is to store scores negated (or use a reverse comparator) so that the highest scores sort first, then iterate forward from the head. Redis sorted sets take this approach with ZREVRANGE by walking forward pointers on a skip list that supports both directions at level 0 only.