Skip Lists

In a sorted array, binary search is $O(\log n)$: the middle element can be jumped to directly. In a sorted linked list, the same search stays $O(n)$, because there is no jumping — reaching the middle element requires following every link.

The skip list brings jumping back while keeping the linked structure. Its method is to add sparse layers on top of the list.

The Layer Idea

Consider a railway line: a local line that stops at every station, a fast line that stops every few stations, and an express line that stops only at major hubs. Traveling to a distant station, the express line is used to get as close as possible first, then the lower lines are dropped down to.

The skip list follows the same arrangement. The bottom layer is a sorted linked list containing every element. Each layer above carries a portion of the elements of the one below it. Search starts from the top layer:

1. Advance within the current layer as long as the next element is smaller than the target.
2. Drop down one layer when advancing is no longer possible.
3. Stop at the bottom layer; the sought element is either the next element at that point, or it is absent.

If each layer carries roughly half the elements of the one below it, the number of layers is $\log_2 n$, and a constant number of steps on average is taken in each layer. The expected search cost is therefore $O(\log n)$.

How Height Is Determined

If the layers had to be kept regular — every second element one layer up, every fourth element two layers up — insertion and deletion would require reorganizing the entire structure. This is the same problem that balanced trees solve, and it would mean code of similar complexity.

The skip list’s solution is different: every new element chooses its own height at random. The common rule is the number of consecutive tails in a coin flip sequence — an element is present in at least one layer; with probability one half it rises to a second layer, with probability one quarter to a third.

The result is that layer occupancy comes out close to the desired ratio on average. No rebalancing is done at all; the structure stays balanced on its own.

The cost is the type of guarantee. With an unlucky sequence of randomness, every element could end up staying in a single layer, and search could fall back to $O(n)$. This probability drops rapidly as the element count grows, but it is not zero. The skip list gives an expected-cost guarantee, not a worst-case one.

The distinction matters: systems that need a worst-case guarantee choose balanced trees.

Demonstrating the Search

The structure below is a skip list whose heights are given by hand, for the sake of the example. Using fixed heights instead of randomness serves to show, repeatably, how the search proceeds.

class SkipNode:
    def __init__(self, value: int, height: int) -> None:
        self.value = value
        self.forward: list = [None] * height        # one link per layer


def build_list(elements: list[tuple[int, int]], top: int) -> SkipNode:
    """Builds a sorted skip list from (value, height) pairs."""
    head = SkipNode(-1, top)                         # sentinel node
    last = [head] * top                              # last node in each layer
    for value, height in elements:
        node = SkipNode(value, height)
        for k in range(height):
            last[k].forward[k] = node
            last[k] = node
    return head


def search(head: SkipNode, target: int, top: int) -> tuple[bool, int]:
    """Searches for the target; returns (found, steps taken)."""
    node = head
    steps = 0
    for k in range(top - 1, -1, -1):                 # from the top layer down
        while node.forward[k] is not None and node.forward[k].value < target:
            node = node.forward[k]                   # advance within the same layer
            steps += 1
        steps += 1                                    # drop down one layer
    candidate = node.forward[0]
    return (candidate is not None and candidate.value == target), steps


TOP = 3
elements = [(7, 3), (12, 1), (14, 2), (18, 1), (25, 3), (30, 1), (42, 2)]
head = build_list(elements, TOP)

print(search(head, 30, TOP))     # (True, 5)
print(search(head, 13, TOP))     # (False, 5)
print(search(head, 7, TOP))      # (True, 3)

When searching for the value 30, the 25 node in the top layer is reached in a single step; by the time the lower layers are reached, only a few elements are left. The same search in a single-layer sorted list would have required following six links.

The second call searches for a value not in the list and follows the same path; even though the search fails, the cost is of the same order.

Insertion and Deletion

Insertion is the search itself: the last node stopped at in each layer is recorded, the new node’s height is determined, and links are rewritten in that many layers. The expected cost is again $O(\log n)$.

Deletion proceeds the same way; the link is skipped past in every layer the node is present in.

What is notable is that no operation involves rebalancing. The rotation operations applied after insertion in balanced trees are absent here; balance comes from probability. This is why a skip list’s code is markedly shorter than a balanced tree’s.

The second practical advantage is concurrency: because changes are local, multiple threads working on the same structure require less locking than with balanced trees. This is why some database and in-memory store implementations choose it as their sorted index structure.

Bounding the Number of Layers

When height is chosen at random, a theoretically very tall node can be produced. Implementations therefore place an upper bound: the number of layers is fixed around the logarithm of the expected element count.

The bound’s effect is negligible. Because the probability of an element rising to $k$ layers is on the order of $2^{-k}$, in a structure of a million elements the probability of rising past twenty layers is vanishingly small. The bound only keeps memory layout predictable: the maximum number of links a node can carry is known.

The second practical detail is that the upper bound is chosen relative to the data size. If it is chosen too small, the layers saturate and search approaches linear; the cost of choosing it too large is only a few empty links. Because of this asymmetry, the bound is chosen generously.

Probabilistic Data Structures

The skip list is the first example of a broader family: probabilistic data structures. Their common trait is giving a probabilistic guarantee instead of a certain one, and being simpler or cheaper in return.

The family also includes filters that test membership with a false-positive probability, and counters that estimate the count of distinct elements using little memory. These structures are used at scales where an exact answer is not required or its cost is unacceptable, and they are a separate topic in the design of data-intensive systems.

Cost Table

Structure	Search	Insert	Delete	Guarantee
Sorted array	$O(\log n)$	$O(n)$	$O(n)$	Certain
Sorted linked list	$O(n)$	$O(1)$*	$O(1)$*	Certain
Skip list	$O(\log n)$	$O(\log n)$	$O(\log n)$	Expected

* If the position is already held.

Summary

• Binary search cannot be done on a sorted linked list; the skip list brings jumping back by adding sparse layers on top.
• Search advances in the top layer and drops to the layer below when it cannot advance further; the number of layers is logarithmic.
• Height is chosen at random for every element; this means rebalancing is never needed.
• The guarantee given is expected cost, not worst case; systems that need a certain guarantee choose balanced trees.
• The brevity of its code and its requiring less locking under concurrency are the structure’s practical advantages.
• The skip list is a member of the probabilistic data structures family.

Next Step

Throughout this topic, search stayed logarithmic at best: as the element count grows, cost keeps growing. Yet if where a value is stored can be computed from the value itself, search can drop to a single step. The next topic takes up the hash tables that build this idea, and the idea’s limits.