Skip List
Layered linked list with express lanes — coin flips decide how tall each tower gets.
How It Works
A skip list is a sorted linked list with extra layers. The bottom level (level 0) contains every element in order. Higher levels act as "express lanes" that skip over elements, letting you jump ahead quickly during a search.
When you insert a node, you flip a coin to decide its height. Heads means go up another level, tails means stop. This randomness gives the structure its balance without any of the rotation machinery that balanced binary search trees need.
To search, you start at the top-left and scan right. When the next node's key is too large (or you hit the end), you drop down a level and keep going. Each level roughly halves the number of nodes you have to look at, giving O(log n) expected time.
Why O(log n)
With probability p = 0.5, about half the nodes reach level 1, a quarter reach level 2, and so on. The number of levels is roughly log₂(n). At each level, you skip over about half the remaining elements before dropping down. The analysis is similar to binary search, just probabilistic instead of deterministic.
Comparison with Balanced BSTs
Red-black trees and AVL trees guarantee O(log n) worst-case through rotations and color/balance invariants. Skip lists get the same expected performance with a much simpler implementation. No rotations, no rebalancing, no complex invariants to maintain. The trade-off: skip lists use more memory (the extra pointers at higher levels) and their performance is expected rather than guaranteed.
Where skip lists really shine is concurrency. Inserting into a skip list only requires local changes to a few pointers at each level. Compare that to tree rotations that can restructure large subtrees. Java's ConcurrentSkipListMap exists precisely because skip lists are easier to make lock-free.
Where They Show Up
Redis sorted sets are backed by skip lists. When you run ZADD or ZRANGEBYSCORE, you're operating on a skip list. LevelDB and RocksDB use skip lists for their in-memory write buffers (MemTables) before flushing to disk. Java's ConcurrentSkipListMap and ConcurrentSkipListSet provide thread-safe sorted collections.
The p Parameter
The probability of promoting a node to the next level is usually 0.5 (coin flip) or 0.25. Lower p means fewer nodes at higher levels, which saves memory but makes searches slightly longer. Redis uses p = 0.25 with a max level of 32. The original paper by William Pugh (1990) analyzed both choices and found p = 0.25 is a good space-time trade-off in practice.