Skip Lists
A Skip List is a probabilistic data structure that allows $O(\log n)$ search complexity within an ordered sequence of elements. It is essentially a linked list with multiple layers of "express lanes" that allow you to skip over large sections of the list.
1. The Problem with Linked Lists
Standard Sorted Linked Lists are slow for searching. Even if the list is sorted, you have to traverse it node by node from the head.
- Search Complexity: $O(n)$.
- Binary Search? Impossible, because you can't jump to the middle index directly.
2. The Solution: Layers
A Skip List adds multiple layers of links.
- Level 0: Contains all elements (standard linked list).
- Level 1: Skips every few elements.
- Level 2: Skips even more elements.
- ...
- Top Level: Very few elements.
3. How it Works
Search
Start at the top layer.
- Move right until the next node is greater than the target.
- Move down one layer.
- Repeat until you find the target or hit the bottom layer.
This mimics the behavior of a Binary Search tree but using a linked list structure.
Insertion (Probabilistic)
When inserting a new element:
- Insert it into the bottom layer (Level 0) to maintain order.
- Flip a coin (randomly decide).
- Heads: Promote the element to the next layer up.
- Tails: Stop promoting.
- Repeat until you stop promoting.
This randomness ensures the list stays balanced on average, without complex rebalancing logic like AVL or Red-Black trees.
4. Complexity
| Operation | Average | Worst Case |
|---|---|---|
| Search | $O(\log n)$ | $O(n)$ |
| Insert | $O(\log n)$ | $O(n)$ |
| Delete | $O(\log n)$ | $O(n)$ |
- Space Complexity: $O(n)$ (on average, we have $n$ nodes at level 0, $n/2$ at level 1, $n/4$ at level 2... summing to $2n$).
5. Use Cases
- Redis Sorted Sets (ZSET): Redis uses Skip Lists to implement sorted sets because they are easier to implement than balanced trees and support range queries efficiently.
- LevelDB / RocksDB: Used in the MemTable (in-memory write buffer).