SpecializedData structureaka probabilistic sorted list, multi-level linked list

Skip List

A sorted linked list with randomised express lanes stacked on top, giving expected O(log n) search, insert, and delete without any rebalancing.

Pattern: Binary SearchPractice (3)
Progress

Definition

A skip list stores keys in sorted order in a bottom-level linked list, then adds higher levels that skip over elements: each node is promoted to the next level with probability p (usually 1/2). Searching starts at the top-left, moves right while the next key is smaller, and drops down a level when it cannot — arriving at the target in expected O(log n) steps.

It delivers the same operations as a balanced Binary Search Tree — ordered iteration, predecessor/successor, range queries — with far simpler code: no rotations, no colour flips. The price is randomness (bounds are expected, not worst-case) and about 1/(1-p) pointers per node on average.

Redis sorted sets, LevelDB/RocksDB memtables, and Java's ConcurrentSkipListMap use skip lists, largely because concurrent insertion is much easier to make lock-free than in a rebalancing tree.

probabilisticsortedexpected O(log n)lock-free friendlyordered map

Intuition

A mental model before the formal terms.

A subway line with express trains. The local (bottom level) stops everywhere. Above it, an express line stops at every other station, and a super-express above that stops at every fourth. To reach your station, ride the fastest train that does not overshoot, then step down to slower trains for the final approach. With log₂ n levels, you never ride more than a couple of stops on any line.

Instead of carefully planning which stations are express, flip a coin at each station: heads, it also gets an express stop. On average the structure looks like the planned one, and no station ever has to be "rebalanced".

How it works

  1. Node: key, value, and an array forward[0…level] of next pointers, one per level. A head sentinel has MAX_LEVEL pointers.
  2. search(key): x = head; for level from top down to 0: while x.forward[level].key < key, move right. At the bottom, x.forward[0] is the candidate; compare its key.
  3. randomLevel(): lvl = 0; while random() < p and lvl < MAX_LEVEL: lvl++. With p = 1/2 about half the nodes have level ≥ 1, a quarter level ≥ 2, and so on.
  4. insert(key, value): perform the search while recording update[level] = last node visited at each level. If the key exists, overwrite the value. Otherwise create a node with a random level and splice it in at every level ≤ lvl: node.forward[i] = update[i].forward[i]; update[i].forward[i] = node.
  5. delete(key): same search with update[]; if found, at every level where update[i].forward[i] is the node, bypass it. Lower the list's current level if the top levels become empty.
  6. range(lo, hi): search for lo, then walk forward[0] until the key exceeds hi.

Why it works

With promotion probability p, the expected number of nodes at level i is n · pⁱ, so the expected height is O(log_{1/p} n).

A search moves right at most an expected 1/p times per level before dropping down (the next node at this level was promoted with probability p), giving expected O((1/p) log_{1/p} n) steps — O(log n) for constant p.

Insertion and deletion touch only the update[] pointers, at most one per level, so they cost O(log n) beyond the search and never restructure other nodes.

Operations

OperationDescriptionCost
search(key)Top-down, right-then-down walk.O(log n) expected
insert(key, value)Search with update[] then splice at a random level.O(log n) expected
delete(key)Search with update[] then bypass at each level.O(log n) expected
predecessor / successorSearch then step at level 0.O(log n) expected
range(lo, hi)Search lo, walk level 0.O(log n + k) expected
rank(key)Requires span counts per pointer (indexable skip list).O(log n) expected
min / maxFirst node at level 0 / walk to the end at top levels.O(1) / O(log n)

Recognition

How to tell a problem wants this.

  • A sorted collection with fast insert, delete, search and ordered traversal / rank / range queries.
  • "Design a skip list" (LeetCode 1206) or "implement an ordered set without a tree".
  • Concurrent ordered maps, in-memory database indexes, leaderboards with rank queries.
“sorted array” → Binary Search“reverse a linked list” → Linked List Manipulation

Interactive demo

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1search(k): x = head; for lvl from top to 0: while x.fwd[lvl] and x.fwd[lvl].key < k: x = x.fwd[lvl]
2  x = x.fwd[0]; return x if x and x.key == k
3insert(k, v): same walk recording update[lvl] = x at each level
4  lvl = random_level(); n = Node(k, v, lvl)
5  for i in 0..lvl: n.fwd[i] = update[i].fwd[i]; update[i].fwd[i] = n
6delete(k): same walk; for i: if update[i].fwd[i] is target: update[i].fwd[i] = target.fwd[i]

Implementation

1import random
2from typing import Optional
3 
4MAX_LEVEL = 16
5 
6 
7class SkipNode:
8    __slots__ = ("value", "next")
9 
10    def __init__(self, value: float, levels: int) -> None:
11        self.value = value
12        self.next: list[Optional["SkipNode"]] = [None] * levels
13 
14 
15class SkipList:
16    """A probabilistic ordered set: a sorted linked list with express lanes.
17    Each node is promoted to the next level with probability 1/2."""
18 
191 · A node carries its value plus one forward pointer per level it reaches
20    def __init__(self) -> None:
21        self.head = SkipNode(float("-inf"), MAX_LEVEL)
22        self.level = 1  # highest level currently in use
23 
242 · Search: drop down a level whenever the next node overshoots
25    def contains(self, value: int) -> bool:
26        n = self.head
27        for l in range(self.level - 1, -1, -1):
28            nxt = n.next[l]
29            while nxt is not None and nxt.value < value:
30                n = nxt
31                nxt = n.next[l]
32        found = n.next[0]
33        return found is not None and found.value == value
34 
353 · Insert: record the predecessor on every level, then splice in
36    def insert(self, value: int) -> bool:
37        update: list[SkipNode] = [self.head] * MAX_LEVEL
38        n = self.head
39        for l in range(self.level - 1, -1, -1):
40            nxt = n.next[l]
41            while nxt is not None and nxt.value < value:
42                n = nxt
43                nxt = n.next[l]
44            update[l] = n
45        successor = n.next[0]
46        if successor is not None and successor.value == value:
47            return False  # no duplicates
48 
494 · Coin flips decide the new node height; raise the list level if needed
50        new_level = 1
51        while new_level < MAX_LEVEL and random.random() < 0.5:
52            new_level += 1
53        self.level = max(self.level, new_level)
54 
55        fresh = SkipNode(value, new_level)
56        for l in range(new_level):
57            fresh.next[l] = update[l].next[l]
58            update[l].next[l] = fresh
59        return True
60 
615 · Erase: unlink from every level that pointed at the node
62    def erase(self, value: int) -> bool:
63        update: list[SkipNode] = [self.head] * MAX_LEVEL
64        n = self.head
65        for l in range(self.level - 1, -1, -1):
66            nxt = n.next[l]
67            while nxt is not None and nxt.value < value:
68                n = nxt
69                nxt = n.next[l]
70            update[l] = n
71        victim = n.next[0]
72        if victim is None or victim.value != value:
73            return False
74        for l in range(self.level):
75            if update[l].next[l] is victim:
76                update[l].next[l] = victim.next[l]
77        while self.level > 1 and self.head.next[self.level - 1] is None:
78            self.level -= 1
79        return True
Walkthrough
  1. __slots__ = ("value", "next") removes each node per-instance __dict__, which for a pointer-heavy structure cuts memory substantially.
  2. [None] * levels sizes the forward-pointer list to this node height only — the same "short nodes are cheap" property as the other languages.
  3. float("-inf") as the sentinel value compares less than every integer, so the head never matches and never needs a special case.
  4. range(self.level - 1, -1, -1) walks levels from the top down; the -1 stop is exclusive, so level 0 is included.
  5. update[l].next[l] is victim uses identity rather than equality, which is the correct test when unlinking a specific node object.
Complexity (this implementation)
time O(log n) expected for contains/insert/erase, O(n) worst case · space O(n) expected — 2 pointers per node on average

Every node is a Python object with reference-counting overhead; sortedcontainers beats this by a wide margin in practice.

Language notes
  • Python has no ordered container in the standard library beyond bisect over a list; sortedcontainers.SortedList is the de facto answer and uses a list-of-lists, not a skip list.
  • is versus == matters here: is None is the correct end-of-list test, and is victim is the correct identity test during unlinking.
  • [self.head] * MAX_LEVEL is safe because SkipNode references are immutable bindings — the same idiom with a mutable default ([[]] * n) would alias.
  • The forward reference Optional["SkipNode"] needs quotes because the class is not yet defined at annotation time; from __future__ import annotations removes the need.
Common mistakes in this language
  • Using == instead of is for the None checks, which invokes __eq__ and is both slower and wrong for classes that define equality.
  • Allocating [None] * MAX_LEVEL for every node rather than [None] * new_level, which inflates memory by roughly 8x.
  • Omitting __slots__ and then wondering why a million-node skip list uses several hundred megabytes.
Language differences that matter here
  • Ordered-container baseline: C++ has std::set/std::map (red-black, worst-case O(log n)), Python has bisect over a list plus third-party sortedcontainers, and JS/TS have nothing — Map is insertion-ordered, not key-ordered.
  • Memory management: C++ needs an explicit destructor walking level 0 (or unique_ptr ownership on that level), while JS/TS/Python simply drop the references and let the collector reclaim.
  • Sentinel value: -Infinity in JS/TS and float("-inf") in Python keep the node type uniform; C++ uses an ordinary int that is never compared, since the search only ever reads next[l]->value.
  • Concurrency is the real-world argument for skip lists, and it only pays off where lock-free CAS is available — C++ and the JVM — not in single-threaded JavaScript or under the CPython GIL.

Complexity

OperationAverageWorstNote
AccessO(log n)O(n)By key; k-th element needs span counts.
SearchO(log n)O(n)Expected O(log n) with high probability.
InsertO(log n)O(n)
DeleteO(log n)O(n)
UpdateO(log n)O(n)
MinO(1)O(1)
Predecessor / SuccessorO(log n)O(n)
Range queryO(log n + k)O(n)
SpaceO(n)Expected n/(1-p) pointers; ~2n with p = 1/2. Worst cases are vanishingly unlikely.

Advantages & disadvantages

Advantages
  • Balanced-tree performance with a fraction of the code and no rotations.
  • Ordered iteration and range queries come free from the bottom list.
  • Naturally lock-free / concurrent-friendly: inserts only modify local pointers.
  • Easy to extend with span counts for O(log n) rank and k-th element.
Disadvantages
  • Bounds are expected, not guaranteed; an adversary controlling the RNG can degrade it (in practice negligible).
  • More memory than a BST or array: ~2 pointers per node on average with p = 1/2, plus the level array.
  • Cache behaviour is worse than a B-tree or sorted array because nodes are scattered.
  • Not in most standard libraries except Java's concurrent variant.

Use cases

  • Redis sorted sets (ZSET) with rank queries.
  • LevelDB / RocksDB memtables.
  • Java ConcurrentSkipListMap / ConcurrentSkipListSet.
  • In-memory ordered indexes where writes are concurrent.
  • Leaderboards and interval/time-ordered event stores.
Use it when
  • You need an ordered map/set with logarithmic operations and simple code.
  • Concurrent inserts and reads on an ordered structure.
  • Range and rank queries on a dynamic sorted collection.
Avoid it when
  • Only unordered lookups are needed — a Hash Map is O(1).
  • Worst-case guarantees are mandatory — use an AVL Tree or Red-Black Tree.
  • Memory or cache efficiency is critical — a B-Tree or sorted array with Binary Search is denser.
  • Data is static — a sorted array with binary search wins on every axis.

Alternatives

Binary Search TreeAVL TreeRed-Black TreeB-TreeHash Map

Common mistakes

  • Forgetting to record update[] for levels above the current maximum when the new node is taller.
  • Comparing against x.forward[i].key without checking for null at the end of a level.
  • Not lowering level after deleting the only node at the top levels (harmless for correctness, wasteful for search).
  • Using <= instead of < in the walk, which lands on the node itself rather than its predecessor and breaks deletion.
  • Unbounded randomLevel — cap at MAX_LEVEL sized for the expected n (log₂ n + a few).

Interview patterns

  • Design Skipset (LeetCode 1206): search, add, erase.
  • Explain expected O(log n) via coin flips and levels.
  • Compare with red-black trees for a concurrent ordered map (why Redis and Java chose skip lists).
  • Extend with span counts for rank / k-th smallest.
Interview questions on this
Mock interviews

Interview problems

Insert Delete GetRandom O(1)mediumKth Largest Element in a StreameasyFind Median from Data Streamhard