Skip to content
Tutorials Center
My learning

Topics

Lesson 195 of 225 ยท Advanced Topics

Skip Lists

Learn how a skip list works and build one in Python: layered linked lists with coin-flip levels give expected O(log n) search, insert and delete.

A sorted linked list is simple, but finding a value means walking from the head one node at a time: O(n). A sorted array lets you binary search in O(log n), but inserting in the middle shifts everything. A balanced tree gives O(log n) for both, at the price of tricky rotations. Is there a structure that is as easy as a linked list and still fast?

Yes: the skip list, invented by William Pugh in 1990. It stacks several sorted linked lists on top of one another. The bottom list holds every element; each higher list holds a random subset of the one below, so higher lists act as express lanes that let a search skip over many nodes. Balance comes from coin flips, not rotations. Redis uses skip lists for its sorted sets, and many databases use them for in-memory indexes.

The idea: express lanes

Think of a subway. The local train stops at every station; the express train stops at every few stations. To travel far you ride the express to the station just before your target, then switch to the local.

TEXT
level 3:  head ------------------------------> 50 -------------------------> nil
level 2:  head --------------> 20 -----------> 50 --------------> 80 -------> nil
level 1:  head ------> 10 ---> 20 ---> 35 ---> 50 ---> 60 -------> 80 -------> nil
level 0:  head -> 5 -> 10 -> 20 -> 25 -> 35 -> 50 -> 55 -> 60 -> 70 -> 80 -> 90 -> nil

Level 0 is a normal sorted list of everything. A node that appears on level 2 also appears on levels 1 and 0, and its tower of links is one object with several "next" pointers.

Searching for 60: start at the top level of the head. At each level, move right while the next key is smaller than the target; when you cannot move right any more, drop one level down. At level 3 you go to 50 (next is nil), drop to level 2: next is 80, which is too big, so drop to level 1: next is 60, which is not smaller than 60, so drop to level 0 and the next node is 60. Found, after only a few steps.

How levels are chosen

When a new key arrives, it needs a random tower height. Flip a coin until it comes up tails: each head adds a level. Then the chance of a node reaching level k is (1/2)^k. In a list of n elements, about n/2 nodes reach level 1, n/4 reach level 2, and so on, and the tallest tower is around log2(n) high. Each level has about half as many nodes as the one below, exactly like the halving in binary search, but nothing needs rebalancing.

Python Random levels follow a halving pattern

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each row is roughly half of the row above it. The exact counts depend on the seed, but the halving shape never does.

Building a skip list

A node stores a key and a list forward, where forward[i] is the next node on level i. The list has a sentinel head with the maximum number of levels, so there are no special cases at the start.

Insert needs to remember, for every level, the last node we passed before the insertion point. These nodes are the update array (also called the predecessors). We then splice the new node in after each of them, level by level, exactly as in a linked list.

Delete uses the same update array: find the predecessors, and if the next node on level 0 has the key, unlink it on every level where it appears.

Python A skip list with insert, search and delete

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that keys() always prints a sorted list, whatever the tower heights are. The levels only affect speed, never correctness. That is a very useful design property: even a terrible random roll cannot break the structure.

Why it is fast: expected O(log n)

Walk the search path backwards, from the found node up to the top. At each step you either go left (staying on a level) or go up (to a higher level). A node reaches a higher level with probability 1/2, so on average you go up once for every two steps, and you go left about once per level. With about log2(n) levels, the expected path has roughly 2 * log2(n) steps. The same bound holds for insert and delete, since they follow the search path.

Operation Expected time Worst case
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Space O(n) O(n log n) (all towers maximal)

The worst case happens only if the random heights are all terrible, which has astronomically small probability. In expectation, each node has 1 + 1/2 + 1/4 + ... = 2 links, so space is O(n) on average.

Python Counting steps as the list grows

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The program counts only the moves to the right, so it stays below the 2 * log2(n) estimate (which includes the downward moves). The average grows by only a few steps each time n grows tenfold, which is the signature of logarithmic growth. A plain linked list would need about n/2 steps on average.

Skip list versus other structures

  • Versus a balanced tree (AVL, red-black): both give O(log n). A skip list is far easier to write and, crucially, easier to make concurrent: inserting changes only a few pointers locally, with no rotations touching distant nodes. Trees give worst-case guarantees; skip lists give expected ones.
  • Versus a hash table: a hash table is O(1) on average but has no order. A skip list keeps keys sorted, so range queries ("all keys from 20 to 60") and ordered iteration are natural: find 20, then walk level 0.
  • Versus a sorted array: the array searches in O(log n) but inserts in O(n). The skip list inserts in O(log n) but uses more memory (extra pointers) and has poor cache locality.

Python's built-in answer for a sorted collection is bisect on a list, which is fine up to a few hundred thousand items. Skip lists matter when you must insert and delete often while keeping order, or when many threads share the structure.

Common mistakes

  • Forgetting the update array. Without the recorded predecessors on every level, you cannot splice the new tower in.
  • Not shrinking level after a delete. Empty top levels slow every search a little. Reduce level while the head's top link is None.
  • Unbounded random heights. Cap the height (for example 16 or 32) so a lucky streak cannot create a huge tower.
  • Wrong comparison. Move right while next.key < key, not <=. Then the final next on level 0 is the first key that is greater than or equal to the target.
  • Using the global random generator in tests. Seed a private random.Random so a failing test can be replayed.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a skip list use instead of rotations to stay balanced?

    Each new node gets a random height, so about half of the nodes are on level 1, a quarter on level 2, and so on. This gives logarithmic search paths in expectation without any rebalancing.
  2. 2. In a skip list search, what do you do when the next node on the current level is not smaller than the target?

    You move right only while the next key is smaller than the target. When you cannot, you go down one level, where steps are finer, until level 0.
  3. 3. What is the expected time of search, insert and delete in a skip list with n elements?

    There are about log2(n) levels, and the search path takes a constant expected number of steps per level.
  4. 4. Why does insert keep an update array?

    At each level the new node has to be spliced after the last smaller node. The update array stores exactly those predecessors.
  5. 5. Which advantage does a skip list have over a hash table?

    A hash table has no order. In a skip list you find the start of a range and walk level 0.

Summary

  • A skip list is a sorted linked list with random express lanes above it; each level holds roughly half the nodes of the level below.
  • Search starts at the top level, moves right while the next key is smaller, and drops down otherwise.
  • Insert and delete use an update array of predecessors and splice towers level by level.
  • Search, insert and delete take expected O(log n) time; space is O(n) expected. The worst case is O(n) but practically never happens.
  • Skip lists keep keys ordered, are simple to write and are easy to make concurrent, which is why databases and Redis use them.

Next: Designing Data Structures