What is a skip list and how does it achieve O(log n) search?

Question

Accepted Answer

A **skip list** is an ordered linked list augmented with multiple **"express lane"** levels. Higher levels skip over many nodes, so search descends and moves right, achieving **O(log n)** expected time — like a probabilistic, simpler alternative to a balanced tree. ## Structure ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` Each node is promoted to higher levels with probability `p` (often 0.5), so on average each level has half as many nodes as the one below. ## Search ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## Complexity | Operation | Expected | Space | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Trade-offs vs balanced trees - **Strengths:** much simpler to implement than red-black/AVL; no rotations; easy concurrent versions (used in Redis sorted sets, Java `ConcurrentSkipListMap`). - **Weaknesses:** probabilistic guarantees (not worst-case); extra pointers per node. ## Why it matters Skip lists deliver tree-like O(log n) ordered operations with far less code and easy lock-free concurrency, which is why real systems like Redis choose them. They are a great example of using **randomization** to replace complex deterministic balancing logic.