A skip list keeps a sorted linked list and a stack of sparser express lanes on top. Each inserted key climbs one extra level for every heads flip, so about half the keys have height 1, a quarter have height 2, an eighth have height 3, and so on — giving expected O(log n) search that beats a plain linked list without needing the rotations of a balanced tree. Redis, LevelDB's MemTable, and Java's ConcurrentSkipListMap all ship one.
Yellow tick = geometric expectation n · p^(h-1) · (1 − p).
visited on search path match just inserted
A sorted linked list gives O(n) search — no way to binary-chop into pointer chases. A skip list bolts on express lanes: level 1 is the base list, level 2 links roughly every second node, level 3 every fourth, and so on. On lookup you start at the top-left header and repeatedly step right while the next key stays ≤ target, dropping down whenever the next key overshoots. Because each node's height is a fresh Geometric(1 − p) draw with p usually 1/2, the expected number of hops is log_{1/p} n — the same asymptotic as a balanced tree but with no rotations, no colour bits, no rebalancing math. Redis' sorted sets and ZooKeeper's snapshot index both use skip lists because concurrent writers get much simpler lock-free updates than a red-black tree can offer.