---
title: 'Skip Lists'
source: 'https://academia.sh/en/courses/data-structures/skip-lists'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:57+00:00'
license: 'CC BY-SA 4.0'
---

# Skip Lists

Reducing search cost by adding layers to a sorted linked list, probabilistic height, and expected cost.

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.

```python
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.