Layered linked lists
A skip list is a sorted linked list with extra express lanes stacked above it. Higher levels skip over many nodes so a search can descend quickly, much like a balanced tree but built from simple lists.
Randomized heights
When a node is inserted, its height is decided by coin flips. Keep flipping while you get heads, raising the node one level each time, and stop on the first tails.
- About half the nodes reach level one.
- About a quarter reach level two, and so on.
This geometric distribution gives a logarithmic number of levels without any rebalancing rotations.
Searching
Start at the top left and move right while the next node is not too large, then drop down a level when it is. Repeat until you reach the bottom, where the target sits or is absent.
Why it is appealing
Expected search, insert, and delete all run in logarithmic time. There is no complex balancing code, only local pointer updates and a random level, which makes skip lists a favorite for concurrent and ordered map implementations.
Key idea
A skip list adds randomly tall express lanes above a sorted list using coin flips for node height, giving expected logarithmic search and update with simple pointer code instead of tree rotations.