./ahmedhashim

Consider the Skip List

When you need sorted data with fast lookups and inserts, your first thought may be to use a balanced tree. This works well when a library hands you one. However, writing your own is a different story, because balance comes from rotations and therein lie the edge cases.

William Pugh said it plainly in the 1990 paper that introduced skip lists:

implementing balanced trees is an exacting task and as a result balanced tree algorithms are rarely implemented except as part of a programming assignment in a data structures class.

You don’t always need the tree. A skip list will get you the same O(log n) time complexity with a lot less code.

Express lanes

A skip list is a sorted linked list with express lanes stacked on top. Every value lives in the bottom list. Each level above holds fewer values than the one below it, so a single hop in a top lane skips over a long stretch of the list underneath.

To search, start at the top, move right until the next value is too big, then drop down a level and keep going until you reach the bottom. Each drop cuts the remaining work roughly in half, the same idea as binary search.

Let’s find 47 in the following skip list, one level at a time. The top lane hops straight to 19, skipping everything before it:

  flowchart TD
    subgraph L2["Level 2"]
        direction LR
        H2["HEAD"] --> B2["19"] --> N2["NIL"]
    end
    subgraph L1["Level 1"]
        direction LR
        H1["HEAD"] --> A1["7"] --> B1["19"] --> C1["47"] --> N1["NIL"]
    end
    subgraph L0["Level 0"]
        direction LR
        H0["HEAD"] --> V3["3"] --> A0["7"] --> V12["12"] --> B0["19"] --> V30["30"] --> C0["47"] --> V52["52"] --> N0["NIL"]
    end
    L2 ~~~ L1
    L1 ~~~ L0
    classDef seen stroke:#5ea1ff,stroke-width:2px
    classDef cur fill:#5ea1ff,stroke:#5ea1ff,color:#16181a
    class H2 seen
    class B2 cur

Nothing useful comes after 19 at the top, so the search drops to level 1. The next value there is 47 itself, but the walk only ever asks one question: is the next value still smaller than the target?

  flowchart TD
    subgraph L2["Level 2"]
        direction LR
        H2["HEAD"] --> B2["19"] --> N2["NIL"]
    end
    subgraph L1["Level 1"]
        direction LR
        H1["HEAD"] --> A1["7"] --> B1["19"] --> C1["47"] --> N1["NIL"]
    end
    subgraph L0["Level 0"]
        direction LR
        H0["HEAD"] --> V3["3"] --> A0["7"] --> V12["12"] --> B0["19"] --> V30["30"] --> C0["47"] --> V52["52"] --> N0["NIL"]
    end
    L2 ~~~ L1
    L1 ~~~ L0
    classDef seen stroke:#5ea1ff,stroke-width:2px
    classDef cur fill:#5ea1ff,stroke:#5ea1ff,color:#16181a
    class H2,B2 seen
    class B1 cur

It isn’t, so the walk drops again without moving, saving the equality check for the bottom. Now back in the full list, it steps through 30 and lands on 47. Seven values in the list, only three of which are visited:

  flowchart TD
    subgraph L2["Level 2"]
        direction LR
        H2["HEAD"] --> B2["19"] --> N2["NIL"]
    end
    subgraph L1["Level 1"]
        direction LR
        H1["HEAD"] --> A1["7"] --> B1["19"] --> C1["47"] --> N1["NIL"]
    end
    subgraph L0["Level 0"]
        direction LR
        H0["HEAD"] --> V3["3"] --> A0["7"] --> V12["12"] --> B0["19"] --> V30["30"] --> C0["47"] --> V52["52"] --> N0["NIL"]
    end
    L2 ~~~ L1
    L1 ~~~ L0
    classDef seen stroke:#5ea1ff,stroke-width:2px
    classDef found fill:#5eff6c,stroke:#5eff6c,color:#16181a
    class H2,B2,B1,B0,V30 seen
    class C0 found

Inserts

An insert starts with the exact same walk. To place 40, the search drops at 19 on level 2, drops at 19 again on level 1, then steps to 30 at the bottom and stops, since 47 is too big. On the way down it remembers each node it dropped from, because the new value will splice in right after them:

  flowchart TD
    subgraph L2["Level 2"]
        direction LR
        H2["HEAD"] --> B2["19"] --> N2["NIL"]
    end
    subgraph L1["Level 1"]
        direction LR
        H1["HEAD"] --> A1["7"] --> B1["19"] --> C1["47"] --> N1["NIL"]
    end
    subgraph L0["Level 0"]
        direction LR
        H0["HEAD"] --> V3["3"] --> A0["7"] --> V12["12"] --> B0["19"] --> V30["30"] --> C0["47"] --> V52["52"] --> N0["NIL"]
    end
    L2 ~~~ L1
    L1 ~~~ L0
    classDef seen stroke:#5ea1ff,stroke-width:2px
    classDef mark fill:#5ea1ff,stroke:#5ea1ff,color:#16181a
    class H2,B0 seen
    class B2,B1,V30 mark

Now randomness decides the height. The new node starts at the bottom and keeps getting promoted one level while a random check passes, and the first failure stops it. Here it earns two promotions, enough to join the top lane. Then it gets spliced in: at each level, the remembered node now points to 40, and 40 points to wherever the remembered node pointed before. Every lane stays sorted, and nothing else in the list moved:

  flowchart TD
    subgraph L2["Level 2"]
        direction LR
        H2["HEAD"] --> B2["19"] --> X2["40"] --> N2["NIL"]
    end
    subgraph L1["Level 1"]
        direction LR
        H1["HEAD"] --> A1["7"] --> B1["19"] --> X1["40"] --> C1["47"] --> N1["NIL"]
    end
    subgraph L0["Level 0"]
        direction LR
        H0["HEAD"] --> V3["3"] --> A0["7"] --> V12["12"] --> B0["19"] --> V30["30"] --> X0["40"] --> C0["47"] --> V52["52"] --> N0["NIL"]
    end
    L2 ~~~ L1
    L1 ~~~ L0
    classDef ins fill:#5eff6c,stroke:#5eff6c,color:#16181a
    class X2,X1,X0 ins

That bit of randomness is the entire balancing strategy. Half the nodes stay on the bottom, a quarter reach level 1, an eighth reach level 2. There’s nothing to rebalance. Random promotion does the work the rotations would, which is what Pugh meant by probabilistic balancing.

Implementation

The whole structure fits in under fifty lines of Python:

import random

MAX_LEVEL = 16
P = 0.5


class Node:
    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * level


class SkipList:
    def __init__(self):
        self.head = Node(None, MAX_LEVEL)
        self.level = 1

    def _random_level(self):
        level = 1
        while level < MAX_LEVEL and random.random() < P:
            level += 1
        return level

    def search(self, value):
        node = self.head
        for i in reversed(range(self.level)):
            while node.forward[i] and node.forward[i].value < value:
                node = node.forward[i]
        node = node.forward[0]
        return node is not None and node.value == value

    def insert(self, value):
        update = [self.head] * MAX_LEVEL
        node = self.head
        for i in reversed(range(self.level)):
            while node.forward[i] and node.forward[i].value < value:
                node = node.forward[i]
            update[i] = node

        level = self._random_level()
        self.level = max(self.level, level)
        node = Node(value, level)
        for i in range(level):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node

search is the walk from the diagram: move right while the next value is too small, then drop a level. insert does the same walk, remembers where it dropped on each level (update), and splices the new node into every level its random height reaches. Implementing delete would be the same walk as insert, except it unsplices nodes instead.

There isn’t a rotation or a balance factor anywhere in the file, which is why it’s hard to get wrong. A MAX_LEVEL of 16 covers 2^16 elements, so scale it with the logarithm of your expected element count.

Use Cases

Say you’re building an in-memory leaderboard: millions of scores in order, with lookups and range reads like “ranks 100 through 200”. A balanced tree handles it. However, Redis sorted sets are built on a skip list instead. When asked why he didn’t use B-trees, antirez explained:

  1. They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make [them] less memory intensive than btrees.

  2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

  3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

The third point is the one I’d emphasize the most. The structure was simple enough for an outsider to extend safely, and that patch shipped to production.

Concurrency tilts things further. A tree insert can rotate nodes far from where it landed, which is hard to lock correctly. A skip list insert touches a few neighboring pointers. That’s why the ordered map in java.util.concurrent is a ConcurrentSkipListMap rather than a concurrent red-black tree.

Tradeoffs

The speed is expected rather than guaranteed. An unlucky streak of promotions can leave the list flat, and the worst case is an O(n) scan. Pugh measured how unlikely that is: at 4,096 elements, the odds of a search taking three times longer than expected are under one in 200 million. That’s fine for a server, but hard real-time systems require a tree’s worst-case guarantee.

Memory comes out about even with a tree, and it’s tunable (antirez’s first reason). Every level a node reaches costs one forward pointer. At a promotion chance of 1/2, the average node ends up with two pointers, matching a tree’s two children. Lower the chance to 1/4 and the average drops to 1.33 pointers, with slightly faster searches as a bonus. That’s why Pugh suggests 1/4 as the default.

The real cost is where the nodes live in memory. Each node is allocated on its own, so every step of a search jumps to an unrelated address, and each jump risks a cache miss that leaves the CPU waiting on RAM. A B-tree packs many keys into each node instead, so one fetch pulls in a whole sorted block that scans almost for free. The gap widens on disk, where a jump becomes a full read. For data on disk or the hottest code paths, the B-tree is the better choice.

Position lookups are the other gap. “Give me the 500th element” is slow because nothing in the list counts how many values a pointer skips over. Storing that count on every link fixes it, but a tree needs the same bookkeeping for the job, so neither side wins.

None of that changes the headline. For an ordered structure in memory, especially one you have to build and debug yourself, a skip list buys tree performance for linked-list effort. The next time sorted data has you planning rotations, consider reaching for randomness instead.