Where this fits, next to what you already know
You already have two tools for "keep data ordered and searchable": a balanced BST (Trees topic — AVL/red-black, guaranteed O(log n)) and binary search over a static sorted array (Binary Search topic — O(log n) query, but O(n) to insert). A skip list is a third option that gets you O(log n) search and O(log n) insert/delete, on a plain linked-list-shaped structure, without any tree-rotation logic at all — by leaning on randomization instead of strict rebalancing invariants. It's a genuinely different trade-off, not a strictly worse or better one, and production systems reach for it specifically because it's simpler to implement correctly under concurrency than a rotating balanced tree.
The structure
A skip list is a series of stacked, increasingly sparse sorted linked lists: the bottom level contains every element; each level above it contains a random subset (classically, each element independently "promotes" to the next level up with probability 1/2, giving level sizes n, n/2, n/4, ... — the same halving shape as a balanced binary search tree's height, achieved via coin flips instead of rotations).
import random
class SkipListNode:
def __init__(self, val, level):
self.val = val
self.forward = [None] * (level + 1)
class SkipList:
def __init__(self, max_level=16, p=0.5):
self.max_level = max_level
self.p = p
self.head = SkipListNode(-float("inf"), max_level)
self.level = 0
def _random_level(self):
lvl = 0
while random.random() < self.p and lvl < self.max_level:
lvl += 1
return lvl
def search(self, target):
node = self.head
for i in range(self.level, -1, -1):
while node.forward[i] and node.forward[i].val < target:
node = node.forward[i]
node = node.forward[0]
return node is not None and node.val == target
def insert(self, val):
update = [self.head] * (self.max_level + 1)
node = self.head
for i in range(self.level, -1, -1):
while node.forward[i] and node.forward[i].val < val:
node = node.forward[i]
update[i] = node
new_level = self._random_level()
if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update[i] = self.head
self.level = new_level
new_node = SkipListNode(val, new_level)
for i in range(new_level + 1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_nodeSearch walks "right as far as possible, then down" at each level, starting from the top (sparsest) level — exactly the same divide-and-conquer intuition as binary search, except the "halving" here comes from skipping across a sparser list layer instead of jumping to a array midpoint. Each level you drop down eliminates roughly half the remaining search space, in expectation, giving expected O(log n) search — this is the same idea explicitly referenced back in Binary Search Fundamentals as "a monotonic predicate over an index space," just materialized as a physical data structure instead of an algorithm over an array.
Why "probabilistic balance" instead of strict rebalancing
A balanced BST (AVL, red-black) enforces its height bound with an explicit invariant, checked and repaired (via rotations) on every insert/delete. A skip list gets the same asymptotic height bound (O(log n), with overwhelming probability, not a hard guarantee) purely from the coin-flip promotion rule — insert a new element, flip coins to decide how many levels it appears on, splice it into each of those levels, and never touch any other node in the structure. No rotations, no rebalancing, no cascading updates to any node besides the ones directly adjacent to the new one.
This matters in exactly the place you'd expect: concurrent data structures. Rebalancing a tree touches nodes that are potentially far from the one being inserted, which is painful to make thread-safe without locking large parts of the structure. A skip list's insert only ever touches the nodes it's splicing next to — which is why skip lists (not balanced trees) are the backing structure for several widely used concurrent ordered structures, most notably Redis's Sorted Set (ZSET) and the memtable in several LSM-tree storage engines (LevelDB's original design, and it's the direct inspiration for RocksDB's default memtable implementation) — both contexts where "many concurrent inserts, need ordered range queries" is the exact requirement, and "simple enough to make correctly concurrent" is a real, load-bearing design constraint, not a nice-to-have.
Skip list vs. balanced BST vs. treap — the family resemblance
All three solve "ordered, dynamic set with O(log n) search/insert/delete," and all three get there by injecting some form of balance:
| Balanced BST (AVL/red-black) | Treap | Skip list | |
|---|---|---|---|
| Balance mechanism | Explicit invariant + rotations | Random priority per node + heap-order rotations | Random level per node, no rotations |
| Worst-case height | O(log n), guaranteed | O(log n), with overwhelming probability | O(log n), with overwhelming probability |
| Implementation complexity | Higher (rotation logic) | Medium (rotation logic, but simpler balance condition) | Lower (no rotations at all) |
| Concurrent-friendly? | Hard (rotations touch distant nodes) | Same difficulty as BST | Easier (insert touches only local nodes) |
| Range queries | Yes, via in-order traversal | Yes | Yes, at the bottom (densest) level |
A treap (a binary search tree where each node also carries a random priority, maintained in max-heap order via the same rotation machinery as a balanced BST) is the "middle" option: it gets probabilistic balance like a skip list, but keeps the tree shape and rotation-based rebalancing of a BST. If asked to compare them, the throughline is: all three trade some form of explicit structural guarantee for either simplicity of implementation (skip list) or simplicity of the balance condition itself (treap), while keeping the same O(log n) expected/guaranteed bound.
Practice: Time-Based Key-Value Store
You've already solved Time Based Key-Value Store in the Binary Search topic — it's included there because the per-key lookup is a binary search over a sorted-by-timestamp list of (timestamp, value) pairs. Restated in this subtopic's frame: it's a small, from-scratch instance of exactly the "ordered structure with fast search" requirement this subtopic is about, using a plain sorted list plus binary search rather than a full skip list, because each individual key's version history is appended to in order (timestamps only increase), which sidesteps needing a general-purpose ordered-insert structure at all. If a variant of that problem allowed out-of-order inserts by timestamp, a skip list (or balanced BST/ordered map) would become the right tool, since a plain list's binary search assumes sorted order that an out-of-order insert would break.
Design Skiplist (practice below) asks you to implement the structure directly — search, add, and erase, each expected O(log n) — which is the most direct way to internalize the promotion/splice mechanics above without a comparison problem to lean on.
Complexity summary
| Operation | Skip list (expected) | Balanced BST (guaranteed) |
|---|---|---|
| Search | O(log n) | O(log n) |
| Insert | O(log n) | O(log n) |
| Delete | O(log n) | O(log n) |
| Space | O(n) expected (each element promotes to ~2 levels on average with p=0.5) | O(n) |
Pitfalls and interview gotchas
- Forgetting to update the
update[]array at every level being modified during insert/delete. Splicing a new node into leveliwithout also updating the predecessor pointer at every level0..icorrupts the structure's "each level is a valid sorted sublist" invariant. - Confusing "expected O(log n)" with a hard guarantee. An unlucky sequence of coin flips (very low probability, but non-zero) can in principle produce a lopsided skip list — same caveat as any randomized structure (quickselect, randomized quicksort) covered elsewhere in this roadmap.
- Not capping
max_level. Without a cap, promotion probability compounds indefinitely and a pathological run could allocate unboundedly many levels for a single node — production implementations always cap this (commonlylog2(expected max n)). - Treating a skip list as strictly superior to a balanced BST. It isn't — it trades a hard worst-case guarantee for simpler, more local mutations. If a worst-case bound is a hard requirement (not just "very likely"), a balanced BST is the more defensible choice.
How to talk about this in an interview
"A skip list gets expected O(log n) search and insert on a linked-list-shaped structure by randomly promoting elements to sparser levels above the base list, instead of enforcing a strict rebalancing invariant like a red-black tree does. The appeal in practice is that inserts only ever touch nodes local to the insertion point — no rotations touching distant parts of the structure — which is exactly why Redis's sorted sets and several LSM-tree memtables use skip lists instead of a balanced BST: it's simpler to make correct under concurrent access."
If you get asked to design this as a class, not just an algorithm
The LLD roadmap's Skip List / Ordered Set subtopic picks up exactly where this one leaves off — the class API, an explicit concurrency strategy (per-level locking vs. lock-free), and how to defend a skip list over a balanced BST out loud, the same "DSA algorithm becomes an LLD class" jump the Linked List topic's LRU Cache made.
Further Resources (Optional)
- William Pugh (1990) — Skip Lists: A Probabilistic Alternative to Balanced Trees (the original paper)Reference20m
- GeeksforGeeks — Skip List Data StructureArticle15m
- Redis Documentation — Sorted Sets (ZSET), implemented as a skip list + hash tableReference15m
- VisuAlgo — Skip List (interactive visualization)Reference15m
- NeetCode — Design Skiplist (LC 1206) walkthroughVideo15m
Practice Problems
Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked
- Design SkiplistHard!4/540m
Optional Practice (Extra Reps)
For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.
- Range ModuleHard~4/540m