Skip lists

Balanced-tree O(log n) from linked lists and coin flips. No rotations — randomization does the balancing.

Express lanes

• Bottom lane: full sorted linked list (level 0)
• Above: sparser lanes, each ~half as dense
• Search: ride a lane right until the next node overshoots, drop down
• Each drop halves the remaining span → O(log n)

Watch the search descend

Search 23: ride the top lane right, drop down near the target. Found it visiting 3 nodes out of 10 — a staircase, like binary search.

O(log n) vs O(n)

100k elements: linked list 48,000 steps, skip list 32 → 1,500× fewer. Same as a balanced tree.

Randomized heights

• Insert: coin-flip the height (promote with prob ½, repeat)
• Half at level 0, quarter reach level 1, eighth level 2 → geometric
• Nothing is ever moved → no rebalancing, no rotation cases
• EXPECTED O(log n); no adversarial input forces the worst case

Takeaway

Randomness replaces cleverness — code a fraction of AVL/red-black size, easy concurrency. Redis sorted sets, LevelDB memtables, Java ConcurrentSkipListMap. Next: LRU cache — hash map + doubly-linked list = O(1).