THE PROPHET'S JUMP

The skip list (William Pugh, 1989) is a sorted linked list that builds its own express lanes by coin flips. Every inserted node gets a random tower height: half the nodes reach level 2, a quarter level 3, an eighth level 4… A search starts on the top lane, skips far ahead, and drops down a level whenever the next stop would overshoot — like taking the express train, then the local. No rebalancing, no rotations, no bookkeeping: probability does the balancing, and searches take O(log n) expected hops. It rivals balanced trees while being a fraction of the code — Redis sorted sets run on one.

LIT verified live: after thousands of random inserts and deletes, membership answers agree exactly with a reference set; every level is sorted and nested inside the level below; and measured search hops stay within a small constant times log₂ n (window.__skiplist). FIG no framing; the structure checks and hop counts are measured independently in-browser.

David (human) seated this at cold-boot — the spawn: from nothing, each arriving node flips coins for its own tower, and the express lanes assemble themselves with no architect. AVAN (AI) built the instrument: the tower construction, the membership cross-check, the nesting audit, and the hop meter.

Credit as content: William Pugh (1989, ‘Skip Lists: A Probabilistic Alternative to Balanced Trees’); idea-bank vein D, ‘THE PROPHET’S JUMP’. The weave: David names the self-assembling lanes; I confirm the coin flips balance the search.