Skip Lists — Probabilistic Balanced Structure

0/12 in this phase0/57 across the roadmap

📖 Concept

A skip list is a probabilistic data structure that provides O(log n) search, insert, and delete — like a balanced BST but simpler to implement.

How it works:

Multiple layers of sorted linked lists
Bottom layer: all elements
Each higher layer: a random subset (~50%) of the layer below
Search: start from top layer, move right, drop down when you overshoot

Visualization:

Level 3: HEAD ---------> 25 -------------------> NIL
Level 2: HEAD ------> 10 -> 25 ---------> 50 -> NIL
Level 1: HEAD -> 5 -> 10 -> 25 -> 30 -> 50 -> NIL
Level 0: HEAD -> 3 -> 5 -> 10 -> 15 -> 25 -> 30 -> 42 -> 50 -> NIL

Operations — all O(log n) expected:

Search: Start top-left, go right until overshooting, go down
Insert: Find position, flip coin for height, insert at each level
Delete: Find all references, remove from each level

Skip List vs Balanced BST:

Feature	Skip List	AVL/Red-Black
Complexity	O(log n) expected	O(log n) guaranteed
Code complexity	Simple	Very complex
Space	O(n) extra pointers	O(n)
Range queries	Easy (follow links)	Need inorder traversal
Concurrency	Easy to lock-free	Very hard
Used in	Redis, LevelDB	Java TreeMap, C++ std::map

🏠 Real-world analogy: Express vs local subway lines. The express line (top layer) has fewer stops and gets you close fast. Then you switch to the local line (bottom layer) for the exact stop. Multiple express lines with different densities speed things up.

💻 Code Example

codeTap to expand ⛶

1// SKIP LIST — Implementation
2class SkipNode {
3  constructor(val = -Infinity, level = 0) {
4    this.val = val;
5    this.forward = new Array(level + 1).fill(null); // Pointers at each level
6  }
7}
8
9class SkipList {
10  constructor(maxLevel = 16, p = 0.5) {
11    this.maxLevel = maxLevel;
12    this.p = p; // Probability of promoting to next level
13    this.level = 0; // Current max level in use
14    this.head = new SkipNode(-Infinity, maxLevel);
15  }
16
17  randomLevel() {
18    let lvl = 0;
19    while (Math.random() < this.p && lvl < this.maxLevel) lvl++;
20    return lvl;
21  }
22
23  search(target) {
24    let curr = this.head;
25    for (let i = this.level; i >= 0; i--) {
26      while (curr.forward[i] && curr.forward[i].val < target) {
27        curr = curr.forward[i]; // Move right at current level
28      }
29      // Drop down to next level
30    }
31    curr = curr.forward[0]; // At level 0, check exact match
32    return curr && curr.val === target ? curr : null;
33  }
34
35  insert(val) {
36    const update = new Array(this.maxLevel + 1).fill(null);
37    let curr = this.head;
38
39    // Find position at each level
40    for (let i = this.level; i >= 0; i--) {
41      while (curr.forward[i] && curr.forward[i].val < val) {
42        curr = curr.forward[i];
43      }
44      update[i] = curr; // Track rightmost node at each level before insertion point
45    }
46
47    const newLevel = this.randomLevel();
48    if (newLevel > this.level) {
49      for (let i = this.level + 1; i <= newLevel; i++) {
50        update[i] = this.head;
51      }
52      this.level = newLevel;
53    }
54
55    const newNode = new SkipNode(val, newLevel);
56    for (let i = 0; i <= newLevel; i++) {
57      newNode.forward[i] = update[i].forward[i];
58      update[i].forward[i] = newNode;
59    }
60  }
61
62  delete(val) {
63    const update = new Array(this.maxLevel + 1).fill(null);
64    let curr = this.head;
65
66    for (let i = this.level; i >= 0; i--) {
67      while (curr.forward[i] && curr.forward[i].val < val) {
68        curr = curr.forward[i];
69      }
70      update[i] = curr;
71    }
72
73    curr = curr.forward[0];
74    if (!curr || curr.val !== val) return false;
75
76    for (let i = 0; i <= this.level; i++) {
77      if (update[i].forward[i] !== curr) break;
78      update[i].forward[i] = curr.forward[i];
79    }
80
81    while (this.level > 0 && !this.head.forward[this.level]) {
82      this.level--;
83    }
84    return true;
85  }
86}
87
88// USAGE
89const sl = new SkipList();
90[3, 6, 7, 9, 12, 19, 17, 26, 21, 25].forEach(v => sl.insert(v));
91console.log(sl.search(19)); // Found: SkipNode(19)
92console.log(sl.search(15)); // null
93sl.delete(19);
94console.log(sl.search(19)); // null

🏋️ Practice Exercise

Practice Problems:

Implement a basic skip list with search, insert, and delete
Visualize skip list construction with random levels
Analyze the expected space complexity of a skip list
Implement range query in a skip list (find all elements between lo and hi)
Compare skip list performance vs balanced BST empirically
Implement a concurrent skip list (conceptual — explain lock-free approach)
Design an LRU cache using a skip list for O(log n) eviction by time
Why does Redis use skip lists instead of Red-Black trees?
Implement a skip list with a custom comparator for string elements
Compare skip list vs B-tree for disk-based storage

⚠️ Common Mistakes

Not understanding probabilistic guarantees — O(log n) is expected, not worst-case guaranteed
Using too many levels — maxLevel = log₂(n) is sufficient; more wastes space
Not handling the update array correctly during insertion — must track predecessors at all levels
Comparing skip lists only to arrays — compare to balanced BSTs for a fair assessment
Forgetting that skip lists excel at concurrent access — this is a major real-world advantage

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Skip Lists — Probabilistic Balanced Structure

Was this topic helpful?

← PreviousBloom Filters & Probabilistic Data Structures Next →Monotonic Stack & Monotonic Queue