Skip List: A Probabilistic Alternative to Balanced Trees

A skip list is a data structure that uses multiple layers of linked lists stacked on top of each other to achieve O(log n) average-case search, insertion, and deletion — the same guarantees as balanced binary search trees, but with a much simpler implementation. Instead of complex rotations (AVL, red-black), skip lists use randomization to stay balanced.

The Problem with Plain Linked Lists

A sorted linked list supports insertion in O(1) (once you find the position), but searching takes O(n) because you must scan from the head. Binary search does not work on linked lists because there is no random access.

What if we added “express lanes” — extra layers of links that let us skip over large sections of the list?

How Skip Lists Work

Imagine a sorted linked list: 1 → 3 → 5 → 7 → 9 → 12 → 15 → 20.

Now add a second level that links every other element: 1 → 5 → 9 → 15.

Add a third level that links every fourth element: 1 → 9.

Add a top level with just the first element: 1.

To search for 12:

1. Level 3: Start at 1. Next is 9. 9 < 12, move right to 9. Next is None, go down.
2. Level 2: At 9. Next is 15. 15 > 12, go down.
3. Level 1: At 9. Next is 12. Found!

Instead of scanning 6 nodes (as in a plain list), we scanned only 3. The express lanes let us skip past irrelevant nodes.

Probabilistic Balancing

In practice, we do not deterministically promote every other node. Instead, we use a coin flip: when inserting a new node, we flip a coin to decide how many levels it should have. With probability p (usually 0.5), we promote the node to the next level.

Level promotion probability:
  Level 0: 100% (every node)
  Level 1: 50%
  Level 2: 25%
  Level 3: 12.5%
  ...
  Level k: (1/2)^k

On average, this produces the same geometric spacing as the deterministic version, but without requiring any rebalancing after insertions or deletions.

The Node Structure

Each node in a skip list has:

• A value (the key)
• An array of forward pointers, one for each level the node participates in

import random


class SkipNode:
    """A node in the skip list."""
    def __init__(self, val=-float('inf'), level=0):
        self.val = val
        # forward[i] points to the next node at level i
        self.forward = [None] * (level + 1)

    def __repr__(self):
        return f"SkipNode({self.val}, levels={len(self.forward)})"

The Skip List Class

class SkipList:
    """
    Skip list implementation with search, insert, and delete.
    Expected time for all operations: O(log n)
    Space: O(n) expected
    """

    def __init__(self, max_level=16, p=0.5):
        """
        max_level: Maximum number of levels (log2 of expected max size)
        p: Probability of promoting a node to the next level
        """
        self.max_level = max_level
        self.p = p
        self.level = 0  # Current highest level in use
        # Header node with max_level forward pointers
        self.header = SkipNode(-float('inf'), max_level)
        self.size = 0

    def _random_level(self):
        """
        Generate a random level for a new node.
        Each level has probability p of being promoted.
        """
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

Search Operation

To search for a value, start at the highest level and move right until the next node’s value is greater than or equal to the target, then drop down one level. Repeat until level 0.

    def search(self, target):
        """
        Search for target in the skip list.
        
        Returns True if found, False otherwise.
        Expected time: O(log n), Worst case: O(n)
        """
        current = self.header

        # Start from the highest level and work down
        for i in range(self.level, -1, -1):
            # Move right while next node's value is less than target
            while (current.forward[i] and
                   current.forward[i].val < target):
                current = current.forward[i]

        # Move to the candidate node at level 0
        current = current.forward[0]

        # Check if we found the target
        return current is not None and current.val == target

Search Trace

Searching for 12 in the list [1, 3, 5, 7, 9, 12, 15, 20]:

Level 3: header → 1 → None
         At 1, next is None → go down

Level 2: At 1 → 5 → 9 → None
         At 1, next=5, 5 < 12 → move to 5
         At 5, next=9, 9 < 12 → move to 9
         At 9, next=None → go down

Level 1: At 9 → 12
         At 9, next=12, 12 not < 12 → go down

Level 0: At 9 → forward[0] = 12
         12 == 12 → Found!

Total comparisons: 5 (versus 6 for linear scan).

Insert Operation

Insertion requires finding the correct position at every level and updating forward pointers:

    def insert(self, val):
        """
        Insert a value into the skip list.
        
        Expected time: O(log n)
        """
        # update[i] will hold the node just before the insertion point at level i
        update = [None] * (self.max_level + 1)
        current = self.header

        # Find insertion position at each level
        for i in range(self.level, -1, -1):
            while (current.forward[i] and
                   current.forward[i].val < val):
                current = current.forward[i]
            update[i] = current

        # current is now the node just before where we want to insert
        # Check if value already exists
        current = current.forward[0]
        if current and current.val == val:
            return  # Duplicate — skip (or update if this were a map)

        # Generate random level for new node
        new_level = self._random_level()

        # If new level is higher than current max, update header
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.header
            self.level = new_level

        # Create the new node
        new_node = SkipNode(val, new_level)

        # Insert at each level by updating forward pointers
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

        self.size += 1

Insert Trace

Inserting 10 with random level = 2:

Before: Level 0: 1 → 3 → 5 → 7 → 9 → 12 → 15 → 20
        Level 1: 1 → 5 → 9 → 15
        Level 2: 1 → 9

Step 1: Find update[] at each level
  Level 2: 1 → 9 (9 < 10, stop at 9). update[2] = 9
  Level 1: 9 → 15 (15 > 10, stop at 9). update[1] = 9
  Level 0: 9 → 12 (12 > 10, stop at 9). update[0] = 9

Step 2: Create SkipNode(10, level=2)

Step 3: Update forward pointers
  Level 0: 9 → 10 → 12  (was 9 → 12)
  Level 1: 9 → 10 → 15  (was 9 → 15)
  Level 2: 9 → 10 → None (was 9 → None)

After: Level 0: 1 → 3 → 5 → 7 → 9 → 10 → 12 → 15 → 20
       Level 1: 1 → 5 → 9 → 10 → 15
       Level 2: 1 → 9 → 10

Delete Operation

Deletion is symmetric to insertion — find the node at each level and update forward pointers to skip it:

    def delete(self, val):
        """
        Delete a value from the skip list.
        
        Expected time: O(log n)
        Returns True if deleted, False if not found.
        """
        update = [None] * (self.max_level + 1)
        current = self.header

        # Find the node at each level
        for i in range(self.level, -1, -1):
            while (current.forward[i] and
                   current.forward[i].val < val):
                current = current.forward[i]
            update[i] = current

        # Check if value exists at level 0
        target = current.forward[0]
        if not target or target.val != val:
            return False  # Not found

        # Remove from each level
        for i in range(self.level + 1):
            if update[i].forward[i] is not target:
                break
            update[i].forward[i] = target.forward[i]

        # Reduce level if top levels are now empty
        while self.level > 0 and self.header.forward[self.level] is None:
            self.level -= 1

        self.size -= 1
        return True

Display and Utility Methods

    def display(self):
        """Print the skip list level by level."""
        print(f"Skip List (size={self.size}, levels={self.level + 1}):")
        for i in range(self.level, -1, -1):
            nodes = []
            node = self.header.forward[i]
            while node:
                nodes.append(str(node.val))
                node = node.forward[i]
            print(f"  Level {i}: {' → '.join(nodes)}")

    def to_list(self):
        """Return all values as a sorted Python list."""
        result = []
        node = self.header.forward[0]
        while node:
            result.append(node.val)
            node = node.forward[0]
        return result

    def __contains__(self, val):
        """Support 'val in skip_list' syntax."""
        return self.search(val)

    def __len__(self):
        return self.size

Complete Example

# Create a skip list and perform operations
sl = SkipList()

# Insert values
for val in [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]:
    sl.insert(val)

sl.display()
# Example output (levels vary due to randomness):
# Skip List (size=10, levels=4):
#   Level 3: 6
#   Level 2: 6 → 9 → 21
#   Level 1: 3 → 6 → 9 → 17 → 21 → 25
#   Level 0: 3 → 6 → 7 → 9 → 12 → 17 → 19 → 21 → 25 → 26

# Search
print(sl.search(19))    # True
print(sl.search(20))    # False
print(19 in sl)          # True

# Delete
sl.delete(19)
print(sl.search(19))    # False
print(sl.to_list())     # [3, 6, 7, 9, 12, 17, 21, 25, 26]
print(len(sl))           # 9

Complexity Analysis

Operation	Expected	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Space	O(n)	O(n log n)

Why O(log n) Expected?

With promotion probability p = 0.5:

• The expected number of levels is O(log n)
• At each level, we examine at most O(1/p) = O(2) nodes on average before dropping down
• Total expected comparisons: O(log n) levels x O(1) comparisons per level = O(log n)

Why O(n) Worst Case?

In the worst case, every coin flip gives the same result and all nodes end up at level 0. This degenerates to a plain linked list with O(n) search. However, this is astronomically unlikely for any reasonable n.

Skip Lists vs. Balanced BSTs

Feature	Skip List	AVL Tree	Red-Black Tree
Search	O(log n) expected	O(log n) worst	O(log n) worst
Insert	O(log n) expected	O(log n) worst	O(log n) worst
Delete	O(log n) expected	O(log n) worst	O(log n) worst
Implementation	Simple	Complex rotations	Very complex
Concurrency	Easy (lock per level)	Hard (tree rotations)	Hard
Range queries	Natural (follow level 0)	In-order traversal	In-order traversal
Space overhead	~2n pointers expected	2n pointers (left, right)	2n + n bits
Worst case guarantee	No (probabilistic)	Yes (deterministic)	Yes (deterministic)

Why Choose Skip Lists?

1. Simplicity: No rotations, no color-flipping, no case analysis. The code is straightforward.
2. Concurrency: You can lock individual nodes at specific levels, making concurrent skip lists easier to implement than concurrent BSTs.
3. Range queries: To get all values between A and B, find A (O(log n)), then walk level 0 until you pass B. No in-order traversal needed.
4. Cache performance: Level 0 is a plain linked list, which is sequential in memory allocation order.

Why Choose BSTs Instead?

1. Worst-case guarantees: If you absolutely need O(log n) in the worst case, AVL or red-black trees are better.
2. Determinism: Skip lists depend on randomness. In adversarial settings (security, real-time systems), deterministic structures are safer.
3. Space: AVL trees use exactly 2 pointers per node. Skip lists use 2 on average but can use more.

Redis Sorted Sets: A Real-World Use Case

Redis, the popular in-memory database, uses skip lists as the underlying data structure for sorted sets (ZSET). Here is why:

1. ZRANGEBYSCORE (range queries) are natural on skip lists — find the start, walk level 0
2. ZRANK (rank of an element) is supported by augmenting nodes with a span counter
3. Concurrent access is simpler with skip lists than with balanced trees
4. Implementation simplicity means fewer bugs in a critical system

From the Redis source code comment by Salvatore Sanfilippo (antirez):

“Skip lists are simpler to implement, debug, and modify compared to balanced trees. They are not slower in practice for the operations we need.”

Augmented Skip List for Rank Queries

Redis adds a span field to each forward pointer, tracking how many level-0 nodes each link skips over:

class AugmentedSkipNode:
    """Skip list node with span for rank queries."""
    def __init__(self, val=-float('inf'), level=0):
        self.val = val
        self.forward = [None] * (level + 1)
        self.span = [0] * (level + 1)  # span[i] = nodes skipped at level i


def get_rank(skip_list, target):
    """
    Get the 0-indexed rank of target in the skip list.
    Time: O(log n) expected
    """
    rank = 0
    current = skip_list.header

    for i in range(skip_list.level, -1, -1):
        while (current.forward[i] and
               current.forward[i].val < target):
            rank += current.span[i]
            current = current.forward[i]

    # Move to the target at level 0
    if current.forward[0] and current.forward[0].val == target:
        rank += current.span[0]
        return rank - 1  # 0-indexed

    return -1  # Not found

Choosing the Right Parameters

Max Level

The max level should be approximately log2(n) where n is the expected maximum number of elements:

import math

def optimal_max_level(expected_size, p=0.5):
    """Calculate optimal max level for a skip list."""
    return int(math.log(expected_size, 1 / p))

# Examples
print(optimal_max_level(1000))     # 9
print(optimal_max_level(1000000))  # 19
print(optimal_max_level(10**9))    # 29

Promotion Probability

• p = 0.5 is the most common choice. It gives O(log2 n) levels and 2n expected total pointers.
• p = 0.25 gives O(log4 n) levels with fewer pointers (1.33n expected) but slightly more comparisons per level.
• p = 0.5 is usually optimal for in-memory skip lists. p = 0.25 is better when memory is a concern.

Iterating Over a Skip List

One advantage of skip lists is that iteration is trivial — just follow level 0:

def iterate_skip_list(skip_list):
    """Iterate over all values in sorted order."""
    node = skip_list.header.forward[0]
    while node:
        yield node.val
        node = node.forward[0]


def range_query(skip_list, low, high):
    """
    Return all values in [low, high].
    Time: O(log n + k) where k is the number of results
    """
    results = []
    current = skip_list.header

    # Find the first node >= low
    for i in range(skip_list.level, -1, -1):
        while (current.forward[i] and
               current.forward[i].val < low):
            current = current.forward[i]

    # Walk level 0 until we pass high
    current = current.forward[0]
    while current and current.val <= high:
        results.append(current.val)
        current = current.forward[0]

    return results


# Example
sl = SkipList()
for v in [1, 3, 5, 7, 9, 11, 13, 15]:
    sl.insert(v)

print(range_query(sl, 5, 11))  # [5, 7, 9, 11]

Performance Benchmarks

Here is a simple benchmark comparing skip list operations to Python’s built-in bisect module (sorted list):

import time
import bisect

def benchmark(n=100000):
    """Compare skip list vs sorted list for n operations."""
    values = random.sample(range(n * 10), n)

    # Skip list insert
    sl = SkipList(max_level=20)
    start = time.time()
    for v in values:
        sl.insert(v)
    sl_insert_time = time.time() - start

    # Sorted list insert
    sorted_list = []
    start = time.time()
    for v in values:
        bisect.insort(sorted_list, v)
    sl_sorted_time = time.time() - start

    # Skip list search
    search_vals = random.sample(values, min(1000, n))
    start = time.time()
    for v in search_vals:
        sl.search(v)
    sl_search_time = time.time() - start

    # Sorted list search
    start = time.time()
    for v in search_vals:
        bisect.bisect_left(sorted_list, v)
    sorted_search_time = time.time() - start

    print(f"Insert {n} items:")
    print(f"  Skip list:   {sl_insert_time:.3f}s")
    print(f"  Sorted list: {sl_sorted_time:.3f}s")
    print(f"Search {len(search_vals)} items:")
    print(f"  Skip list:   {sl_search_time:.4f}s")
    print(f"  Sorted list: {sorted_search_time:.4f}s")


# benchmark()  # Uncomment to run

In Python, the sorted list with bisect is often faster due to C implementation and cache locality. However, in C/C++ implementations, skip lists are competitive, and their concurrency advantages make them the preferred choice in systems like Redis.

Practice Problems

1. LeetCode 1206 — Design Skiplist: Implement a skip list with search, add, and erase (Hard)
2. Design a leaderboard: Use a skip list to maintain ranked scores with efficient insert and rank queries
3. Implement an ordered set: Support insert, delete, search, and range queries in O(log n)
4. Concurrent skip list: Add lock-based or lock-free concurrency to the basic implementation
5. Compare skip list vs. red-black tree: Benchmark insert, search, and delete for various sizes

Key Takeaways

• A skip list is a multi-level linked list where higher levels act as express lanes for faster search.
• Probabilistic balancing (coin flip promotion) keeps the structure balanced without rotations. Expected height is O(log n).
• All operations (search, insert, delete) run in O(log n) expected time and O(n) expected space.
• Skip lists are simpler to implement than AVL or red-black trees and easier to make concurrent.
• Redis sorted sets use skip lists because they naturally support range queries and rank lookups.
• The tradeoff is that skip lists lack worst-case guarantees — they rely on randomness, unlike deterministic balanced BSTs.
• For most practical applications, the expected O(log n) performance of skip lists is indistinguishable from the worst-case O(log n) of balanced trees.