Skip lists

What this chapter covers

The trees tier gave us O(log n) ordered operations, but only through the intricate rotation logic of AVL and red-black trees — code that's genuinely hard to get right. The skip list gets the same O(log n) search, insert, and delete using nothing but linked lists and coin flips. Instead of carefully rebalancing after every change, it lets randomness do the balancing: each element is given a random "height," and the heights work out, in expectation, to exactly the layered structure that makes search logarithmic. This chapter builds the skip list, watches a search ride its express lanes to a target while touching only a handful of nodes, and shows it beat a plain sorted linked list by 1,500× on search steps at 100,000 elements — all with code far simpler than a balanced tree. That simplicity is why real systems (Redis, LevelDB) use skip lists where a textbook would reach for a balanced tree.

A bit of history

William Pugh introduced skip lists in 1989, in a paper whose subtitle said it all: "A Probabilistic Alternative to Balanced Trees." Pugh's argument was as much about software engineering as about algorithms — he showed that skip lists match balanced trees' O(log n) bounds while being dramatically easier to implement, to reason about, and to make concurrent. A balanced-tree insertion might trigger a cascade of rotations with many cases to handle correctly; a skip-list insertion flips a coin and splices a few pointers. That simplicity, especially for concurrent access (a skip list is far easier to make lock-free than a balanced tree, because updates are local pointer splices), made skip lists a favorite in systems programming. They're the ordered structure behind Redis sorted sets, the memtables in LevelDB and RocksDB, Java's ConcurrentSkipListMap, and MemSQL's indexes. Pugh's deeper point — that randomization can replace intricate deterministic balancing, trading a worst-case guarantee for an equally-good expected one and a fraction of the complexity — connects skip lists to the same philosophy as the previous chapter's Bloom filter and the next chapter's randomized structures: sometimes the simplest good-enough answer beats the complex perfect one.

The intuition

A sorted linked list is the problem: it's simple, but search is O(n) because you must walk every node to reach your target — there's no way to jump ahead. Skip lists add express lanes. Keep the full sorted list as the bottom lane (level 0), but build sparser lists on top: level 1 might contain every other element, level 2 every fourth, and so on, each a linked list that skips over many elements. Now search top-down. Start in the sparsest top lane and move right until the next node would overshoot your target — then drop down one lane, where you're now positioned just before the target among a denser set of nodes, and continue. Each drop lands you in a lane with twice the density but only in the small span you've narrowed to, so each level roughly halves the remaining distance. That's O(log n), the same divide-and-conquer as binary search, achieved by riding express lanes down to the local lane near your target.

The elegant part is how the lanes get built without any bookkeeping. When you insert an element, you flip a coin to decide its height: it always goes in level 0; with probability ½ it's also promoted to level 1; if so, with probability ½ again to level 2; and so on. So half the elements have height 0, a quarter reach height 1, an eighth reach height 2 — a geometric distribution that makes each lane about half as populated as the one below, which is exactly the express-lane structure that gives logarithmic search. No element ever needs to be moved or rebalanced; its height is fixed at insertion by the coins, and the probabilities guarantee the right shape on average. Insert and delete are just splicing pointers into (or out of) each lane the element occupies, found on the way down. The whole structure balances itself statistically, which is why the code has no rotation cases at all.

Complexity: how it scales

Search, insert, and delete are all O(log n) expected: the structure is O(log n) lanes tall in expectation (a node reaches level k with probability 1/2^k, so the max height is ~log₂ n), and each lane contributes O(1) expected rightward steps before dropping down. Space is O(n) expected — the total number of pointers is n × (1 + ½ + ¼ + …) = 2n. These are expected bounds, not worst-case: an unlucky run of coin flips could in principle make a tall degenerate structure, but the probability is astronomically small (like a hash table's worst case), and unlike a hash table there's no adversarial input that forces it, because the randomness is the structure's own, not the data's. The face-off shows the search cost against the plain sorted linked list it upgrades:

The linked-list line climbs linearly — search visits on average half the elements — while the skip-list line barely rises, growing logarithmically. At 100,000 elements the sorted linked list took about 48,000 steps to find a random element; the skip list took about 32 — a 1,500-fold difference, and the gap widens without bound because one is linear and the other logarithmic. The skip list achieves this with the express lanes alone: the same data, the same linked-list nodes, plus a handful of extra forward pointers assigned by coin flips. That's the entire cost of turning an O(n) structure into an O(log n) one, and it matches what a balanced tree would give you — with code you could write correctly on the first try.

What it's good at, what it isn't

Skip lists are the right choice for an ordered map or set when you want balanced-tree performance without balanced-tree complexity — especially in concurrent settings, where their local pointer splices are far easier to make lock-free than a tree's rotations (Java's ConcurrentSkipListMap is the standard example). They support everything a balanced tree does — ordered iteration, range queries, predecessor/successor, rank — and their memtable role in LevelDB/RocksDB and index role in Redis sorted sets are exactly these ordered-operation workloads at scale. They're also simply nice to implement: when you need an ordered structure and don't want to debug red-black rotations, a skip list gets you there with confidence. And because they degrade gracefully and have no adversarial worst case, they're robust to untrusted input in a way naive hash tables aren't.

Where they're less ideal: they use more memory than a plain balanced tree (the extra forward pointers, ~2n total) and more than a hash table for pure membership; they're slower than a hash table for unordered key-value access (a hash table is O(1), a skip list O(log n)); and their bounds are expected, so a hard real-time system needing a strict worst-case guarantee might prefer a balanced tree (though the skip list's bad case is vanishingly unlikely). For purely static sorted data, a plain sorted array with binary search (bisect) is more cache-friendly and compact than a skip list's scattered nodes. Skip lists shine specifically for dynamic ordered data where simplicity and concurrency matter; for static data or unordered access, other structures fit better.

The data, or the inputs

The face-off counts search steps for the skip list against a plain sorted linked list, as the element count grows to 100,000 (the linked list's cost is computed analytically from sorted rank to avoid an O(n²) build). Correctness is checked by treating the skip list as a sorted set under hundreds of random insert/delete sequences: its bottom lane must always equal the sorted set of present values, and membership queries must match a reference set for every probe. The animation searches a small skip list (ten elements, several lanes) for the value 23, showing the search ride the top express lane rightward and drop down toward the target.

Build it, one function at a time

The skip list — random levels by coin flip, search by riding lanes down, insert/delete by splicing:

class SkipList:
    """A skip list over comparable values. `level` is the current highest lane in use; `header` is a
    sentinel reaching every lane. p = 0.5 means each element is promoted to the next lane with
    probability 1/2, so lane heights are geometric and the structure is O(log n) tall in expectation."""

    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level
        self.p = p
        self.header = Node(None, max_level)
        self.level = 0

    def _random_level(self):
        """Flip coins: keep promoting to a higher lane while heads come up. Gives level 0 half the
        time, level 1 a quarter, level 2 an eighth, … — the geometric distribution that makes the
        express lanes exponentially sparser going up."""
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

    def search(self, value, trace=None):
        """Start in the top lane; at each lane move right while the next node is still < value, then
        drop down a lane. After dropping through the bottom lane, the next node is the answer (or a
        larger value / None if absent). O(log n) expected — each lane skips ~half the remaining span."""
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]              # move right along this express lane
                if trace is not None:
                    trace.append(("right", i, cur.value))
            if trace is not None:
                trace.append(("down", i, cur.value if cur.value is not None else "head"))
        cur = cur.forward[0]
        return cur is not None and cur.value == value

    def insert(self, value):
        """Insert, keeping every lane sorted. Walk down recording, at each lane, the last node before
        `value` (the `update` array — where new links must be spliced). Then coin-flip the new node's
        height and splice it into every lane up to that height. No rebalancing."""
        update = [self.header] * (self.max_level + 1)
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]
            update[i] = cur
        if cur.forward[0] is not None and cur.forward[0].value == value:
            return                                # already present — no duplicates
        lvl = self._random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.header           # new top lanes start from the header
            self.level = lvl
        node = Node(value, lvl)
        for i in range(lvl + 1):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node           # splice into lane i

    def delete(self, value):
        """Remove `value` by unlinking it from every lane it appears in, then trimming any now-empty
        top lanes."""
        update = [self.header] * (self.max_level + 1)
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]
            update[i] = cur
        target = cur.forward[0]
        if target is None or target.value != value:
            return False
        for i in range(self.level + 1):
            if update[i].forward[i] is target:
                update[i].forward[i] = target.forward[i]
        while self.level > 0 and self.header.forward[self.level] is None:
            self.level -= 1                       # trim empty top lanes
        return True

Watch it work

Here's a skip list of ten elements searching for 23. The bottom lane (level 0) holds every element; the lanes above are the express lanes, each sparser than the one below, and H is the header that reaches every lane. The search starts at the top-left, in the sparsest lane, and rides it rightward as long as the next node is still less than 23 (orange marks the current node, blue the ones visited). When the next node would overshoot 23, it drops down a lane — landing among denser nodes, but only in the narrow span it's already reached — and continues right. Watch it descend the lanes in a staircase toward the target, and note how few nodes it touches: it finds 23 having visited only 3 nodes out of 10, because the express lanes let it skip over everything to the left in a couple of hops. That staircase is the same halving as binary search, done with linked lists and coin flips:

The complete code

The from-scratch tab is the full skip list — random levels, search, insert, delete; the library tab is the plain sorted linked list it upgrades (the O(n) baseline and a correctness reference), with a note on the production sortedcontainers and the skip lists inside Redis and LevelDB. Flip between them — the skip list is the linked list plus a coin flip and an array of forward pointers, and that small addition is the whole difference between O(n) and O(log n).

"""Skip list — a sorted structure with the O(log n) search, insert, and delete of a balanced tree,
built from nothing but linked lists and coin flips. It's the answer to a frustration from the trees
tier: AVL and red-black trees achieve O(log n) but only through intricate rotation logic that's
genuinely hard to get right. A skip list gets the same performance with almost no cleverness —
randomization does the balancing for you.

The idea is express lanes. A plain sorted linked list forces you to walk element by element — O(n) to
find anything. A skip list stacks several linked lists on top of each other: the bottom level holds
every element, and each level above is a sparser "express lane" that skips over many elements. To
search, you start at the top (sparsest) lane and move right until the next node would overshoot your
target, then DROP DOWN a level and continue — each drop lands you in a denser lane near the target,
halving the remaining distance. The magic is how the lanes are built: when you insert an element, you
flip a coin to decide how many levels tall it is (heads → promote it one lane up, repeat). No
balancing, no rotations — just probability, which makes the levels geometrically sparser and the
expected search O(log n).
"""
import random


class Node:
    __slots__ = ("value", "forward")

    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)       # a forward pointer per level this node reaches


# region: skiplist
class SkipList:
    """A skip list over comparable values. `level` is the current highest lane in use; `header` is a
    sentinel reaching every lane. p = 0.5 means each element is promoted to the next lane with
    probability 1/2, so lane heights are geometric and the structure is O(log n) tall in expectation."""

    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level
        self.p = p
        self.header = Node(None, max_level)
        self.level = 0

    def _random_level(self):
        """Flip coins: keep promoting to a higher lane while heads come up. Gives level 0 half the
        time, level 1 a quarter, level 2 an eighth, … — the geometric distribution that makes the
        express lanes exponentially sparser going up."""
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

    def search(self, value, trace=None):
        """Start in the top lane; at each lane move right while the next node is still < value, then
        drop down a lane. After dropping through the bottom lane, the next node is the answer (or a
        larger value / None if absent). O(log n) expected — each lane skips ~half the remaining span."""
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]              # move right along this express lane
                if trace is not None:
                    trace.append(("right", i, cur.value))
            if trace is not None:
                trace.append(("down", i, cur.value if cur.value is not None else "head"))
        cur = cur.forward[0]
        return cur is not None and cur.value == value

    def insert(self, value):
        """Insert, keeping every lane sorted. Walk down recording, at each lane, the last node before
        `value` (the `update` array — where new links must be spliced). Then coin-flip the new node's
        height and splice it into every lane up to that height. No rebalancing."""
        update = [self.header] * (self.max_level + 1)
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]
            update[i] = cur
        if cur.forward[0] is not None and cur.forward[0].value == value:
            return                                # already present — no duplicates
        lvl = self._random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.header           # new top lanes start from the header
            self.level = lvl
        node = Node(value, lvl)
        for i in range(lvl + 1):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node           # splice into lane i

    def delete(self, value):
        """Remove `value` by unlinking it from every lane it appears in, then trimming any now-empty
        top lanes."""
        update = [self.header] * (self.max_level + 1)
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]
            update[i] = cur
        target = cur.forward[0]
        if target is None or target.value != value:
            return False
        for i in range(self.level + 1):
            if update[i].forward[i] is target:
                update[i].forward[i] = target.forward[i]
        while self.level > 0 and self.header.forward[self.level] is None:
            self.level -= 1                       # trim empty top lanes
        return True
# endregion


# region: levels
def dump_levels(sl):
    """Return, for each lane, the list of values reachable in it — for drawing the express lanes."""
    lanes = []
    for i in range(sl.level, -1, -1):
        vals, cur = [], sl.header.forward[i]
        while cur is not None:
            vals.append(cur.value)
            cur = cur.forward[i]
        lanes.append((i, vals))
    return lanes
# endregion

"""The contrast and the reference. Two comparisons:

- `SortedLinkedList` is a plain sorted singly-linked list — the structure a skip list upgrades. Its
  search is O(n): no express lanes, you walk every node. It's the baseline that shows what the skip
  list's random levels buy, and (being obviously correct) a correctness reference.
- Python's `bisect` on a list, and the third-party `sortedcontainers`, are what you'd use in practice
  for a sorted collection; Redis sorted sets and LevelDB use skip lists internally for the same job.
  `bisect`-based membership is a second correctness oracle.

    import bisect
    i = bisect.bisect_left(sorted_list, x); present = i < len(sorted_list) and sorted_list[i] == x
"""


# region: linkedlist
class _LLNode:
    __slots__ = ("value", "next")

    def __init__(self, value):
        self.value = value
        self.next = None


class SortedLinkedList:
    """A sorted singly-linked list: search walks node by node until it reaches or passes the value —
    O(n). The skip list is this plus randomized express lanes. Used to count comparisons against the
    skip list's search."""

    def __init__(self):
        self.head = None

    def insert(self, value):
        node = _LLNode(value)
        if self.head is None or self.head.value >= value:
            if self.head is not None and self.head.value == value:
                return
            node.next = self.head
            self.head = node
            return
        cur = self.head
        while cur.next is not None and cur.next.value < value:
            cur = cur.next
        if cur.next is not None and cur.next.value == value:
            return
        node.next = cur.next
        cur.next = node

    def search(self, value):
        """Returns (found, comparisons) — the linear walk that skip lists improve on."""
        cur, comparisons = self.head, 0
        while cur is not None and cur.value < value:
            comparisons += 1
            cur = cur.next
        comparisons += 1
        return (cur is not None and cur.value == value), comparisons
# endregion

Scratch vs library

The skip list's lesson is that randomness can replace cleverness. A balanced tree earns its O(log n) through deterministic rotations with many carefully-handled cases; the skip list earns the same bound by flipping coins and trusting the probabilities — and the result is code you can write correctly without a reference open beside you. That's a genuinely different design philosophy, and it echoes the previous chapter's Bloom filter (trade exactness for space) and anticipates the reservoir-sampling and randomized-algorithm ideas ahead: introducing randomness deliberately, on your side rather than the adversary's, often buys simplicity, robustness against worst-case inputs, and easy concurrency, at the cost of turning a worst-case guarantee into an overwhelmingly-likely expected one. The face-off's 1,500× win over the sorted linked list is what the express lanes buy; the comparison against a balanced tree — same performance, far simpler code — is why skip lists ship in Redis and LevelDB. In production you'd use sortedcontainers or a database's built-in; building the skip list yourself is what makes "randomization instead of rotations" a structure you've watched work rather than a slogan.

Where you'll actually meet it

Skip lists run in widely-used systems precisely because of their simplicity and concurrency-friendliness. Redis implements its sorted sets (ZSET) with a skip list, powering leaderboards, priority queues, and range queries in one of the most-deployed data stores. LevelDB and RocksDB use skip lists for their in-memory memtables (the write buffer before data is flushed to disk). Java's standard library ships ConcurrentSkipListMap and ConcurrentSkipListSet as its scalable concurrent ordered collections. Apache Lucene, HBase, and various databases use them for indexes and in-memory structures. They appear in lock-free and wait-free concurrent programming as the go-to ordered structure, and in networking and range-query systems where ordered dynamic data must be searched under concurrent access. Anywhere you'd want a balanced tree but value implementation simplicity or easy concurrency more than a strict worst-case guarantee, a skip list is a common and excellent choice.

Takeaways

A skip list is a stack of sorted linked lists — a full bottom lane plus geometrically-sparser express lanes above — where each element's height is set by coin flips, giving O(log n) expected search, insert, and delete with no rotations. Search rides each express lane rightward and drops down near the target, the same halving as binary search; it beat a sorted linked list by 1,500× at 100,000 elements. It matches balanced trees' performance with a fraction of the code and far easier concurrency, trading a worst-case guarantee for an overwhelmingly-likely expected one — and because the randomness is its own, no adversarial input can force bad performance. It's the canonical example of randomization replacing deterministic complexity.

The next chapter builds a concrete, ubiquitous structure by combining two you already know. An LRU (least-recently- used) cache — the eviction policy behind CPU caches, web caches, and memory managers everywhere — needs O(1) lookup and O(1) tracking of access order, which neither a hash table nor a linked list gives alone, but their combination does: a hash map for instant lookup plus a doubly-linked list for instant reordering, the classic composition that turns two simple structures into exactly the interface a cache needs.