Skip Lists: Layered Linked Lists for Fast Search

Skip lists are a probabilistic data structure that gives you O(log n) search, insertion, and deletion—comparable to balanced trees—but with dramatically simpler implementation. The idea is brilliant: layer multiple linked lists on top of each other, where higher layers act as “express lanes” that skip over many elements in the lower layers. Searching starts from the top layer and descends until finding the target or reaching the bottom.

The magic is in the probabilistic layer assignment. Each element has a 50% chance of appearing in level 1, 25% chance of appearing in level 2, 12.5% in level 3, and so on. This gives you roughly log₂(n) layers on average, with O(log n) expected search time. Because there’s no rebalancing logic (unlike AVL or Red-Black trees), concurrent implementations are far simpler—useful for high-throughput databases like Redis, which uses skip lists for sorted set operations.

Introduction

Skip lists are a probabilistic alternative to balanced trees that delivers O(log n) search, insertion, and deletion—comparable to AVL or Red-Black trees—but with simpler implementation. The idea is to layer multiple linked lists on top of each other, where higher layers act as express lanes that skip over many elements in the lower layers. Searching starts from the top layer and descends until finding the target or reaching the bottom.

The layer distribution comes from a geometric random process. Each element has a 50% chance of appearing in level 1, 25% in level 2, 12.5% in level 3, and so on. This guarantees roughly log₂(n) layers on average. Since there’s no rebalancing logic—no rotations to perform when inserts disrupt the balance—concurrent implementations are far simpler than their tree counterparts. This makes skip lists valuable in high-throughput systems like Redis, which uses them for sorted set operations.

This guide covers the search, insertion, and deletion algorithms with full implementations, explains the probabilistic analysis behind O(log n) expected performance, and discusses the practical advantages over balanced trees. You’ll learn when skip lists make more sense than trees (concurrent access, simple implementation, memory locality) and when their probabilistic guarantees might not be sufficient (systems requiring deterministic worst-case bounds).

When to Use

Skip lists excel when:

• Need sorted iteration — Unlike hash tables, maintains order
• Concurrent access — Lock-free variants exist; simpler than tree write locks
• Range queries — Efficiently iterate over sorted ranges
• Simple implementation — Half the code of balanced trees with equivalent performance
• Insertions interleaved with traversals — No rebalancing disruption

When Not to Use

• When deterministic O(log n) is required (probabilistic structures have non-zero chance of degrade)
• Memory is extremely constrained (skip lists use 2× pointers on average per node)
• When you need more than simple ordering (trees can be augmented with subtree metadata)

Architecture: Multi-Layer Express Lanes

graph LR
    subgraph L3["Level 3 (fastest)"]
        A3["1"] --> D3["10"]
    end
    subgraph L2["Level 2"]
        A2["1"] --> B2["3"] --> D2["10"]
    end
    subgraph L1["Level 1 (base)"]
        A1["1"] --> B1["3"] --> C1["5"] --> D1["10"]
    end
    subgraph L0["Bottom (all elements)"]
        A0["1"] --> B0["3"] --> C0["5"] --> D0["7"] --> E0["10"] --> F0["12"]
    end

Search from top level, move horizontally until overshoot, then descend. Higher levels skip more elements.

Implementation

Basic Skip List

import random

class SkipListNode:
    def __init__(self, value, max_level=16):
        self.value = value
        self.forward = [None] * max_level


class SkipList:
    """
    Skip list with O(log n) search, insert, delete.
    Probability p = 0.5 for level promotion.
    """

    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level
        self.p = p
        self.header = SkipListNode(float('-inf'), max_level)
        self.level = 0  # Current max level

    def _random_level(self):
        """Generate random level with geometric distribution."""
        level = 0
        while random.random() < self.p and level < self.max_level - 1:
            level += 1
        return level

    def search(self, target):
        """
        Find element or return None.
        Time: O(log n) expected
        """
        current = self.header
        update = [None] * self.max_level

        # Start from top level, descend
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < target:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]

        if current and current.value == target:
            return current.value
        return None

    def insert(self, value):
        """
        Insert element into skip list.
        Time: O(log n) expected
        """
        update = [None] * self.max_level
        current = self.header

        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]

        if current is None or current.value != value:
            new_level = self._random_level()

            if new_level > self.level:
                for i in range(self.level + 1, new_level + 1):
                    update[i] = self.header
                self.level = new_level

            new_node = SkipListNode(value, self.max_level)

            for i in range(new_level + 1):
                new_node.forward[i] = update[i].forward[i]
                update[i].forward[i] = new_node

    def delete(self, value):
        """
        Delete element from skip list.
        Time: O(log n) expected
        """
        update = [None] * self.max_level
        current = self.header

        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]

        if current and current.value == value:
            for i in range(self.level + 1):
                if update[i].forward[i] == current:
                    update[i].forward[i] = current.forward[i]

            while self.level > 0 and self.header.forward[self.level] is None:
                self.level -= 1

            return True
        return False

    def display(self):
        """Visualize skip list levels."""
        for i in range(self.level, -1, -1):
            line = f"Level {i}: "
            node = self.header.forward[i]
            while node:
                line += f"[{node.value}] -> "
                node = node.forward[i]
            print(line + "None")

Production Failure Scenarios

1. Unbalanced structure from bad randomness: Every skip list implementation eventually hits a streak of bad random levels. I’ve seen production systems where a faulty RNG seed caused search times to spike 10× above normal. Use a proper seed source (time-based or CSPRNG at startup), not whatever default your language gives you.

2. Memory overhead from high max_level: Each node stores max_level forward pointers. Set max_level too high relative to your actual element count and you’re burning memory for no benefit. A good rule: max_level = log₂(expected_max_elements) + 3 gives you breathing room without waste.

3. Worst-case O(n) performance under adversarial input: The “expected” in O(log n) expected is doing a lot of work. An attacker who knows your random level generation can craft insertions that produce pathological structures. If you’re in an adversarial context (network-facing), use a CSPRNG and add level jitter.

Common Pitfalls / Anti-Patterns

1. Confusing level indexing — Level 0 is the base list with all elements
2. Off-by-one in random level — Should be < max_level - 1 in while condition
3. Not updating level after delete — Must check if top level became empty
4. Using fixed random seed in production — May cause predictable patterns under attack

Observability Checklist

Track skip list operations to catch probabilistic degradation and correctness issues.

Core Metrics

• Search operation count and latency per call
• Insert/delete operation count
• Average level vs expected log₂(n) — if this drifts above 2×, something’s wrong with level generation
• Level distribution across all nodes — watch for too many nodes at level 0
• Current level count vs max_level — hitting max_level constantly means you need to raise it

Health Signals

• Search latency climbing: your list might be unbalanced or your random source might be broken
• Average level above 2× log₂(n): random level generation is biased or under attack
• Level count hitting max_level frequently: either traffic is higher than expected or an attacker is probing
• Delete operations not reducing level: this is a bug in your level maintenance logic
• Search returning wrong elements: memory corruption or a concurrent write race

Alerting Thresholds

• Search latency > 2× log₂(n) consistently: probabilistic degradation happening
• Level distribution skew > 3σ from expected: random generator issue or deliberate attack
• Level count == max_level for extended periods: capacity planning needed
• Any null pointer in forward chain during traversal: memory corruption — page it immediately

Distributed Tracing

• Trace search with level visited count and comparisons per level
• Include level distribution in span metadata — you’ll want this when debugging slow searches
• Track insert/delete with new level assigned
• Correlate slow searches with specific level distributions

Trade-off Analysis

Aspect	Skip Lists	Balanced Trees (AVL/Red-Black)	B-Trees
Search Time	O(log n) expected	O(log n) guaranteed	O(log n) guaranteed
Insert/Delete	O(log n) expected	O(log n) + rebalancing	O(log n) + page splits
Implementation	~200 lines	~500 lines	~400 lines
Concurrent Access	Lock-free CAS possible	Complex tree rotations	Page-level locking
Memory Overhead	2× pointers/node avg	2-3 pointers/node	Pointer + page metadata
Worst-case	O(n) with bad RNG	O(log n) always	O(log n) always
Cache Friendliness	Poor (pointer chasing)	Moderate	Excellent (sequential page access)
Range Queries	O(log n + k)	O(log n + k)	O(log n + k)

When to prefer each:

• Skip lists: In-memory, simple concurrent access, rapid iteration
• Balanced trees: Guaranteed performance, simpler disk layout
• B-trees: Disk-based storage, page-oriented access patterns

Security Notes

Random seed manipulation: If an attacker controls or predicts your random seed, they can force your skip list into worst-case behavior. I once traced a latency spike to an adversarial client who had reverse-engineered our level-0-only attack pattern. The fix was switching to a CSPRNG seeded at process start — don’t use language defaults in security-sensitive paths.

Level 0 targeted attacks: Someone watching your list (through timing side channels or memory access patterns) can infer your level distribution and craft insertions that bury specific elements at level 0, inflating search time for targets they care about. Add padding to level generation so observations don’t reveal structure.

Concurrent modification races: In concurrent environments, a search can cross a level while another thread is updating pointers at that level, seeing partially constructed nodes or stale forward pointers. Naive locking helps but doesn’t fully solve it — use lock-free CAS operations and node versioning so readers can detect and retry when they see an in-progress update.

Quick Recap Checklist

• Level 0 contains all elements (like base linked list)
• Higher levels skip elements in lower levels
• Random level follows geometric distribution (p^k probability)
• Search descends from top level, moves horizontally, repeats
• O(log n) is expected (probabilistic), not guaranteed

Interview Questions

Further Reading

Core References:

• Pugh, W. (1990) - “Skip Lists: A Probabilistic Alternative to Balanced Trees” - Original paper describing the data structure
• Redis Source - t_zset.c implements skiplist-based sorted sets

Deep Dives:

• Lock-free Skip Lists - Herlihy et al. on concurrent variants
• Probabilistic Analysis of Skip Lists - rigorous expected bounds
• CSPRNG for Production - Python’s secrets module for secure random

Implementations:

• Java util.concurrent ConcurrentSkipListMap - production-grade lock-free
• Go’s sync.Map uses skip list ideas internally

Conclusion