Skip Lists: Fast Search With a Few Coin Flips

Let’s talk about the problem first. We have some sorted data, and we want to find an item. How fast we can do that depends on the data structure we use.

For example, take this linked list:

HEAD → 7 → 14 → 21 → 30 → 38 → 45 → 52 → 60 → NIL

If we want to find 60, we have to go through every node before it. The data is sorted, but we still have to follow the pointers one by one. That’s O(n) work.

Now, with an array, we can jump to the middle and do a binary search. We get O(log n) search. But try inserting an item in the middle while keeping the array sorted. We have to move the items that come after it, and that can cost O(n).

With a linked list, once we know where to insert, we can just change a few pointers. Finding that position is what takes time.

So, what we want is fast search, while keeping those simple pointer updates for insertion and deletion. Skip lists give us a way to do this. Let’s see how.

You can also watch the video and follow along on the lightboard. I’m using the same examples here.

Adding an express lane

Imagine you’re on a local train. You want to reach your destination, but the train stops at every station on the way.

Now, suppose there’s an express train that skips some of those stations. You can take it as far as possible without going past your destination, then switch to the local train. You make fewer stops.

We can do something similar with a linked list. Add another level with pointers that skip some nodes. Add one more level that skips even more. When searching, start at the highest level and move down when you can’t go any further on that level.

The bottom level, level 0, still contains all the nodes. Each upper level takes some of the nodes from the level below it. A node on level 3 also appears on levels 2, 1, and 0.

Now we need to decide which nodes go to which levels.

One approach would be to send every second node to level 1, every fourth node to level 2, every eighth node to level 3, and so on. We get a nice, predictable structure.

But insert a node near the beginning and look at what happens. The node that was fourth is now fifth. Our rule breaks, and maintaining that exact pattern means changing towers further along the list.

That brings back the work we wanted to avoid. We need to decide a node’s height without depending on its position in the list.

Deciding the levels with coin flips

Every node starts at level 0. We flip a coin. If it’s heads, the node goes up one level and we flip again. If it’s tails, we stop.

For example:

• Tails: the node stays at level 0.
• Heads, then tails: it reaches level 1.
• Heads, heads, then tails: it reaches level 2.

With a fair coin, both outcomes have a 50% chance. So, in expectation, half the nodes reach level 1, a quarter reach level 2, and an eighth reach level 3.

We don’t need exactly half the nodes on the next level. The actual numbers can vary. We’re using probability to get that distribution over many nodes.

The useful part is that inserting another node doesn’t change the heights we’ve already chosen. Each new node gets its own coin flips.

What are we actually storing?

When you see a tower in the diagram, you might think we’re storing the same node multiple times. We don’t need to do that.

A tower can be one node with a key, a value, and an array of forward pointers. The coin flips decide the length of that array. Each entry tells us where to go next on that level.

For example, 38 in our list has four levels:

38.next[3] → NIL
38.next[2] → 60
38.next[1] → 45
38.next[0] → 45

We number the levels from 0, so a height of 4 means levels 0 to 3. HEAD is the starting node, with a pointer for each supported level. NIL means there’s no next node.

How do we search?

We start at HEAD, on the highest level. We want to skip as many nodes as we can, right?

Look at the next key. If it’s smaller than our target, move right. Otherwise, move down one level and check again. Keep doing this until we reach level 0 and can’t move right anymore.

At that point, inspect the next node. If its key equals our target, we’ve found it. If it’s larger, or the pointer is NIL, the target isn’t in the list.

There’s one small detail we’ll need later. Before moving down, we record where we stopped on that level. We keep these nodes in an array called update.

These are the predecessors: the nodes just before the position we’re looking for, one per level. When we insert or delete something, these are the nodes whose pointers we’ll change.

Here’s the pseudocode. top is the highest level we’re currently using:

find_predecessors(target):
    x = HEAD
    update = array(top + 1)

    for i from top down to 0:
        while x.next[i] != NIL and x.next[i].key < target:
            x = x.next[i]
        update[i] = x

    return update, x.next[0]

Notice the < here. We stop before the target, even if we can see it on an upper level. That gives us the predecessors we need. And we check for NIL before trying to read the next key.

Let’s find 52

Follow the highlighted path. Each tower is one node with pointers at different levels. Click any diagram to see it at full size.

We’re starting at the top left, and our target is 52.

1. The next key on level 3 is 38. It’s smaller than 52, so we can move there. The data is sorted, so we know we haven’t skipped over our target.
2. From 38, the next pointer is NIL. We still have lower levels to check. Record update[3] = 38 and go down.
3. On level 2, the next key is 60. That’s greater than 52, so we stay at 38, record update[2] = 38, and go down again.
4. On level 1, the next key is 45. We can move there. After that comes 60, so record update[1] = 45 and go down.
5. On level 0, the next key is 52. Record update[0] = 45, check the next key, and we’re done.

Here’s our update array, from level 0 upwards:

update = [45, 45, 38, 38]

The same node can appear more than once. We stopped at 38 on two levels and at 45 on two levels. That’s all the array is recording.

Inserting 48

Okay, now let’s insert 48 into the original list. First, we need to find where it belongs. We use the same search and get:

update = [45, 45, 38, 38]

We create the new node and flip the coin. Let’s say we get heads, then tails. The node reaches level 1, so it needs two forward pointers: one for level 0 and one for level 1.

Now the update array becomes useful. We already know which pointers to change. We don’t have to search for those nodes again.

For each level the new node has:

new.next[i] = update[i].next[i]
update[i].next[i] = new

First, make the new node point to the old next node. Then make the predecessor point to the new node. Keep that order; otherwise, without saving the old pointer somewhere, we lose the link to the rest of the list.

Two levels, two pointer writes on each. Four writes after the search, and 48 is in the list.

Our links now look like this:

Level 1: 45 → 48 → 60
Level 0: 45 → 48 → 52

We don’t touch levels 2 and 3 because 48 doesn’t reach them. The other nodes keep their heights. No rotations to work through here.

There are a couple of cases to handle in an implementation. If the key already exists, we need a rule for it: replace the value, reject it, or allow duplicates with a defined ordering. If the new node is taller than every existing node, HEAD is its predecessor on the new levels. Implementations usually set a maximum height too.

Also, when we say pointer updates are cheap, remember that we still had to find the insertion position. The whole operation takes expected O(log n) time.

Deleting 38

Let’s go back to the original list and remove 38. Again, we search first and keep the update array:

update = [30, 21, 21, HEAD]

We check that the next node really is 38. Then, on each level it has, we make its predecessor point to whatever comes after 38:

for i from 0 to victim.height - 1:
    update[i].next[i] = victim.next[i]

These are the changes:

Now level 3 has no data nodes. Keeping it around would just add an extra downward move to every search, so we lower the active top level to 2. We always keep level 0, even if the list is empty.

One thing to be careful about with concurrent readers: another thread could still be using the node we just removed. We need to wait until it’s safe before freeing that memory. Updating the pointers is only part of a concurrent implementation.

Why is the search actually faster?

We’ve followed the pointers, but we haven’t explained where O(log n) comes from. Let’s work through that.

We need to figure out two things: how many levels we have, and how many moves we make per level.

How many levels do we get?

To reach level 1, a node needs one head. To reach level 2, it needs two heads in a row. For level 3, three heads in a row.

If the probability of promotion is p, then:

P(node reaches level i) = p^i
Expected nodes on level i = n × p^i

For our fair coin, p = 1/2. So we expect n nodes at level 0, n/2 at level 1, n/4 at level 2, and so on. The higher we go, the fewer nodes we expect to see.

Let’s find the level where that expected count gets down to one:

n × (1/2)^i ≈ 1
              i ≈ log₂ n

For a million nodes, that’s around level 20. The actual height can vary because we’re flipping coins. Also, we’re counting from level 0, so a level index and the number of levels differ by one.

We can put a bound on the chance of getting a much taller tower. If M is the highest occupied level, then:

P(M ≥ L) ≤ n × p^L

This is a union bound: each node has probability p^L of reaching level L, and we add those probabilities across n nodes to get an upper bound.

With a fair coin, set L = ceil(log₂ n) + c and the bound becomes 2^(-c). Go ten levels above that rounded-up log₂ n, and the chance of any node reaching that high is below 0.1%.

So we have a handle on the height. Now we need to count the moves.

Let’s walk the path backwards

We’re walking backwards to understand the cost. The search itself still goes right and down.

Start where the search stopped on level 0. If the current node has a level above it, go up. Otherwise, move left to the previous node on this level.

Think about the coin flips that built these towers. Heads gave a node another level, so we can go up. Tails means we have to move left and try again.

Let C(k) be the expected number of moves to climb k levels. There are two cases:

• We get heads. We make one upward move and have k - 1 levels left. The cost is 1 + C(k - 1).
• We get tails. We make one leftward move, but we still have k levels left. The cost is 1 + C(k).

Each has a probability of 1/2, so:

C(k) = 1/2 × (1 + C(k - 1)) + 1/2 × (1 + C(k))

Subtract 1/2 × C(k) from both sides and multiply by 2:

C(k) = 2 + C(k - 1)
C(k) = 2k

Going up one more level costs two moves in expectation. With roughly log₂ n levels, we get:

about log₂ n levels × about 2 moves per level
≈ 2 log₂ n expected search-path moves

This is the basic argument. In a finite list, we can hit HEAD before taking all those leftward steps, and the full analysis also accounts for the sparse levels at the top. The expected search cost is O(log n).

Remember, we’re calculating an expected cost. An individual search can take more or fewer moves. And counting pointer moves doesn’t tell us exactly how many microseconds an implementation will take.

What about all these extra pointers?

Every node needs one pointer for level 0. Half the nodes, in expectation, need a second pointer. A quarter need a third, and so on:

Expected forward pointers per node
= 1 + 1/2 + 1/4 + 1/8 + …
= 2

This is a geometric series. It adds up to 2, which gives us about 2n forward pointers for n nodes. The expected space is O(n).

We still need memory for the keys, values, and allocation overhead. Having two pointers per node on average doesn’t mean the total memory usage is identical to a doubly linked list.

For a general promotion probability p, the same calculation gives:

Expected forward pointers per node = 1 / (1 - p)

These calculations assume we haven’t capped the height. A cap limits the pointer array size, but we need to pick it for the amount of data we expect. If we keep a very small maximum height and keep adding nodes, the highest level will eventually have too many nodes to search quickly.

We can change the probability too

So far, we’ve used p = 1/2. But the implementation can use a different probability. We aren’t actually restricted to flipping a physical coin.

Lowering p means fewer nodes get promoted. We store fewer pointers, but we tend to make more horizontal moves per level. The main term in the expected search cost is:

(1/p) × log base (1/p) of n

Let’s put some values into that:

These numbers come from the probability calculations. They aren’t benchmark results.

Look at 1/4. Compared to 1/2, we use a third fewer forward pointers, while the main term in the search cost stays the same. That’s a useful thing to be able to control.

You can see this one-in-four promotion rule in LevelDB’s implementation.

Of course, the same formula doesn’t guarantee the same runtime. Cache misses, comparisons, allocation, and synchronization still cost time. We’d need to measure the implementation on our workload.

What if we keep getting tails?

If every node stays at level 0, we’re back to a plain linked list. Search can take O(n). That can happen.

For 100 nodes with fair, independent coin flips, the chance that all 100 stop at level 0 is 2^(-100), or about 7.9 × 10^(-31). That’s very unlikely. It’s also just one possible bad configuration; this number doesn’t cover every way a search could be slow.

This is why we keep saying expected O(log n). The guarantee comes from the random choices. It isn’t a worst-case bound.

Inserting sorted data doesn’t itself force a skip list into a bad shape, as it can with an ordinary, unbalanced binary search tree. The heights come from the random choices, independently of insertion order. That assumes suitable randomness; a broken generator or someone exploiting predictable choices changes the situation.

Why use this when we have balanced trees?

Balanced trees give us worst-case O(log n) operations. A randomized skip list gives us expected O(log n), and its worst case is O(n). If we need a strict worst-case guarantee, that difference matters. Balanced trees, or a deterministic skip-list design, are options to consider.

What I like about the randomized skip list is how little the basic algorithm needs. Search follows one rule. Insertion and deletion use the path we’ve already recorded to change pointers. We don’t need to work through tree rotations.

We also keep the nodes in order. For a range query, find the beginning of the range, then walk along level 0. Returning k items takes expected O(log n + k) work.

You’ll find skip lists in systems you may already use:

• Redis sorted sets can use a skip list for ordered access alongside a dictionary for member lookups. Small sorted sets may use listpack instead. See the implementation and encoding documentation.
• RocksDB uses a skip list in its default memtable implementation. It has other memtable options too. The MemTable documentation explains those choices.
• Java’s ConcurrentSkipListMap is a concurrent sorted map, with expected average logarithmic cost for its common lookup and update operations. You can read the details in the API documentation.

Concurrency needs a bit more discussion. Skip lists can have lock-free implementations, but we don’t get thread safety just by using this data structure. For example, LevelDB requires external synchronization for writes. The pointer updates we’ve used here assume a sequential implementation.

I don’t want to hand-wave that part. Coordinating writes and deciding when a removed node can be freed need their own explanation.

And simplicity isn’t the only thing to compare. A page-oriented tree can have better memory locality than following pointers through separately allocated nodes. We still need to look at the actual workload and implementation.

Try finding 40

Go back to our original list and search for 40. Work out where we’d stop at each level and what the next key would be.

update = [38, 38, 38, 38]
candidate = 45

Now try the game at the top again. Pay attention to where you stop before going down. Those are the nodes you’d need in the update array if the next operation was an insertion or a deletion.

That’s what makes the idea so nice. The coin flips build the levels, the search finds our position, and we keep the pointer updates that made linked lists useful in the first place.