Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Skip lists: randomized levels over an ordered bottom chain

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A skip list keeps all keys in a sorted bottom lane and assigns some nodes additional forward pointers at higher lanes. Search starts high, moves right while the next key is smaller, and descends toward the target. Independent promotion choices give expected O(log n) search and insertion with O(n) expected pointers, while a rare unfavorable assignment can still require O(n) work. This small implementation fixes a maximum height for a bounded teaching input; a long-lived index must size or adapt the height ceiling for its expected key count. Duplicate-key behavior belongs in the API contract.

Operational case

A depot stores ordered dock codes 19, 47, 52, 61, and 83. Search for 52 can skip over part of the bottom chain using promoted links. A later insertion of 58 must appear between 52 and 61 on the bottom lane while any promoted links also remain sorted. The seeded random generator makes the trace reproducible, but it does not make the structure deterministically balanced for arbitrary input. A sorted Python list may still be simpler for a small mostly read-only catalog, because skip-list nodes carry pointer overhead.

Working Python program

python
from random import Random

class DockNode:
    def __init__(self, dock_key, height):
        self.dock_key = dock_key
        self.forward = [None] * height

max_height = 16
head = DockNode(-1, max_height)
coin = Random(47)

def locate(dock_key):
    current = head
    predecessors = [head] * max_height
    for level in range(max_height - 1, -1, -1):
        while current.forward[level] and current.forward[level].dock_key < dock_key:
            current = current.forward[level]
        predecessors[level] = current
    return predecessors

def insert(dock_key):
    predecessors = locate(dock_key)
    next_node = predecessors[0].forward[0]
    if next_node and next_node.dock_key == dock_key:
        return
    height = 1
    while height < max_height and coin.random() < 0.5:
        height += 1
    new_node = DockNode(dock_key, height)
    for level in range(height):
        new_node.forward[level] = predecessors[level].forward[level]
        predecessors[level].forward[level] = new_node

for dock_key in (61, 19, 83, 47, 52, 58):
    insert(dock_key)
ordered = []
current = head.forward[0]
while current:
    ordered.append(current.dock_key)
    current = current.forward[0]
print(ordered)
print(locate(52)[0].forward[0].dock_key == 52)

Output

Output
[19, 47, 52, 58, 61, 83]
True

Time, space, and tradeoff

Search and insertion are expected O(log n) while the level cap is high enough for the stored population; the worst case remains O(n). The implementation allocates one node per key and as many forward references as that key's sampled height. It rejects duplicate keys by leaving the existing node unchanged. It does not implement deletion, concurrency, or persistence. The search path is an O(max_height) temporary array in this insertion implementation. A production index should state ordering of duplicate values, random-state ownership, and synchronization across pointer updates.

Common Mistakes

  • Do not describe expected logarithmic cost as a worst-case guarantee.
  • Do not allow duplicate bottom-lane keys when lookup assumes uniqueness.
  • Do not reuse this fixed height ceiling for an unbounded population without analysis.

Connected lessons

Apply it: Project: design a versioned warehouse index and Advanced structure contracts.

Van Emde Boas trees: successor in a bounded integer universe adds a distinct structure contract to compare.

Span skip lists: rank and select without a full scan adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details