Introduction

Yes, skip lists really can achieve the expected O(log n) search, insertion, and deletion behavior that Pugh described. The catch is that "performing as good as the paper claims" depends on whether you mean asymptotic complexity, constant factors on real hardware, or behavior under concurrency.

Why Skip Lists Work at All

A skip list is a layered linked structure. Every key appears in the bottom level, and a random subset of keys is promoted to higher levels that act as shortcuts.

Search works by:

1. moving right while the next key is still below the target,
2. dropping down one level when moving right would overshoot,
3. repeating until the bottom level is reached.

That produces expected logarithmic behavior because each level eliminates large parts of the search space.

Here is a minimal search sketch in Python:

1class Node:
2    def __init__(self, key, level):
3        self.key = key
4        self.forward = [None] * (level + 1)
5
6
7def search(head, key, max_level):
8    current = head
9
10    for level in range(max_level, -1, -1):
11        while current.forward[level] and current.forward[level].key < key:
12            current = current.forward[level]
13
14    current = current.forward[0]
15    return current is not None and current.key == key

The elegance of the algorithm is one of the structure's biggest strengths.

What Pugh Actually Claimed

The classic claim was not that skip lists beat every balanced tree in every benchmark. The real claim was that skip lists deliver balanced-tree-like expected complexity with much simpler balancing logic.

That claim has aged well.

Compared with red-black trees or AVL trees, skip lists avoid:

• rotations,
• several structural corner cases,
• and much of the bookkeeping complexity required for deterministic balancing.

So from an algorithm-design perspective, skip lists absolutely deliver on the paper's main promise.

Where Real Machines Change the Story

Big-O notation hides constant factors, and skip lists have some practical costs:

• pointer chasing,
• weaker cache locality,
• more memory overhead from multiple forward pointers,
• and branch-heavy traversal.

Those costs matter on modern CPUs. A structure that is theoretically elegant can still lose to a cache-friendly alternative in a benchmark dominated by memory latency.

For example, a sorted array with binary search may beat a skip list for read-heavy workloads when updates are rare and the dataset fits cache well. Likewise, B-tree-like structures often outperform pointer-rich structures when locality matters more than implementation simplicity.

Where Skip Lists Often Shine

Skip lists remain very attractive in concurrent systems. Their local pointer updates and simple invariants make them easier to adapt to fine-grained locking and lock-free techniques than rotation-based balanced trees.

That is one reason skip-list-like structures show up in in-memory databases, key-value stores, and concurrent maps. The attraction is not only the expected O(log n) bound. It is also the engineering convenience of maintaining that bound under concurrency.

Insertion Shows the Simplicity

Insertion is a good example of why skip lists are so appealing:

1import random
2
3
4def random_level(max_level, p=0.5):
5    level = 0
6    while level < max_level and random.random() < p:
7        level += 1
8    return level
9
10
11def insert(head, key, max_level):
12    update = [None] * (max_level + 1)
13    current = head
14
15    for level in range(max_level, -1, -1):
16        while current.forward[level] and current.forward[level].key < key:
17            current = current.forward[level]
18        update[level] = current
19
20    level = random_level(max_level)
21    node = Node(key, level)
22
23    for i in range(level + 1):
24        node.forward[i] = update[i].forward[i]
25        update[i].forward[i] = node

There is no rotation logic here. Random promotion does the balancing work probabilistically.

Expected Performance Versus Worst-Case Guarantees

This is one of the most important distinctions in the whole discussion. Skip lists are classically analyzed with expected bounds, not hard deterministic worst-case guarantees for every possible promotion outcome.

In practice, with a sound random-level generator, pathological layouts are rare enough that skip lists work extremely well. But if your application needs strict worst-case guarantees and the environment is hostile to pointer-heavy structures, a deterministic balanced tree or a cache-oriented structure may still be the better choice.

Benchmarking Them Fairly

A fair benchmark should compare more than asymptotic complexity. It should include:

• realistic key distributions,
• read/write ratios,
• memory allocation costs,
• cache effects,
• and concurrency patterns if the structure is shared.

A skip list may lose in a tiny single-threaded benchmark and still be the right choice in a highly concurrent service where implementation simplicity and lock behavior matter more than absolute single-thread lookup speed.

Common Pitfalls

The biggest pitfall is comparing skip lists and trees only through big-O notation. Real performance depends heavily on memory layout and constant factors.

Another mistake is using a poor random-level policy. If promotion is badly skewed, the height distribution degrades and performance follows.

Developers also sometimes ignore workload shape. For small collections or read-mostly tables, a simpler structure may outperform a skip list outright.

Finally, do not forget why skip lists became popular in the first place. Their value is not just average-case complexity. It is the combination of good expected performance and simple, concurrency-friendly structure.

Summary

• Pugh's expected O(log n) claim for skip lists is still sound.
• Skip lists trade deterministic balancing for probabilistic balancing and simpler code.
• Real speed depends on memory locality, pointer overhead, and workload shape.
• They are especially attractive in concurrent and lock-free designs.
• The paper's claims hold algorithmically, but practical winners still depend on context and constants.