Take a sorted linked list — slow to search, one step at a time — and add EXPRESS LANES above it: a sparser list that skips ahead, then a sparser one above that. To find a key you ride the top express as far as you can, drop down, ride again — halving the distance each level, like a search tree, but built with simple lists and a coin flip. O(log n), no rebalancing. Slide to search and watch it skip.
A skip list is a sorted linked list with a tower of EXPRESS LANES: level 0 holds all nodes; each higher level keeps a random subset (each node promoted with probability ½), forming logarithmically-spaced shortcuts. Search starts at the top-left, moves right while the next key is ≤ target, drops down a level when it would overshoot, and repeats — halving the remaining span each level for expected O(log n) search, insert, and delete. It matches balanced trees’ performance using only linked lists and randomization, with no rotation/rebalancing (used in Redis sorted sets, LevelDB). A fail-loud self-check throws unless search finds present keys and rejects absent ones. ◆ real data structures, node-verified.
Bounds are EXPECTED (probabilistic, from the coin-flip promotions) — a bad run can be slower, unlike a guaranteed-balanced tree. The express-lane search and O(log n) expectation are exact; the illustration uses fixed lanes for clarity.