Skip Lists - Learning Module

Loading content...

0/276

Comparison with Balanced Trees

Choosing the Right Tool

Skip lists and balanced binary search trees (BSTs) solve the same fundamental problem: maintaining a sorted collection with O(log n) search, insertion, and deletion. Given that both achieve the same asymptotic complexity, how do you choose between them?

This page provides a comprehensive comparison across multiple dimensions: implementation complexity, actual runtime performance, memory usage, cache behavior, concurrency support, and suitability for different use cases. By the end, you'll have a clear framework for making this architectural decision.

The goal isn't to declare a winner—both structures excel in different contexts. Rather, we want to understand the tradeoffs deeply enough to make informed choices for specific problems.

What You Will Learn

By the end of this page, you will understand the practical differences between skip lists and balanced trees across implementation complexity, performance, memory, cache efficiency, and concurrency. You'll learn which scenarios favor each structure and see examples from production systems that have made this choice.

Implementation Complexity

One of skip lists' most compelling advantages is their dramatically simpler implementation. Let's compare the conceptual and code complexity of each approach.

Skip List Implementation Requirements:

Node structure: Key, value, array of forward pointers
Random level generation: Simple coin-flip loop
Search: Walk right, then down—straightforward loop
Insert: Search + link new node at its level
Delete: Search + unlink node from each level

No rotations. No rebalancing. No color maintenance. No height checks.

Red-Black Tree Implementation Requirements:

Node structure: Key, value, left, right, parent, color
Search: Standard BST traversal
Insert: BST insert + fixup with:
- 3 cases for uncle's color
- Left/right rotations
- Color flipping
- Propagation up the tree
Delete: Most complex—6 cases involving:
- Transplant operations
- Successor finding
- Double-black resolution
- Multiple rotation types

Lines of Code Comparison (Typical Implementation)
Component	Skip List	Red-Black Tree	AVL Tree
Node class	~15 lines	~20 lines	~18 lines
Search	~15 lines	~15 lines	~15 lines
Insert	~25 lines	~80 lines	~60 lines
Delete	~20 lines	~120 lines	~80 lines
Helper rotations	0 lines	~40 lines	~40 lines
Fixup/rebalance	0 lines	~60 lines	~40 lines
Total (approx)	~75 lines	~335 lines	~253 lines

complexity_comparison.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
"""
Side-by-side comparison of insert operations.
 
This demonstrates the dramatic difference in implementation
complexity between skip lists and balanced trees.
"""
 
# ============================================================
# SKIP LIST INSERT - Simple and Direct
# ============================================================
 
def skip_list_insert(self, key, value):
    """
    Skip list insertion: Find position, create node, link it.
    No rotations, no rebalancing, no fixups.
    """
    # Step 1: Find predecessors at each level
    update = [self.header] * self.max_level
    current = self.header
    
    for level in range(self.current_level, 0, -1):
        while current.forward[level-1] and current.forward[level-1].key < key:
            current = current.forward[level-1]
        update[level-1] = current
    
    # Step 2: Check for existing key
    candidate = current.forward[0]
    if candidate and candidate.key == key:
        candidate.value = value
        return
    
    # Step 3: Generate random level
    new_level = self._random_level()
    if new_level > self.current_level:
        for level in range(self.current_level + 1, new_level + 1):
            update[level-1] = self.header
        self.current_level = new_level
    
    # Step 4: Create and link new node
    new_node = Node(key, value, new_level)
    for level in range(1, new_level + 1):
        new_node.forward[level-1] = update[level-1].forward[level-1]
        update[level-1].forward[level-1] = new_node
    
    self.size += 1
    # DONE! No fixup needed.
 
 
# ============================================================
# RED-BLACK TREE INSERT - Complex with Multiple Cases
# ============================================================
 
def red_black_insert(self, key, value):
    """
    Red-Black insertion: BST insert + complex fixup.
    Must handle rotations, color changes, and case analysis.
    """
    # Step 1: Standard BST insert
    new_node = RBNode(key, value, color=RED)
    parent = None
    current = self.root
    
    while current != self.nil:
        parent = current
        if key < current.key:
            current = current.left
        elif key > current.key:
            current = current.right
        else:
            current.value = value
            return
    
    new_node.parent = parent
    if parent is None:
        self.root = new_node
    elif key < parent.key:
        parent.left = new_node
    else:
        parent.right = new_node
    
    new_node.left = self.nil
    new_node.right = self.nil
    
    # Step 2: Fix Red-Black properties (THIS IS THE COMPLEX PART)
    self._insert_fixup(new_node)
 
 
def _insert_fixup(self, node):
    """
    Fix Red-Black properties after insertion.
    Three cases to handle, potentially propagating up the tree.
    """
    while node.parent and node.parent.color == RED:
        if node.parent == node.parent.parent.left:
            uncle = node.parent.parent.right
            
            # Case 1: Uncle is red - recolor and move up
            if uncle.color == RED:
                node.parent.color = BLACK
                uncle.color = BLACK
                node.parent.parent.color = RED
                node = node.parent.parent
            else:
                # Case 2: Uncle is black, node is right child
                if node == node.parent.right:
                    node = node.parent
                    self._left_rotate(node)
                
                # Case 3: Uncle is black, node is left child
                node.parent.color = BLACK
                node.parent.parent.color = RED
                self._right_rotate(node.parent.parent)
        else:
            # Symmetric cases for right subtree
            uncle = node.parent.parent.left
            
            if uncle.color == RED:
                node.parent.color = BLACK
                uncle.color = BLACK
                node.parent.parent.color = RED
                node = node.parent.parent
            else:
                if node == node.parent.left:
                    node = node.parent
                    self._right_rotate(node)
                node.parent.color = BLACK
                node.parent.parent.color = RED
                self._left_rotate(node.parent.parent)
    
    self.root.color = BLACK
 
 
def _left_rotate(self, x):
    """Left rotation - also needed for Red-Black maintenance."""
    y = x.right
    x.right = y.left
    if y.left != self.nil:
        y.left.parent = x
    y.parent = x.parent
    if x.parent is None:
        self.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y
 
 
def _right_rotate(self, y):
    """Right rotation - symmetric to left rotation."""
    x = y.left
    y.left = x.right
    if x.right != self.nil:
        x.right.parent = y
    x.parent = y.parent
    if y.parent is None:
        self.root = x
    elif y == y.parent.right:
        y.parent.right = x
    else:
        y.parent.left = x
    x.right = y
    y.parent = x

Bug Surface Area

More code means more bugs. Red-Black tree implementations are notoriously tricky—even textbook implementations often contain subtle errors. The rotation and fixup logic involves many pointer manipulations that must all be exactly right. Skip lists have far fewer opportunities for error.

Runtime Performance Analysis

Both structures have O(log n) complexity, but constant factors matter in practice. Let's analyze the actual performance characteristics.

Constant Factors in Skip Lists:

Comparisons per level: ~1/p on average (2 for p = 0.5)
Pointer traversals: One per move (right or down)
Memory indirection: Each level requires following a pointer
Random number generation: One call per level during insertion

Constant Factors in Balanced Trees:

Comparisons per level: Exactly 1
Pointer traversals: One per tree level (left or right)
Memory indirection: Each level follows a pointer
Rebalancing overhead: Rotations require 5-10 pointer updates

performance_benchmark.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
"""
Performance Comparison: Skip List vs Red-Black Tree
 
This benchmark compares actual runtime for common operations.
Results will vary by implementation and hardware.
"""
import time
import random
from typing import List, Tuple, Dict
 
 
def benchmark_operations(
    structure,
    name: str,
    n: int,
    operations: int = 10000
) -> Dict[str, float]:
    """
    Benchmark insert, search, and delete operations.
    
    Args:
        structure: Data structure instance with insert/search/delete
        name: Name for reporting
        n: Number of elements to pre-populate
        operations: Number of operations to benchmark
    
    Returns:
        Dictionary of timing results
    """
    results = {}
    
    # Pre-populate with n elements
    elements = list(range(n))
    random.shuffle(elements)
    
    start = time.perf_counter()
    for x in elements:
        structure.insert(x, f"value_{x}")
    results["initial_insert_time"] = time.perf_counter() - start
    results["initial_insert_per_op"] = results["initial_insert_time"] / n
    
    # Benchmark random searches
    search_keys = [random.randint(0, n-1) for _ in range(operations)]
    
    start = time.perf_counter()
    for key in search_keys:
        structure.search(key)
    results["search_time"] = time.perf_counter() - start
    results["search_per_op"] = results["search_time"] / operations
    
    # Benchmark random insertions (new elements)
    new_elements = list(range(n, n + operations))
    random.shuffle(new_elements)
    
    start = time.perf_counter()
    for x in new_elements:
        structure.insert(x, f"value_{x}")
    results["insert_time"] = time.perf_counter() - start
    results["insert_per_op"] = results["insert_time"] / operations
    
    # Benchmark random deletions
    delete_keys = random.sample(range(n + operations), operations)
    
    start = time.perf_counter()
    for key in delete_keys:
        structure.delete(key)
    results["delete_time"] = time.perf_counter() - start
    results["delete_per_op"] = results["delete_time"] / operations
    
    return results
 
 
def format_benchmark_results(
    skip_list_results: Dict[str, float],
    rbtree_results: Dict[str, float]
) -> str:
    """Format benchmark results for comparison."""
    lines = []
    lines.append("Performance Comparison")
    lines.append("=" * 70)
    lines.append(f"{'Operation':<25} {'Skip List':>15} {'Red-Black':>15} {'Ratio':>10}")
    lines.append("-" * 70)
    
    for op in ["search", "insert", "delete"]:
        sl_time = skip_list_results[f"{op}_per_op"] * 1_000_000  # Convert to µs
        rb_time = rbtree_results[f"{op}_per_op"] * 1_000_000
        ratio = sl_time / rb_time if rb_time > 0 else float('inf')
        
        lines.append(f"{op.capitalize():<25} {sl_time:>12.2f} µs {rb_time:>12.2f} µs {ratio:>9.2f}x")
    
    return "\n".join(lines)
 
 
# Typical benchmark results (will vary by implementation):
#
# Performance Comparison (n = 100,000)
# ======================================================================
# Operation                       Skip List       Red-Black      Ratio
# ----------------------------------------------------------------------
# Search                           0.45 µs          0.38 µs       1.18x
# Insert                           0.52 µs          0.55 µs       0.95x
# Delete                           0.48 µs          0.62 µs       0.77x
#
# Analysis:
# - Search: Red-Black slightly faster (exactly 1 comparison per level)
# - Insert: Nearly equal (skip list avoids rebalancing overhead)
# - Delete: Skip list faster (no complex transplant/fixup)
#
# Overall: Performance is comparable, with skip lists sometimes faster
# due to simpler operations despite 2 comparisons per level.

Key Performance Insights:

Search Performance: Red-Black trees have a slight edge because they make exactly one comparison per level, while skip lists average 2. However, the difference is often negligible.
Insertion Performance: Despite extra comparisons, skip lists often match or beat balanced trees because they avoid rebalancing. No rotations means fewer pointer updates.
Deletion Performance: Skip lists typically win here. Balanced tree deletion is complex, involving transplants, successor finding, and multiple fixup cases. Skip list deletion is just pointer unlinking.
Variance: Skip list times vary slightly due to randomness; balanced tree times are deterministic. In practice, the variance is small enough to be unnoticeable.

Benchmark Reality Check

Microbenchmarks rarely tell the whole story. In production, factors like cache behavior, memory allocation patterns, and concurrent access often dominate. A structure that's 10% slower in microbenchmarks might be 50% faster in your actual workload due to better cache utilization or lock contention.

Memory Usage Comparison

Memory efficiency can be crucial for large datasets. Let's analyze the memory footprint of each structure.

Skip List Memory:

Per node: Key + value + array of forward pointers
Expected pointers per node: 1/(1-p) = 2 for p = 0.5
Total pointer overhead: ~2n pointers
Variable allocation: Each node has a differently-sized pointer array

Red-Black Tree Memory:

Per node: Key + value + left + right + parent + color
Pointers per node: Exactly 3 (left, right, parent)
Extra per node: 1 bit for color (often 1 byte due to alignment)
Total pointer overhead: 3n pointers + n color bits

AVL Tree Memory:

Per node: Key + value + left + right + height
Pointers per node: 2 (left, right) + optional parent
Extra per node: Height counter (typically 4 bytes)

Memory Usage per Node (64-bit pointers)
Structure	Base Fields	Pointers	Extra	Total (approx)
Skip List (p=0.5)	Key + Value	~2 × 8 = 16 bytes	Level array overhead	Key + Value + ~24 bytes
Skip List (p=0.25)	Key + Value	~1.33 × 8 = 11 bytes	Level array overhead	Key + Value + ~18 bytes
Red-Black Tree	Key + Value	3 × 8 = 24 bytes	1 byte color	Key + Value + ~25 bytes
AVL Tree (no parent)	Key + Value	2 × 8 = 16 bytes	4 bytes height	Key + Value + ~20 bytes
AVL Tree (with parent)	Key + Value	3 × 8 = 24 bytes	4 bytes height	Key + Value + ~28 bytes

memory_analysis.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
"""
Memory Usage Analysis
 
Calculate and compare memory footprint for different structures.
"""
import sys
from typing import List, Optional
 
 
class SkipListNode:
    """Skip list node with variable-length forward array."""
    __slots__ = ('key', 'value', 'forward')
    
    def __init__(self, key, value, level: int):
        self.key = key
        self.value = value
        self.forward: List[Optional['SkipListNode']] = [None] * level
    
    def memory_usage(self) -> int:
        """Estimate memory usage of this node."""
        # Base object overhead
        base = sys.getsizeof(self)
        # Key and value sizes (depends on actual types)
        # Forward array
        array_size = sys.getsizeof(self.forward)
        # Pointer slots (8 bytes each on 64-bit)
        pointers = len(self.forward) * 8
        return base + array_size + pointers
 
 
class RBTreeNode:
    """Red-Black tree node with parent pointer."""
    __slots__ = ('key', 'value', 'left', 'right', 'parent', 'color')
    
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        self.parent = None
        self.color = True  # True = RED
    
    def memory_usage(self) -> int:
        """Estimate memory usage of this node."""
        base = sys.getsizeof(self)
        # 3 pointers + 1 boolean
        overhead = 3 * 8 + 1
        return base + overhead
 
 
def analyze_memory(n: int, p: float = 0.5) -> dict:
    """
    Analyze expected memory usage for n elements.
    
    Returns comparison statistics.
    """
    import random
    
    # Simulate skip list level distribution
    def random_level(max_lv=20):
        level = 1
        while random.random() < p and level < max_lv:
            level += 1
        return level
    
    levels = [random_level() for _ in range(n)]
    avg_level = sum(levels) / n
    total_pointers = sum(levels)
    
    # Skip list memory (simplified model)
    # 8 bytes per pointer, plus per-node overhead
    skip_list_pointer_bytes = total_pointers * 8
    skip_list_overhead_per_node = 40  # Object overhead, array container
    skip_list_total = n * skip_list_overhead_per_node + skip_list_pointer_bytes
    
    # Red-Black tree memory
    # 3 pointers + 1 color byte + object overhead
    rb_pointer_bytes = n * 3 * 8
    rb_overhead_per_node = 40 + 1  # Object overhead + color
    rb_total = n * rb_overhead_per_node + rb_pointer_bytes
    
    return {
        "n": n,
        "p": p,
        "avg_skip_list_level": round(avg_level, 2),
        "theoretical_avg_level": round(1 / (1 - p), 2),
        "skip_list_total_pointers": total_pointers,
        "skip_list_bytes": skip_list_total,
        "skip_list_bytes_per_node": round(skip_list_total / n, 1),
        "rb_tree_bytes": rb_total,
        "rb_tree_bytes_per_node": round(rb_total / n, 1),
        "ratio": round(skip_list_total / rb_total, 3),
    }
 
 
def demonstrate_memory():
    print("Memory Usage Comparison")
    print("=" * 70)
    
    print(f"\n{'n':>10} | {'p':>5} | {'SL bytes/node':>15} | {'RB bytes/node':>15} | {'Ratio':>8}")
    print("-" * 70)
    
    for n in [1000, 10000, 100000]:
        for p in [0.25, 0.5]:
            result = analyze_memory(n, p)
            print(f"{n:>10} | {p:>5} | {result['skip_list_bytes_per_node']:>15.1f} | "
                  f"{result['rb_tree_bytes_per_node']:>15.1f} | {result['ratio']:>8.3f}")
    
    print("\nNotes:")
    print("- Skip list with p=0.25 uses less memory (fewer pointers)")
    print("- Skip list with p=0.5 is comparable to Red-Black tree")
    print("- Trade-off: lower p = less memory but slower operations")
 
# Output:
# Memory Usage Comparison
# ======================================================================
#
#          n |     p |    SL bytes/node |    RB bytes/node |    Ratio
# ----------------------------------------------------------------------
#       1000 |  0.25 |            50.6 |            65.0 |    0.778
#       1000 |   0.5 |            56.1 |            65.0 |    0.863
#      10000 |  0.25 |            50.7 |            65.0 |    0.780
#      10000 |   0.5 |            55.9 |            65.0 |    0.860
#     100000 |  0.25 |            50.7 |            65.0 |    0.780
#     100000 |   0.5 |            56.0 |            65.0 |    0.862

Memory Tuning with p

Skip lists offer a unique memory/speed tradeoff via the probability parameter p. Lower p means fewer levels (less memory) but more horizontal traversal (slower search). This tunability is not available with balanced trees, which always have the same structure regardless of workload.

Cache Behavior and Locality

Modern CPUs rely heavily on caches. A data structure with poor cache behavior will be slow regardless of its asymptotic complexity. Let's compare cache characteristics.

Skip List Cache Behavior:

Node layout: Forward pointers are contiguous within a node (good)
Traversal pattern: Follow pointers across nodes (potentially scattered)
Sequential access: Following forward[0] pointers is sequential-ish (depends on allocation)
Level locality: Lower levels have more nodes closer together

Binary Tree Cache Behavior:

Node layout: Fixed structure, good for prefetching
Traversal pattern: Follow child pointers (potentially scattered)
Subtree locality: Nodes in same subtree may be allocated together
Van Emde Boas layout: Special layouts can dramatically improve cache behavior

Cache Miss Analysis:

For both structures, each level traversed typically involves a cache miss (following a pointer to a new node). The number of cache misses is proportional to:

Skip List: O(log n) levels × ~2 nodes per level = O(log n) misses
Balanced Tree: O(log n) height = O(log n) misses

Neither has a significant advantage for pointer-chasing operations.

Where Cache Matters:

Range scans: Skip lists can scan the bottom level sequentially. Trees require in-order traversal, which has worse locality.
Bulk operations: Trees with special layouts (cache-oblivious, van Emde Boas) can be optimized. Skip lists are harder to optimize this way.
Iterator access: Skip list iterators just follow level-0 pointers. Tree iterators need stack space or parent pointers.

Cache Behavior Comparison
Aspect	Skip List	Balanced Tree	Winner
Point lookup cache misses	~2×log n	~log n	Tree (slight)
Range scan locality	Good (level 0 chain)	Poor (tree traversal)	Skip List
Iterator memory	O(1)	O(log n) or parent pointers	Skip List
Prefetching potential	Moderate	High (with special layouts)	Tree
Allocation locality	Variable (random levels)	Fixed (uniform nodes)	Tie

Range Queries Favor Skip Lists

If your workload involves many range queries or sequential scans, skip lists have an advantage. Once you've found the starting point, scanning forward is simply following level-0 pointers—equivalent to traversing a sorted linked list. Trees require more complex traversal logic.

Concurrent Access

In multi-threaded environments, data structure choice can dramatically impact performance. Skip lists have a significant advantage here.

Why Skip Lists Excel at Concurrency:

Local operations: Insert and delete only modify pointers at a single position (plus the node's own pointers). There's no rebalancing that touches distant ancestors.
Independent levels: Operations at different levels are largely independent. A thread modifying level 3 doesn't interfere with one at level 1.
Lock-free implementations: The ConcurrentSkipListMap in Java and similar structures provide lock-free operations using CAS (Compare-And-Swap). This is well-understood and battle-tested.
Fine-grained locking: If locks are needed, each level can have its own lock, reducing contention.

Why Balanced Trees Struggle with Concurrency:

Rebalancing cascades: A single insertion might trigger rotations that propagate to the root. Locking the entire path is often necessary.
Global restructuring: Tree shape changes can affect distant nodes. Readers might observe inconsistent states.
Lock-free difficulty: Lock-free balanced trees are an active research area. No widely-deployed production implementations exist.
Read-write asymmetry: Readers and writers need different lock granularity, leading to complexity.

concurrent_skip_list.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
"""
Conceptual Lock-Free Skip List Insert
 
This shows the basic idea of how skip lists support lock-free
concurrent operations using CAS (Compare-And-Swap).
 
Note: This is simplified pseudocode. Real implementations need
more careful handling of edge cases and memory management.
"""
import threading
from typing import Optional, TypeVar, Generic
 
K = TypeVar('K')
V = TypeVar('V')
 
 
class AtomicReference(Generic[K]):
    """
    Placeholder for atomic reference operations.
    Real implementations use atomic CAS instructions.
    """
    def __init__(self, value: K):
        self._value = value
        self._lock = threading.Lock()
    
    def get(self) -> K:
        return self._value
    
    def compare_and_set(self, expected: K, new_value: K) -> bool:
        """
        Atomically: if current == expected, set to new_value, return True.
        Otherwise return False.
        """
        with self._lock:
            if self._value is expected:
                self._value = new_value
                return True
            return False
 
 
class ConcurrentSkipListNode:
    """
    Node for concurrent skip list.
    Each forward pointer is an atomic reference.
    """
    def __init__(self, key, value, level: int):
        self.key = key
        self.value = value
        # Atomic references for lock-free operations
        self.forward = [AtomicReference(None) for _ in range(level)]
    
    @property
    def level(self):
        return len(self.forward)
 
 
def concurrent_insert(skip_list, key, value, level: int) -> bool:
    """
    Lock-free insert using CAS operations.
    
    The key insight: we link the new node into the list bottom-up,
    ensuring each level is valid before moving to the next.
    
    If a CAS fails (another thread modified the pointer), we retry.
    """
    new_node = ConcurrentSkipListNode(key, value, level)
    
    # Retry loop for each level
    for lv in range(level):
        while True:
            # Find predecessor at this level
            pred = find_predecessor(skip_list, key, lv)
            succ = pred.forward[lv].get()
            
            # Set new node's forward pointer
            new_node.forward[lv] = AtomicReference(succ)
            
            # Try to link into list
            if pred.forward[lv].compare_and_set(succ, new_node):
                # Success at this level, move to next
                break
            # CAS failed, another thread interfered
            # Loop will retry with updated predecessor
    
    return True
 
 
# Contrast with balanced tree, which would need:
# 1. Lock acquisition on potentially distant nodes
# 2. Tree restructuring while holding locks
# 3. Careful unlock ordering to avoid deadlock
# 4. Handling readers who might see inconsistent states
 
 
"""
Production Examples:
 
1. Java ConcurrentSkipListMap:
   - Lock-free concurrent sorted map
   - Used extensively in high-concurrency systems
   - Part of java.util.concurrent since Java 6
 
2. Redis Sorted Sets (ZSET):
   - Uses skip list internally
   - Handles millions of operations per second
   - Single-threaded, but skip list simplicity helps
 
3. RocksDB/LevelDB MemTable:
   - Skip list for in-memory sorted storage
   - Supports concurrent readers with single writer
 
4. Apache Cassandra:
   - Uses skip lists in MemTable
   - Handles high write throughput
"""

Concurrency: Skip Lists Win Decisively

For concurrent workloads, skip lists are the clear choice. Lock-free ConcurrentSkipListMap implementations are production-proven and performant. Lock-free balanced trees remain largely theoretical or research prototypes. If your system needs thread-safe sorted collections, skip lists are the practical answer.

Use Case Recommendations

Based on our comprehensive comparison, here are concrete recommendations for when to use each structure.

Choose Skip Lists When

•You need concurrent access. Lock-free skip lists are battle-tested in Java, Redis, and major databases.
•Implementation simplicity matters. For custom implementations or educational purposes, skip lists are dramatically easier.
•You do many range queries. Level-0 traversal is efficient for sequential access.
•You want tunable memory/speed tradeoff. The probability parameter p gives control.
•Deletion is frequent. Skip list deletion is simpler and often faster.
•You're building custom data structures. Skip lists compose well with other techniques.

Choose Balanced Trees When

•Hard real-time constraints exist. Worst-case O(log n) might be required.
•You're using standard libraries. Most languages have optimized balanced tree implementations (e.g., std::map, TreeMap).
•Cache optimization is critical. Special tree layouts can improve cache performance.
•Space is extremely tight. With p=0.5, skip lists use similar memory, but trees can be slightly more efficient.
•Existing codebase uses trees. Consistency with existing code may outweigh switching benefits.
•You need persistent/immutable versions. Functional programming trees are well-developed.

Production System Choices
System	Structure Used	Reason
Redis Sorted Sets	Skip List	Simplicity, range queries, single-threaded performance
LevelDB/RocksDB MemTable	Skip List	Concurrent reads, sequential scan efficiency
Java ConcurrentSkipListMap	Skip List	Lock-free concurrent sorted map
Linux kernel (rbtree)	Red-Black Tree	Deterministic performance, kernel predictability
C++ std::map/std::set	Red-Black Tree	Standard library, worst-case guarantees
Java TreeMap	Red-Black Tree	Standard library, deterministic
PostgreSQL B-tree indexes	B-tree (variant)	Disk-optimized, high fan-out

The Default Choice

If you're writing a new system and don't have specific constraints pushing you toward balanced trees, skip lists are often the better choice. They're simpler, have great performance, and exceed balanced trees for concurrent access. Reserve balanced trees for cases with hard real-time requirements or when leveraging existing library implementations.

Summary: Making the Choice

We've compared skip lists and balanced trees across every relevant dimension. Here's the consolidated decision framework:

Key Comparison Points

•Asymptotic Complexity: Both achieve O(log n) for all operations. Skip lists provide expected bounds; balanced trees provide worst-case bounds.
•Implementation Complexity: Skip lists are dramatically simpler—~75 lines vs ~300+ lines. Fewer opportunities for bugs.
•Runtime Performance: Comparable in most cases. Skip lists may win on deletion; trees may win on search (1 vs 2 comparisons per level).
•Memory Usage: Similar with p=0.5. Skip lists offer tunability via p parameter.
•Cache Behavior: Trees may prefetch better; skip lists excel at range scans.
•Concurrency: Skip lists win decisively. Lock-free implementations are mature and widely deployed. Lock-free balanced trees are largely theoretical.

The Bottom Line:

Skip lists represent a genuine alternative to balanced trees, not just an academic curiosity. For most modern applications—especially those requiring concurrency, range queries, or simple implementations—skip lists are an excellent choice.

Balanced trees remain valuable for hard real-time systems, leveraging existing library implementations, and cache-critical single-threaded workloads.

Both are powerful tools in a software engineer's toolkit. Understanding their tradeoffs enables you to make informed architectural decisions.

Module Complete

Congratulations! You've completed the Skip Lists module. You now understand the probabilistic foundations of skip lists, their multi-level architecture, rigorous O(log n) complexity analysis, and how they compare with balanced trees. Skip lists exemplify how elegant randomized algorithms can match—and in some cases exceed—the performance of complex deterministic alternatives.