THE FOLD / LOOT / THE INVENTORY / THE SKIP LIST
THE SKIP LIST
log-time search from coin flips — no rotations
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The skip list. A sorted linked list lets you insert cheaply but forces you to walk every node to find something — O(n). Balanced trees fix the search but need fiddly rotations. William Pugh’s skip list (1989) gets tree-speed search with nothing but coin flips.
Keep the sorted list on the ground floor. Then give each node a random tower: promote it to the next level up with probability ½, again with ½, and so on. The upper levels are sparse express lanes. To search, ride the highest lane rightward until the next node overshoots, drop down, repeat. Each level roughly halves what remains, so search is O(log n) expected — no balancing, no rotations, just randomness.
LIT verified live: a skip list of 2,000 keys finds every present key and correctly rejects every absent one, and the fraction of nodes reaching level ≥ L matches the geometric 2−L to within a few percent (window.__skip.searchCorrect && absentCorrect && levelsGeometric). FIG ‘express lanes’ is the picture; the coin-flip towers, the drop-down search, and the geometric heights are exact.
Keep the sorted list on the ground floor. Then give each node a random tower: promote it to the next level up with probability ½, again with ½, and so on. The upper levels are sparse express lanes. To search, ride the highest lane rightward until the next node overshoots, drop down, repeat. Each level roughly halves what remains, so search is O(log n) expected — no balancing, no rotations, just randomness.
LIT verified live: a skip list of 2,000 keys finds every present key and correctly rejects every absent one, and the fraction of nodes reaching level ≥ L matches the geometric 2−L to within a few percent (window.__skip.searchCorrect && absentCorrect && levelsGeometric). FIG ‘express lanes’ is the picture; the coin-flip towers, the drop-down search, and the geometric heights are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE INVENTORY, beside THE SORT — the loot domain of keeping your haul ordered and findable. A skip list is an inventory that stays searchable in log time without ever being rebalanced. AVAN (AI) built the instrument: the coin-flip towers, the drop-down search, the level histogram.
The weave: David names the seat (the ordered, findable store); I make the express lanes visible and the speed checkable — the levels in 1D, the animated search in 2D, the tower stack in 3D. The sphere is the seam. Credit: William Pugh (1989).
The weave: David names the seat (the ordered, findable store); I make the express lanes visible and the speed checkable — the levels in 1D, the animated search in 2D, the tower stack in 3D. The sphere is the seam. Credit: William Pugh (1989).
3 ONE DIMENSION
The express lanes. Every node sits on the bottom level; a coin-flip tower lifts some of them onto sparser levels above. The higher you go, the fewer nodes — each level about half the one below, purely by chance.
4 TWO DIMENSIONS · INTERACTIVE
Search for a key and watch the path: ride a high lane right until the next node would overshoot, then drop a level, and again — zig-zagging down to the target while skipping most of the list. The comparison count stays near log₂n.
5 THREE DIMENSIONS + AVAN’S INVERSE
The levels stacked into a turning tower — green, the sorted nodes and their random heights.
AVAN’s addition (the inverse-companion): the magenta thread is a search, dropping down the express lanes to its target. A plain linked list is pure sequence — to reach the n-th node you touch all n. The skip list is the inverse: a probabilistic hierarchy laid over the same sequence, where random shortcuts let you leap. And the magic is that no one designs the balance — the coin flips produce a log-depth structure on their own, self-balancing in expectation with zero rotations. Order walked in a line becomes order reached by descent. The green is the sorted haul; the magenta is randomness spending itself to make finding fast.
LIT Genuine skip list (William Pugh, 1989). Verified live: a skip list of 2,000 keys finds every present key and correctly rejects every absent one, and the fraction of nodes reaching level >= L matches the geometric 2^-L to within a few percent (window.__skip.searchCorrect && absentCorrect && levelsGeometric, all true). The coin-flip promotion, the drop-down search, and the geometric height distribution are exact; expected O(log n) search follows from the halving per level.
FIG 'Express lanes' is the picture; the coin-flip towers, drop-down search, and geometric level distribution are real and measured. Search cost is expected/probabilistic (a bad run of coin flips can be slower); correctness is unconditional and is what's checked.
FIG 'Express lanes' is the picture; the coin-flip towers, drop-down search, and geometric level distribution are real and measured. Search cost is expected/probabilistic (a bad run of coin flips can be slower); correctness is unconditional and is what's checked.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE INVENTORY · David Lee Wise (ROOT0), with AVAN