Skip Lists

Linked lists are simple and beautiful. Insert a node? O(1). Delete a node? O(1). Traverse? O(n). Search? Also O(n). And that's the problem, searching a linked list means walking every single node from the beginning until you find what you're looking for.

Balanced binary trees (AVL trees, red-black trees) solve the search problem. O(log n) lookups. But they're complex to implement. Rotations, rebalancing, color-flipping, the code is notoriously error-prone and hard to debug.

In 1990, William Pugh published a paper with a deceptively simple idea: what if you gave a linked list express lanes? Instead of walking every node, what if some nodes had pointers that let you skip ahead, like an express subway line that stops at every 4th station?

That's a skip list. It gives you O(log n) search, insertion, and deletion, the same as a balanced BST, but with an implementation so simple you can code it from memory in an interview.

Redis uses skip lists as the backbone of its sorted sets (ZSET). When you run ZRANGEBYSCORE in Redis, you're walking a skip list. LevelDB and MemSQL use them too. They're one of those data structures that look like a toy but power serious production systems.

A skip list is a multi-level sorted linked list where each level acts as an "express lane" for the level below.

• Level 0 (bottom): Contains all elements, sorted. This is a regular linked list.
• Level 1: Contains roughly 1/2 of elements. Each node at this level also exists at level 0.
• Level 2: Contains roughly 1/4 of elements.
• Level k: Contains roughly 1/2^k of elements.

Searching for a value:

1. Start at the highest level, at the head node
2. Move right along the current level until the next node is greater than your target (or null)
3. Drop down one level
4. Repeat until you find the target at level 0 or determine it doesn't exist

Inserting a value:

1. Search for the insertion position (same algorithm as above)
2. Insert the new node at level 0
3. Flip a coin: heads = promote to the next level. Keep flipping until tails.
4. The coin flip is what makes it probabilistic, on average, 50% of nodes reach level 1, 25% reach level 2, and so on.

This randomized promotion is the genius of skip lists. You don't need complex rebalancing algorithms, probability handles the balance for you. On average, the structure stays balanced, giving O(log n) operations.

The worst case is theoretically possible (every coin flip is heads, creating a tall tower), but astronomically unlikely with a fair random number generator.