Skip Lists

A linked list is the simplest ordered structure there is: a chain of nodes, each pointing to the next. It is wonderfully easy to build, but searching it is painful — to find a value you walk node by node from the front, so a list of a million items can cost a million steps.

Balanced trees fix that with $O(\log n)$ search, but they earn it with bookkeeping: every insertion may trigger rotations and rebalancing to keep the tree's shape under control. The code is fiddly and easy to get wrong.

In 1990, William Pugh asked a mischievous question: what if we keep the simple linked list, but add a few random express lanes on top? Some nodes get promoted to a higher level — by a coin flip — and those higher levels let a search skip over long stretches of the list. No rotations, no rebalancing. Just luck, applied consistently. The result is the skip list.

Insert a few keys below. Each new node flips a coin repeatedly to decide its tower height — heads keeps building up, tails stops — so most nodes stay short and a lucky few rise into the express lanes.

<p class="hint">{{hint}}</p>
<div class="controls">
  <input id="key" type="number" value="42" min="1" max="99" />
  <button id="insert" type="button">{{btn_insert}}</button>
  <button id="rand" type="button">{{btn_rand}}</button>
  <button id="search" type="button">{{btn_search}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="grid" class="grid"></div>
<div class="status" id="status">{{status_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
input { width: 64px; font: 600 14px system-ui, sans-serif; padding: .4rem .5rem;
        border: 1px solid #adb1b8; border-radius: 8px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.grid { display: flex; flex-direction: column-reverse; gap: 4px; overflow-x: auto;
        padding: .6rem .4rem; background: #f4f7fa; border-radius: 10px; }
.lane { display: flex; gap: 4px; align-items: center; min-height: 38px; }
.lane-label { flex: 0 0 34px; font: 700 11px ui-monospace, monospace; color: #6b7785; text-align: right; padding-right: 4px; }
.node { flex: 0 0 38px; height: 32px; display: flex; align-items: center; justify-content: center;
        font: 700 14px ui-monospace, monospace; border-radius: 8px; background: #e8eef3;
        color: #1d3557; border: 1px solid #cdd9e3; transition: all .12s; }
.node.head { background: #1d3557; color: #fff; border-color: #1d3557; font-size: 11px; }
.node.gap { background: transparent; border: 1px dashed #d6dee6; color: transparent; }
.node.cursor { background: #f4a900; border-color: #c98700; color: #1d3557; transform: scale(1.12); }
.node.found { background: #0a7d33; border-color: #086628; color: #fff; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }

// Code not found

Then search for a key. Watch the cursor start at the top-left, race rightward along the highest lane until the next node would overshoot, then drop down a level and continue. Each hop along a high lane skips over many nodes at once. Count the hops: a plain linked-list search would have to visit every node up to the target, while the skip list reaches it in far fewer steps.

So how fast is a skip list, and is it actually guaranteed?

• Search, insert, delete are expected $O(\log n)$. With each level holding roughly half the nodes of the one below, there are about $\log_{2}$ n levels, and a search spends a constant number of hops per level on average.
• Space is $O(n)$ expected. A node has height 1 with probability ½, height 2 with probability ¼, and so on, so the average tower is just two pointers tall.
• The guarantee is probabilistic, not worst-case. A spectacularly unlucky run of coin flips could make every node tall and degrade search toward $O(n)$. That's vanishingly unlikely — the probability of being far from $O(\log n)$ shrinks exponentially — but it is never zero. This is a solved design, introduced by William Pugh in 1990; it isn't an open problem, but its bounds are expected, not guaranteed.
• No rotations, ever. Unlike a red-black or AVL tree, a skip list never restructures existing nodes. Balance is an emergent property of randomness, which is exactly why the code is so short.

This is the same trade balanced trees deny you: they pay with worst-case guarantees and complex rebalancing; skip lists pay with simplicity and randomness, and win in expectation. It is randomized algorithms at their most elegant — close cousins of the hashing tricks behind Bloom filters.

Skip lists aren't just a classroom curiosity — they ship in software you use every day:

• Redis sorted sets are backed by a skip list, giving fast ranked lookups for leaderboards, rate limiters and priority queues.
• Java's ConcurrentSkipListMap uses one because skip lists are far easier to make lock-free than balanced trees: a local pointer update doesn't ripple into rotations across the structure.
• LSM-tree databases (LevelDB, RocksDB, Cassandra) often use a skip list as the in-memory memtable that buffers writes before they're flushed to disk.
• Teaching randomized algorithms: because the code fits on a napkin, skip lists are a favourite first example of trading worst-case guarantees for expected-case simplicity.

The common thread is concurrency and simplicity: when many threads hammer an ordered structure at once, a design with no global rebalancing is a gift.

Skip lists are a small lesson with a big punchline: sometimes the cleanest way to stay balanced is to stop trying and let chance do it for you. By stacking random express lanes over a humble linked list, William Pugh matched the $O(\log n)$ speed of balanced trees while throwing away their hardest part — the rotations.

The catch is honest: the guarantee is expected, not worst-case, and a cosmically unlucky stream of coin flips could slow things down. But in practice that never happens, and the payoff — short, concurrency-friendly code — is why skip lists quietly run inside Redis, Java and half the databases you've ever queried. If you enjoyed how randomness buys you speed here, see the same idea in Bloom filters, and the deeper question of which problems stay hard in P vs NP.