Skip to content
Skip Lists: A Probabilistic Alternative to Balanced Trees 4 min

William Pugh · Communications of the ACM 1990

Skip Lists: A Probabilistic Alternative to Balanced Trees

Sorted lists with coin-flip express lanes: search in about log n steps without any rebalancing. Search and insert in a live skip list.

Read the original paper

Algorithms · Yellow Belt · Pro · 4 min read

Skip Lists: A Probabilistic Alternative to Balanced Trees

A sorted list is easy to search if it is an array: jump to the middle, then the middle of the half, and so on. But insert into an array and you must shift everything. A linked list inserts easily, yet finding anything means walking from the start. Computer scientists solved this with balanced trees such as AVL trees, which stay shallow by rotating nodes after every change. They work well, and they are fiddly to write correctly.

In 1990 William Pugh proposed something much simpler. Take a sorted linked list and add express lanes above it. Decide which items get express stops by flipping a coin. The result is a skip list. It searches in about log n steps on average, with code short enough to write in an afternoon.

A skip list keeps items in sorted order with several layers of links. Each item climbs to higher layers by luck, so higher layers hold fewer items and let searches jump far. Randomness replaces the careful rebalancing of a tree.

The express-lane idea

Think of a subway. A local train stops at every station. An express train stops at only some. To travel far, ride the express to the station nearest your destination, then switch to the local. A skip list layers several such lines on top of each other.

A skip list is a sorted linked list with express lanes. Higher levels skip over many nodes, so a search can take big steps first and small steps at the end.

To search for a key, start at the top-left. Move right while the next key on this level is smaller than your target. When the next key would overshoot, drop down one level and continue. At the bottom level, the next item is either your key or proof that it is not there.

It is the same trick as flipping through a dictionary. You first jump by thick groups of pages, then by thinner groups, then page by page.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 1 more diagram and 2 interactive elements to play with

  • Where do the levels come from? Coin flips
  • Skip lists versus balanced trees

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.