The “Staff Engineer” Linked List

Standard Linked Lists have O(N) search. Binary Search Trees (BST) have O(log N). Can we make a Linked List O(log N)? Yes, if we cheat with probability.

Enter the Skip List.

1. The Concept: Express Lanes

Imagine a highway.

  • Level 0: Local traffic. Stops at every node. 1 → 2 → 3 → 4 ...
  • Level 1: Express. Skips every other node. 1 ----> 3 ----> 5 ...
  • Level 2: Super Express. Skips even more. 1 ----------> 5 ...

To find 5:

  1. Start at top level.
  2. If next > target, go down a level.
  3. If next ≤ target, go forward.

Visualizing the multi-layer highway.

Ready.

3. The Mathematical Anchor: Probabilistic Analysis

Why does a Skip List achieve O(\log N) search when it’s just a bunch of linked lists?

1. Expected Height

For each node, we flip a coin to decide if it moves up a level.

  • Probability of Level 0: 1
  • Probability of Level 1: 1/2
  • Probability of Level h: (1/2)h The expected number of nodes at level h is N/2h. The “exit” level where only 1 node remains is when N/2h = 1, which gives h = \log2 N.

2. Search Cost (Backwards Analysis)

Imagine searching for a node and looking at the path backwards from the target to the top-left:

  • At any node, we either came from the left (same level) or from above (higher level).
  • Since a node is promoted with probability p=0.5, the probability we came from above is 0.5.
  • The expected number of steps at any level is 1/p = 2.
  • Since there are \log N levels, the total expected steps is 2 \cdot \log N.
  • Conclusion: Average time complexity is O(\log N).

4. Why Redis uses Skip Lists

Redis uses Skip Lists for Sorted Sets (zset), not Balanced Binary Trees (like Red-Black Trees). Why?

  1. Simplicity: Implementing a Skip List is simpler than a self-balancing RB-Tree.
  2. Memory: Skip Lists use less pointers on average (1.33 per node vs 2 for Trees).
  3. Concurrency: It’s easier to make a Skip List lock-free (thread-safe updates) because changes are often local. Rebalancing a tree can touch many nodes.
  4. Range Queries: Skip Lists are naturally efficient for range scans (just traverse Level 0).

5. Implementation Details

  • Insertion: Flip a coin. Heads → Promote to next level.
  • Height: Logarithmic with high probability.

[!NOTE] This is a probabilistic structure. Worst case is O(N), but extremely unlikely (like winning the lottery 100 times in a row).