Skip List

A skip list is a probabilistic, ordered, linked data structure that supports search, insert, and delete in O(log n) expected time by stacking multiple “express lane” linked lists on top of a base list. Each element is independently promoted to higher levels with probability p (typically 1/2 or 1/4). Skip lists were introduced by William Pugh in his 1990 CACM paper as a simpler alternative to balanced binary search trees — no rotations, no rebalancing logic, just a coin flip per insert. They are the data structure behind Redis sorted sets (ZSET, ZADD/ZRANGE), LevelDB and RocksDB MemTables, and Java’s ConcurrentSkipListMap / ConcurrentSkipListSet. The conceptual claim Pugh made — that random promotion can replace the deterministic algebra of red-black or AVL trees — is one of the cleaner ideas in data structures.

1. Intuition — The Subway Express + Local

Imagine a subway line with 32 stops. The local train stops at every one of them; finding stop #19 from stop #1 takes 18 hops on the local. So the city builds:

An express train that stops only at every 4th station (stops 1, 5, 9, 13, 17, 21, …).
A super-express that stops only at every 16th station (1, 17, 33, …).

To get from stop 1 to stop 19, you take the super-express to stop 17 (1 hop), the express to no useful stop (or skip), the local to stop 19 (2 hops). About 3 hops instead of 18.

A skip list does exactly this for an ordered linked list. The bottom layer (level 0) is the full sorted linked list. Layer 1 contains a randomly-chosen ~half of those nodes, linked left-to-right. Layer 2 contains a randomly-chosen ~half of those nodes. And so on. To find a key, you start at the top-left and walk right while the next node’s key ≤ target; when you’d overshoot, drop down a level and continue. Each level halves the search distance, giving O(log n) expected hops.

The trick that makes it elegant: the random promotion decides each node’s height independently — flip a coin at insert time, and the node belongs to level L where L is the number of consecutive heads (geometric distribution). No rebalancing operation ever needs to move a node, split it, or rotate its neighbors. The structure is “balanced” in expectation, not by enforcement. That’s the conceptual leap from balanced trees: trade deterministic worst-case bounds for probabilistic expected bounds, and gain enormous implementation simplicity.

2. Tiny Worked Example

Insert 3, 6, 7, 9, 12, 19, 17, 26, 21, 25 into an empty skip list. Suppose the random promotions happen to produce these heights (1 = base level only, higher = also in upper express lanes):

Key	Height
3	1
6	4
7	1
9	2
12	1
17	2
19	1
21	1
25	3
26	1

The resulting structure (HEAD is a left sentinel that’s tallest):

Lvl 4: HEAD ───────────────────────► 6 ────────────────────────────────────► NIL
Lvl 3: HEAD ───────────────────────► 6 ──────────────────────► 25 ─────────► NIL
Lvl 2: HEAD ───────────────────────► 6 ──► 9 ────────► 17 ──► 25 ─────────► NIL
Lvl 1: HEAD ──► 3 ──► 6 ──► 7 ──► 9 ──► 12 ──► 17 ──► 19 ──► 21 ──► 25 ──► 26 ──► NIL

Search for key 21. Start at top-left (HEAD level 4):

Lvl 4: next is 6, 6 ≤ 21 → step right to 6. Next is NIL → drop to lvl 3.
Lvl 3 from 6: next is 25, 25 > 21 → drop to lvl 2.
Lvl 2 from 6: next is 9, 9 ≤ 21 → step. From 9: next is 17, 17 ≤ 21 → step. From 17: next is 25, 25 > 21 → drop to lvl 1.
Lvl 1 from 17: next is 19, 19 ≤ 21 → step. From 19: next is 21, equal → found.

Total hops: 5. The base list alone (HEAD → 3 → 6 → 7 → 9 → 12 → 17 → 19 → 21) would have taken 8 hops. The advantage compounds for larger n — at n = 1,000,000, search takes ~2 log₂ n ≈ 40 hops (or ~20 if you count level-drops as part of the path) vs ~500,000 for a plain linked list.

Insert key 14. First find the predecessor of 14 at every level (the rightmost node with key < 14): at level 1 that is 12, at level 2 it is 9, and at levels 3–4 it is 6. These predecessors are exactly the update[] array. Flip coins to determine 14’s height — say it comes up height 2. Splice it in at levels 1 and 2, between each captured predecessor and that predecessor’s old successor:

Lvl 2: ... 9 ──► 14 ──► 17 ...
Lvl 1: ... 12 ──► 14 ──► 17 ...

No rotations, no rebalance — the structure remains a valid skip list because the random-promotion property is independent across nodes.

3. The Algorithm

3.1 Geometric height generation

function random_height(p, max_level):
    h = 1
    while random() < p and h < max_level:
        h = h + 1
    return h

With p = 1/2 the average height is 1/(1−p) = 2; with p = 1/4 it’s 1/(1−1/4) = 4/3. Smaller p → fewer pointers per node (less memory). The effect on search speed is more subtle than “smaller p is slower”: Pugh’s Table 1 normalizes search time as L(n)/p and shows p = 1/2 and p = 1/4 are essentially tied (both 1.0 in his table), with p = 1/8 being where search starts to degrade (1.33×) and p = 1/16 doubling it. So Pugh actually recommends p = 1/4 as the default — it cuts memory to 1/(1−1/4) ≈ 1.33 pointers per node with no meaningful search penalty — and only suggests p = 1/2 “unless the variability of running times is a primary concern” (smaller p increases the variance of the running time). Decreasing p below 1/4 trades real search speed for marginal extra memory savings, which is rarely worth it.

max_level is set to L(N) = log_{1/p} N, where N is an upper bound on the number of elements (Pugh’s “Determining MaxLevel” section). For p = 1/2 and N = 2¹⁶, MaxLevel = 16; for N = 2³², MaxLevel = 32.

3.2 Search

function search(key):
    x = head
    for level = top_level downto 1:
        while x.next[level] != NIL and x.next[level].key < key:
            x = x.next[level]
    x = x.next[1]
    if x != NIL and x.key == key:
        return x.value
    return NOT_FOUND

The pattern “walk right while you can, then drop down” is the entire search algorithm.

3.3 Insert

function insert(key, value):
    update[1..max_level] = array of node pointers
    x = head
    for level = top_level downto 1:
        while x.next[level] != NIL and x.next[level].key < key:
            x = x.next[level]
        update[level] = x                # rightmost node strictly < key, at this level

    h = random_height(p, max_level)
    if h > top_level:
        for level = top_level + 1 to h:
            update[level] = head
        top_level = h

    new_node = Node(key, value, height=h)
    for level = 1 to h:
        new_node.next[level] = update[level].next[level]
        update[level].next[level] = new_node

The update[] array captures the predecessor at every level — exactly the insertion point. Splice the new node in at levels 1..h (its random height).

3.4 Delete

function delete(key):
    update[1..max_level] = ...           # same predecessor capture as insert
    x = update[1].next[1]
    if x == NIL or x.key != key: return false
    for level = 1 to top_level:
        if update[level].next[level] != x: break
        update[level].next[level] = x.next[level]
    while top_level > 1 and head.next[top_level] == NIL:
        top_level = top_level - 1
    return true

Splice the node out of every level it appears in, then trim empty top levels.

4. Python Implementation

A runnable, didactic skip list with insert, search, delete, and sorted iteration:

import random
 
class _Node:
    __slots__ = ("key", "val", "next")
    def __init__(self, key, val, height):
        self.key, self.val = key, val
        self.next = [None] * height       # next[i] = forward pointer at level i
 
class SkipList:
    """Pugh-style probabilistic skip list. p = 1/2, max_level = 32."""
 
    def __init__(self, p: float = 0.5, max_level: int = 32):
        self.p = p
        self.max_level = max_level
        self.head = _Node(key=None, val=None, height=max_level)
        self.top  = 0                     # highest level currently in use
 
    def _random_height(self) -> int:
        h = 1
        while random.random() < self.p and h < self.max_level:
            h += 1
        return h
 
    def _find_predecessors(self, key) -> list[_Node]:
        update = [self.head] * self.max_level
        x = self.head
        for lvl in range(self.top, -1, -1):
            while x.next[lvl] is not None and x.next[lvl].key < key:
                x = x.next[lvl]
            update[lvl] = x
        return update
 
    def search(self, key):
        x = self.head
        for lvl in range(self.top, -1, -1):
            while x.next[lvl] is not None and x.next[lvl].key < key:
                x = x.next[lvl]
        x = x.next[0]
        return x.val if x is not None and x.key == key else None
 
    def insert(self, key, val) -> None:
        update = self._find_predecessors(key)
        # If key exists, just update value.
        candidate = update[0].next[0]
        if candidate is not None and candidate.key == key:
            candidate.val = val
            return
        h = self._random_height()
        if h - 1 > self.top:
            self.top = h - 1
        node = _Node(key, val, h)
        for lvl in range(h):
            node.next[lvl] = update[lvl].next[lvl]
            update[lvl].next[lvl] = node
 
    def delete(self, key) -> bool:
        update = self._find_predecessors(key)
        node = update[0].next[0]
        if node is None or node.key != key:
            return False
        for lvl in range(len(node.next)):
            if update[lvl].next[lvl] is node:
                update[lvl].next[lvl] = node.next[lvl]
        while self.top > 0 and self.head.next[self.top] is None:
            self.top -= 1
        return True
 
    def __iter__(self):
        x = self.head.next[0]
        while x is not None:
            yield (x.key, x.val)
            x = x.next[0]
 
# --- demo ---------------------------------------------------------------
if __name__ == "__main__":
    sl = SkipList()
    for k in (3, 6, 7, 9, 12, 19, 17, 26, 21, 25):
        sl.insert(k, f"v{k}")
    print(list(sl))                       # sorted iteration, "for free"
    print("search 17:", sl.search(17))
    print("delete 9:", sl.delete(9))
    print("search 9:", sl.search(9))

A few implementation notes worth understanding:

The update[] array is the magic. It captures the rightmost node < key at every level during the same descent that would do a search. Insert and delete reuse the search work — there’s no second pass.
__slots__ on _Node removes the per-instance __dict__, shrinking each node by ~50–60 bytes — significant when you have millions of nodes.
The head sentinel has full max_level height so the algorithm never has to special-case “is the new node taller than the head?”
No rotations, no balance factor, no color flips. Compare to a red-black tree implementation (typically 200+ lines including delete-fixup); the entire skip list above is under 70 lines.

5. Complexity / Math

5.1 Expected operation cost

Pugh’s 1990 paper proves (Section “Analysis of skip list algorithms”):

Expected search/insert/delete time: O(log n) for any constant p ∈ (0, 1).
Expected length of the search path (number of pointer hops), starting the search at level L(n) = log_{1/p} n, is at most L(n)/p + 1/(1−p) — Pugh’s exact bound. The number of comparisons is one more than the path length, i.e. L(n)/p + 1/(1−p) + 1. For p = 1/2: 2 log₂ n + 2 + 1, so the leading term is ~2 log₂ n hops — matching the note’s earlier estimate, now pinned to the exact formula.
Expected number of pointers per node: 1/(1−p). For p = 1/2 this is 2; for p = 1/4 it is 4/3 ≈ 1.33; for p = 1/e it is ≈ 1.58 (Pugh’s Table 1). Multiplying by n nodes gives the expected total node pointers (memory): n/(1−p) → 2n for p = 1/2, ~1.33n for p = 1/4.
Expected maximum level: L(n) + 1/(1−p) = log_{1/p} n + O(1). With p = 1/2 and n = 10⁶, this is ≈ 20 + 2.

5.2 Why O(log n) — proof sketch

A node is at level L with probability p^(L−1) · (1 − p) (it must come up L−1 heads then one tail), so the fraction of nodes reaching level i or higher is p^(i−1). The expected number of nodes at level i or higher is therefore n · p^(i−1).

Pugh’s elegant trick is to analyze the search path backwards — from the found node, climbing up and left toward the header. At any point in this backward climb we are at the i-th forward pointer of some node x, having no information about x’s level beyond ”≥ i”. With probability p, x’s level is greater than i, so the pointer we arrived on came from above — we climb up a level (Pugh’s “situation c”). With probability 1 − p, x’s level is exactly i — we move left to the previous node (situation b). Let C(k) be the expected number of steps to climb k levels in an (assumed-infinite) list. The recurrence is

C(k) = (1 − p)·(1 + C(k)) + p·(1 + C(k−1)),

which simplifies to C(k) = 1/p + C(k−1), and with C(0) = 0 gives the closed form C(k) = k/p. We climb to level L(n) = log_{1/p} n (cost L(n)/p), then bound the remaining leftward movements at the top by the expected number of level-≥L(n) nodes, which contributes 1/(1−p). Adding the two pieces yields the total expected search-path length

≤ L(n)/p + 1/(1−p) = O(log n),

exactly the bound quoted in §5.1. The reason we start the search at L(n) = log_{1/p} n rather than the actual top level is that this is the level at which we expect roughly 1/p nodes — high enough to skip aggressively, low enough that the few taller “freak” nodes above it add only a small constant to the cost.

5.3 Worst case

The worst case is O(n) — if every node randomly lands at level 1, the structure degenerates to a plain linked list and search is linear. The probability that all n nodes are level-1 only is (1−p)^n, which for p = 1/2 is (1/2)^n — vanishingly small. More usefully, Pugh quantifies the tail: for a dictionary of more than 250 elements with p = 1/2, the chance that a search takes more than 3× its expected time is less than one in a million (Pugh’s introduction; his Figure 8 plots the full upper-bound curve). Unlike an adversarially-ordered insert sequence into a naive BST, a skip list’s randomness is internal (from its own coin flips), so no input ordering can force the worst case — only freakishly bad luck can, and the analysis assumes an adversary who can delete but cannot see the coin flips.

5.4 Memory

Each node has a pointer per level it appears in. With p = 1/2:

Level 1: n nodes, 1 pointer each → n pointers.
Level 2: n/2 nodes, 1 pointer each → n/2 pointers.
Level 3: n/4 → n/4.
…
Total: n · (1 + 1/2 + 1/4 + …) = 2n pointers.

Plus key/value storage (same as any other map). The 2n pointer overhead is the price of the probabilistic balancing — slightly worse than a red-black tree’s ~2n pointers (left, right) but in the same ballpark.

6. Skip List vs Balanced BST (Red-Black, AVL)

	Skip List	Red-Black / AVL Tree
Search/insert/delete	O(log n) expected	O(log n) worst case
Memory	~2n pointers (p=1/2)	2n pointers + color/height bit
Implementation complexity	~60 lines	~200+ lines (insert + delete fixup)
Cache behavior	Pointer chasing across levels — moderate	Two pointers per node, depth-first — moderate
Concurrent variants	Lock-free implementations exist (Java’s ConcurrentSkipListMap)	Lock-free balanced trees are very hard
Range queries	O(k + log n) — walk base list	O(k + log n) — in-order
Persistent (functional) variants	possible, less standard	well-studied

The big practical reasons skip lists beat balanced trees:

Far simpler to implement correctly. A red-black tree’s delete-fixup has roughly six cases; getting them right under interview pressure is hard. A skip list’s delete is a loop. The probability of writing a buggy red-black tree in 30 minutes greatly exceeds that of a buggy skip list.
Concurrency. A lock-free skip list is achievable; a lock-free balanced tree is a research topic. Java’s ConcurrentSkipListMap (since Java 6, by Doug Lea) is the canonical example — high-throughput concurrent ordered map.
Range scans are natural. Both structures support O(k) range scans, but a skip list’s bottom level is literally a sorted linked list — ZRANGE on a Redis sorted set is exactly “walk this list.”

The reasons to prefer balanced trees:

Worst-case guarantees matter. A real-time system that cannot tolerate the (vanishingly small) chance of an O(n) operation prefers a tree.
Slightly better cache behavior in cold-cache scenarios — fewer pointers traversed on average.

Antirez's reasoning

Salvatore Sanfilippo (Redis creator, “antirez”) gave a widely-quoted explanation of why Redis uses skip lists for sorted sets rather than balanced trees, citing four reasons: (1) simpler to implement, debug, and extend — for instance he received a small patch adding ZRANK in O(log N) via augmented skip lists, which “required little changes to the code”; (2) range queries are natural — once you locate the start score you walk forward along level 1, whereas a BST needs an in-order traversal that revisits parents; (3) memory is tunable — by adjusting the level probability p a skip list can be made less memory-intensive than a balanced tree; and (4) the cache locality is “at least as good as” balanced trees (note: his actual phrasing is “at least as good as,” not “more cache-friendly than” — an earlier version of this note overstated the claim). The Redis implementation stores score and member separately, allows duplicate scores broken by lexicographic member comparison, and maintains backward pointers at level 1 for reverse-range (ZREVRANGE) queries.

7. Production Use Cases

Redis Sorted Sets (ZSET): a large sorted set is a “dual-ported” structure — a skip list keyed by score (for ZRANGE, ZRANGEBYSCORE, ZRANK) paired with a hash table mapping member → score (for O(1) point lookups by member). Per the Redis docs, every ZADD is therefore an O(log N) operation. A small sorted set is instead stored as a compact listpack (the successor to the old ziplist): Redis keeps it as a listpack while it has at most zset-max-listpack-entries members (default 128) and every member is at most zset-max-listpack-value bytes (default 64), and only converts to the skiplist+hashtable encoding once either threshold is exceeded — the listpack form is roughly 3× more memory-compact but only cheap to scan at small sizes.
LevelDB and RocksDB MemTables: the MemTable — the in-memory buffer that absorbs writes before they’re flushed to an SSTable on disk — is by default a skip list. Writes splice into it in O(log n); reads consult it before going to disk. LevelDB’s db/skiplist.h uses kBranching = 4 (so the promotion probability is p = 1/4, minimizing pointer overhead) and kMaxHeight = 12 (supporting up to ~4¹² ≈ 16 million entries before the height cap binds). (LevelDB source cited above.)
Apache HBase: MemStore historically used a ConcurrentSkipListMap. (Verify against current HBase versions — they’ve added alternatives.)
Java’s ConcurrentSkipListMap and ConcurrentSkipListSet: lock-free concurrent ordered maps in java.util.concurrent, by Doug Lea. The de facto choice for “concurrent ordered map” in Java.
Apache Lucene’s posting lists (in some configurations): skip lists used to skip over irrelevant document IDs during query intersection.
Cassandra’s MemTable (older versions): used skip lists; current versions have moved to other structures for write throughput.
Various transactional memory implementations: skip lists are easier to make lock-free than balanced trees.

Uncertain

Verify: the current default and available MemTable structures in RocksDB, HBase, and Cassandra. Reason: the skip-list MemTable is well-documented as the LevelDB/RocksDB default (confirmed in LevelDB’s db/skiplist.h), but RocksDB also ships alternative memtable factories (e.g. HashSkipList, HashLinkList, vector) selectable by configuration, and HBase/Cassandra have changed their in-memory structures across versions; these specific cross-system, cross-version facts were not pinned to each project’s current source here. To resolve: check each project’s current memtable/factory documentation and source.

8. Variants

8.1 Deterministic Skip List

Munro, Papadakis & Sedgewick (1992) replaced the random promotion with a deterministic rule (after every 1/p insertions at level L, promote one to L+1). Worst-case O(log n) at the cost of more complex insertion logic. Rarely used — defeats the simplicity argument.

8.2 Indexable Skip List

Augment each forward pointer with a width (number of base-level nodes it skips). Enables O(log n) select(k) (find the k-th smallest element) — useful for ZRANK in Redis, which Redis implements exactly this way.

8.3 Concurrent Lock-Free Skip List

Herlihy, Lev, Luchangco & Shavit (2007) gave a fully lock-free skip list. Used in Java’s ConcurrentSkipListMap. Insertion/deletion uses CAS (compare-and-swap) to splice nodes one level at a time; readers may briefly observe a node present at low levels but not yet at high levels — handled by the lookup logic re-checking.

8.4 Persistent Skip List

Functional/immutable variants used in some persistent data-structure libraries.

8.5 Fast Concurrent Hash + Skip List

Combine a hash map (O(1) point lookup) with a skip list (ordered iteration) — exactly what Redis does for sorted sets.

9. Pitfalls

9.1 PRNG Quality

A pathological random number generator can produce skewed heights and degrade performance. Use a well-seeded PRNG (e.g., the language’s default).

9.2 max_level Capping

max_level is a cap to avoid pathological towers (e.g., 100-level node from extreme luck). Set it generously — log₂(n_max) plus a safety margin. Too low caps performance under load; too high wastes per-node memory.

9.3 The `update[]` Array Allocation

A naive implementation allocates an update[] array on every operation — significant overhead. Reuse a thread-local buffer or stack-allocate.

9.4 Concurrent Modification Without Care

Plain skip lists are not thread-safe. Two concurrent inserts can corrupt the structure (interleaved splice operations leave dangling pointers). Either lock the whole structure, or use a lock-free design — but rolling your own lock-free skip list is hard. Use java.util.concurrent.ConcurrentSkipListMap rather than reimplementing.

9.5 Forgetting Backward Pointers for Reverse Range

Standard skip lists are forward-only. Range scans backward (e.g., ZREVRANGE in Redis) require backward pointers — Redis adds prev pointers at level 1 only.

9.6 Confusing p With Step Size

p is the promotion probability per level, not the step size. Higher p means more promotions, taller towers, more pointers, faster search. Lower p means fewer pointers, slower search. The trade is memory vs speed.

9.7 Worst-Case Anxiety

The worst case is O(n). For interview questions about real-time / hard-deadline systems, the interviewer may expect you to volunteer that skip lists give expected (not worst-case) bounds and that a balanced tree is the safer choice if the worst case is unacceptable.

10. Diagram — Skip List Structure

flowchart LR
    subgraph "Level 4 — express×8"
        H4[HEAD] --> N6_4["6"] --> NIL4[NIL]
    end
    subgraph "Level 3 — express×4"
        H3[HEAD] --> N6_3["6"] --> N25_3["25"] --> NIL3[NIL]
    end
    subgraph "Level 2 — express×2"
        H2[HEAD] --> N6_2["6"] --> N9_2["9"] --> N17_2["17"] --> N25_2["25"] --> NIL2[NIL]
    end
    subgraph "Level 1 — local (sorted base list)"
        H1[HEAD] --> N3["3"] --> N6_1["6"] --> N7["7"] --> N9_1["9"] --> N12["12"] --> N17_1["17"] --> N19["19"] --> N21["21"] --> N25_1["25"] --> N26["26"] --> NIL1[NIL]
    end

What this diagram shows. The base level (Level 1) is a simple sorted singly-linked list — by itself, search is O(n). Higher levels are progressively sparser linked lists where each node was independently coin-flipped into existence at that level. A search starts at top-left and walks right while next ≤ target; on overshoot, drops down a level. The “express lanes” mean each level approximately halves (with p = 1/2) the remaining search distance, giving expected O(log n) hops. Crucially, no node ever moves: insert just splices a new node into 1, 2, 3, … random levels; delete just unsplices it. There is no rebalance step.

11. Common Interview Problems

Problem	Source	What’s tested
Design Skiplist	LeetCode 1206	The implementation in §4
Design In-Memory Sorted Set	system-design round	Skip list + hash map (the Redis ZSET design)
Design Range-Query Service	system-design round	Skip list as base structure
Design Leaderboard	system-design round	Sorted set semantics → skip list
Design KV Store with Range Scans	system-design round	LSM tree → skip list MemTable
Compare Skip List vs Red-Black Tree	system-design round	The §6 trade-offs

In coding rounds the “implement a skip list” problem (LC 1206) is rare but does come up — it’s a great test of probabilistic-data-structure understanding combined with linked-list manipulation skill.

12. Open Questions

Is there empirical evidence that skip lists beat B-trees for in-memory ordered map workloads at typical sizes, or is it a wash?
Why did Cassandra move away from skip-list MemTables in newer versions? (Throughput? Allocation pressure? Off-heap concerns?)
How does the cache behavior of skip lists compare to B-trees on modern CPUs? Folklore says skip lists are competitive; I haven’t found a definitive benchmark.

13. See Also

Binary Search Tree — deterministic O(log n) cousin
Red-Black Tree — the comparison standard
AVL Tree — strictly-balanced cousin
Hash Table — paired with skip list to form Redis ZSETs
LSM Tree — uses skip lists in MemTables (LevelDB, RocksDB)
Big-O Notation — expected vs worst-case
Bloom Filter — sibling probabilistic data structure
Probabilistic Data Structures — broader topic
Concurrent Data Structures — lock-free skip list as a key example
Splay Tree — self-adjusting BST; the amortized (vs skip-list probabilistic) route to “balanced trees without rebalancing logic,” and far harder to make concurrent because every read mutates the structure
SWE Interview Preparation MOC

vault

Explorer

Skip List

Skip List

1. Intuition — The Subway Express + Local

2. Tiny Worked Example

3. The Algorithm

3.1 Geometric height generation

3.2 Search

3.3 Insert

3.4 Delete

4. Python Implementation

5. Complexity / Math

5.1 Expected operation cost

5.2 Why O(log n) — proof sketch

5.3 Worst case

5.4 Memory

6. Skip List vs Balanced BST (Red-Black, AVL)

7. Production Use Cases

8. Variants

8.1 Deterministic Skip List

8.2 Indexable Skip List

8.3 Concurrent Lock-Free Skip List

8.4 Persistent Skip List

8.5 Fast Concurrent Hash + Skip List

9. Pitfalls

9.1 PRNG Quality

9.2 max_level Capping

9.3 The `update[]` Array Allocation

9.4 Concurrent Modification Without Care

9.5 Forgetting Backward Pointers for Reverse Range

9.6 Confusing p With Step Size

9.7 Worst-Case Anxiety

10. Diagram — Skip List Structure

11. Common Interview Problems

12. Open Questions

13. See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

Skip List

Skip List

1. Intuition — The Subway Express + Local

2. Tiny Worked Example

3. The Algorithm

3.1 Geometric height generation

3.2 Search

3.3 Insert

3.4 Delete

4. Python Implementation

5. Complexity / Math

5.1 Expected operation cost

5.2 Why O(log n) — proof sketch

5.3 Worst case

5.4 Memory

6. Skip List vs Balanced BST (Red-Black, AVL)

7. Production Use Cases

8. Variants

8.1 Deterministic Skip List

8.2 Indexable Skip List

8.3 Concurrent Lock-Free Skip List

8.4 Persistent Skip List

8.5 Fast Concurrent Hash + Skip List

9. Pitfalls

9.1 PRNG Quality

9.2 max_level Capping

9.3 The update[] Array Allocation

9.4 Concurrent Modification Without Care

9.5 Forgetting Backward Pointers for Reverse Range

9.6 Confusing p With Step Size

9.7 Worst-Case Anxiety

10. Diagram — Skip List Structure

11. Common Interview Problems

12. Open Questions

13. See Also

Graph View

Table of Contents

Backlinks

9.3 The `update[]` Array Allocation