Skip List - Algorithms

Overview

A Skip List is a probabilistic data structure that allows O(log n) search, insertion, and deletion within an ordered sequence. It achieves this by maintaining multiple layers of linked lists, where each higher layer acts as an "express lane" skipping over elements.

Info

Each node is promoted to the next level with probability p (typically 0.5 or 0.25). With p=0.5, on average half the nodes appear at level 2, quarter at level 3, etc. This creates O(log n) expected levels.

Complexity Analysis

Operation	Average	Worst	Notes
Search	O(log n)	O(n)	Worst case very unlikely
Insert	O(log n)	O(n)	Plus O(level) pointer updates
Delete	O(log n)	O(n)	Simpler than balanced trees
Range Query	O(log n + k)	O(n + k)	k = number of results
Space	O(n) expected (2n with p=0.5)		Extra pointers per level

n = number of elements, k = range query results, p = promotion probability

How It Works

A skip list starts with a sorted linked list at the bottom level. Each element has a random "height" determining how many levels it appears in. Higher levels contain fewer elements, creating express lanes for faster traversal.

Multi-Level Structure Visualization

Search Algorithm

To search for a value, start at the highest level and move right until the next node is greater than the target. Then drop down one level and repeat. Continue until you find the value or reach the bottom level.

Step-by-Step Search

Skip List Search

1function search(target: number): Node | null {2  let current = head;34  // Start from top level, work down5  for (let level = maxLevel; level >= 0; level--) {6    // Move right while next is less than target7    while (current.next[level] &&8           current.next[level].value < target) {9      current = current.next[level];10    }11  }12

Insert Algorithm

Insertion involves finding the position (like search), then randomly determining the height of the new node. Update pointers at each level where the new node appears.

Step-by-Step Insertion with Random Level

Skip List Insert

1function insert(value: number): void {2  const update: Node[] = new Array(maxLevel + 1);3  let current = head;45  // Find insert position at each level6  for (let level = maxLevel; level >= 0; level--) {7    while (current.next[level] &&8           current.next[level].value < value) {9      current = current.next[level];10    }11    update[level] = current;  // Track predecessor12  }

Random Level Generation

Flip a coin (p = 0.5)
Heads: increment level, flip again
Tails: stop, return current level
Cap at maximum level (e.g., 16 for 65536 elements)

Delete Algorithm

Deletion is similar to insertion: find the node and its predecessors, then update pointers to skip over the deleted node at each level.

Skip List Delete

1function delete(value: number): boolean {2  const update: Node[] = new Array(maxLevel + 1);3  let current = head;45  // Find node and track predecessors6  for (let level = maxLevel; level >= 0; level--) {7    while (current.next[level] &&8           current.next[level].value < value) {9      current = current.next[level];10    }11    update[level] = current;12  }

Skip List vs Balanced Trees

Skip List: Probabilistic balance | AVL/Red-Black: Guaranteed balance
Skip List: Simpler implementation | Trees: Complex rotations required
Skip List: Cache-friendly traversal | Trees: Pointer-heavy navigation
Skip List: Easy concurrent access | Trees: Lock contention on rotations
Skip List: O(log n) average case | Trees: O(log n) worst case

Tip

Choose skip lists when you need simpler code, concurrent access, or range queries. Choose balanced trees when you need guaranteed worst-case performance or memory efficiency.

Common Pitfalls

Forgetting to update maxLevel: When highest level becomes empty, reduce maxLevel
Probability p too high: p=0.9 creates very tall lists, wasting memory
Probability p too low: p=0.1 creates very flat lists, losing speed benefits
Not capping maxLevel: With n elements, maxLevel should be approximately log(n)
Ignoring sentinel nodes: Head and tail sentinels simplify edge cases
Relying on worst case: Worst case O(n) is extremely rare with good PRNG

Performance Characteristics

Strengths

Much simpler implementation than AVL/Red-Black trees
No complex rotations needed on insert/delete
Easy to implement lock-free version for concurrent access
Efficient range queries due to linked structure
Good practical performance with small constants

Weaknesses

Theoretical O(n) worst case (though very rare)
Higher memory usage due to multi-level pointers
Depends on quality of random number generator
Worse cache locality than array-based structures

Practical Optimizations

Use p=0.25 instead of 0.5: Fewer levels, saves memory, still O(log n)
$Pre-calculate maxLevel: maxLevel = log_{1/p}(n) for expected n elements
Use memory pool: Reduces memory allocation overhead
Store pointer array contiguously: Improves cache locality

Real-World Usage

Redis: Sorted sets (ZSET) for O(log n) range queries with ZADD, ZRANGE
LevelDB/RocksDB: MemTable index in memory before flushing to SSTable
Apache Lucene: Concurrent skip list for posting lists
MemSQL/SingleStore: Lock-free concurrent skip lists for OLTP
Java ConcurrentSkipListMap: Sorted concurrent map implementation
HBase: MemStore uses ConcurrentSkipListMap

Tip

Redis chose skip list over balanced tree for sorted sets because: (1) Easier to implement and debug, (2) Fast range queries with simple traversal, (3) Tunable by changing p, (4) Antirez (Redis author) found skip lists as fast as balanced trees in practice.

Concurrent Skip List

Skip lists are particularly well-suited for concurrent environments because they can be implemented lock-free. Unlike balanced trees that need to lock multiple nodes during rotations, skip lists only need to update local pointers.

Lock-Free Insert Concept

1function concurrentInsert(value: number): boolean {2  while (true) {3    // Find predecessors (no locks needed for reading)4    const [preds, succs] = findPosition(value);56    // Check if already exists7    if (succs[0]?.value === value) {8      return false;9    }1011    const newLevel = randomLevel();12    const newNode = new Node(value, newLevel);

Info

Java's ConcurrentSkipListMap and ConcurrentSkipListSet use this technique to provide thread-safe sorted collections without global locking.