Introduction

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)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.

Build a 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">Insert keys to build the list — each node flips a coin for its <b>tower height</b>, so a lucky few rise into the express lanes. Then <b>search</b> and watch the cursor hop along the high lanes, dropping down only when the next node would overshoot.</p>
<div class="controls">
  <input id="key" type="number" value="42" min="1" max="99" />
  <button id="insert" type="button">Insert</button>
  <button id="rand" type="button">Insert random</button>
  <button id="search" type="button">Search</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div id="grid" class="grid"></div>
<div class="status" id="status">Insert a few keys, then search for one.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A skip list: an ordered linked list with random "express lanes". Each inserted
// node gets a random TOWER HEIGHT (flip a coin: heads => grow taller, P=1/2).
// Search starts on the top lane, moves right while the next key <= target, and
// drops a level otherwise — so high lanes skip over many nodes at once.
// Expected search/insert/delete: O(log n). (William Pugh, 1990.)
const P = 0.5, MAXLVL = 5;
let keys = [];        // sorted unique keys
let height = {};      // key -> tower height (1..MAXLVL)
let topLevel = 1;

function randomHeight(){ let h = 1; while (Math.random() < P && h < MAXLVL) h++; return h; }

function insert(k){
  if (height[k]) return false;          // no duplicates
  keys.push(k); keys.sort((a,b)=>a-b);
  height[k] = randomHeight();
  topLevel = Math.max(1, ...keys.map(x=>height[x]));
  return true;
}

// Returns the ordered list of nodes visited during the search (for animation),
// and whether the key was found. This is the real skip-list search: at each
// level the "next" pointer jumps to the next node tall enough to reach this
// level, skipping over the short ones — that is what makes it O(log n).
function searchPath(target){
  const path = [];                       // {level, key}  key=null means HEAD
  let lvl = topLevel - 1;                 // levels are 0-indexed internally
  let i = -1;                             // index in `keys`, -1 = head sentinel
  path.push({ level: lvl, key: null });
  while (lvl >= 0){
    // advance to the next node present at this level while its key <= target
    while (true){
      let j = i + 1;
      while (j < keys.length && height[keys[j]] - 1 < lvl) j++;   // skip short nodes
      if (j < keys.length && keys[j] <= target){ i = j; path.push({ level: lvl, key: keys[j] }); }
      else break;
    }
    if (i >= 0 && keys[i] === target) return { path, found: true };
    lvl--;                               // drop down a level
    if (lvl >= 0) path.push({ level: lvl, key: i >= 0 ? keys[i] : null });
  }
  return { path, found: keys[i] === target };
}

// ---- rendering ----
const grid = document.getElementById('grid');
function nodeId(level, key){ return 'n_'+level+'_'+(key===null?'H':key); }
function render(){
  grid.innerHTML = '';
  for (let lvl = 0; lvl < topLevel; lvl++){
    const lane = document.createElement('div'); lane.className = 'lane';
    const lab = document.createElement('div'); lab.className = 'lane-label'; lab.textContent = fmt('L%lvl%', { lvl: lvl });
    lane.appendChild(lab);
    const head = document.createElement('div'); head.className = 'node head';
    head.textContent = 'HEAD'; head.id = nodeId(lvl, null); lane.appendChild(head);
    for (const k of keys){
      const cell = document.createElement('div');
      if (height[k] - 1 >= lvl){ cell.className = 'node'; cell.textContent = k; cell.id = nodeId(lvl, k); }
      else { cell.className = 'node gap'; cell.textContent = k; }
      lane.appendChild(cell);
    }
    grid.appendChild(lane);
  }
}
function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status '+(cls||''); }

async function animateSearch(target){
  const { path, found } = searchPath(target);
  render();
  let hops = 0;
  for (const step of path){
    const el = document.getElementById(nodeId(step.level, step.key));
    if (el){ el.classList.add('cursor'); }
    hops++;
    await new Promise(r=>setTimeout(r, 380));
    if (el && !(found && step === path[path.length-1])) el.classList.remove('cursor');
  }
  const last = path[path.length-1];
  if (found){
    // highlight the found node on its top lane
    const lvl = height[target]-1;
    const el = document.getElementById(nodeId(lvl, target));
    if (el){ el.classList.remove('cursor'); el.classList.add('found'); }
    setStatus(fmt('Found %target% in %hops% hops (a flat list would need up to %indexOf%%v%).', { target: target, hops: hops, indexOf: keys.indexOf(target), v: 1 }), 'ok');
  } else {
    setStatus(fmt('%target% is not in the list — search ended after %hops% hops.', { target: target, hops: hops }), 'bad');
  }
}

document.getElementById('insert').addEventListener('click', ()=>{
  const k = parseInt(document.getElementById('key').value, 10);
  if (isNaN(k)) return;
  if (insert(k)){ render(); setStatus(fmt('Inserted %k% with tower height %v%.', { k: k, v: height[k] }), ''); }
  else setStatus(fmt('%k% is already in the list.', { k: k }), 'bad');
});
document.getElementById('rand').addEventListener('click', ()=>{
  let k, tries=0; do { k = 1 + Math.floor(Math.random()*99); tries++; } while (height[k] && tries<200);
  if (insert(k)){ document.getElementById('key').value = k; render(); setStatus(fmt('Inserted %k% with tower height %v%.', { k: k, v: height[k] }), ''); }
});
document.getElementById('search').addEventListener('click', ()=>{
  const k = parseInt(document.getElementById('key').value, 10);
  if (isNaN(k)) return;
  if (keys.length === 0){ setStatus('Insert some keys first.', 'bad'); return; }
  setStatus(fmt('Searching for %k%…', { k: k }), ''); animateSearch(k);
});
document.getElementById('reset').addEventListener('click', ()=>{
  keys = []; height = {}; topLevel = 1; render(); setStatus('Insert a few keys, then search for one.', '');
});

// seed a small list so the structure is visible immediately
[12, 25, 37, 42, 58, 71, 90].forEach(insert);
render();
Result
Console

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.

The Real Complexity

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

  • Search, insert, delete are expected O(log⁡n)O(\log n). With each level holding roughly half the nodes of the one below, there are about log⁡2\log_{2} n levels, and a search spends a constant number of hops per level on average.
  • Space is O(n)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)O(n). That's vanishingly unlikely — the probability of being far from O(log⁡n)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.

Where It Matters

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.

Conclusion

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)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/skip-lists/Content licensed under CC BY-NC 4.0.