What is a Skip List?
A skip list is a probabilistic data structure that provides O(log n) expected time for search, insert, and delete — the same as a balanced binary search tree — but with a much simpler implementation. It was invented by William Pugh in 1990 as an alternative to AVL trees and red-black trees.
Structure
A skip list is built on multiple levels of sorted linked lists:
- Level 0 (bottom): contains all elements in sorted order. This is a standard sorted linked list.
- Level 1: contains a subset of elements — roughly half.
- Level 2: contains roughly a quarter of elements.
- Level k: contains roughly 1/2^k of elements.
- Top level: contains very few elements — often just the sentinel head.
Each element that appears at level k also appears at all levels below k. The levels form a tower of pointers for that element.
Promotion (coin flip)
When inserting a new element, it is always added to level 0. Then the algorithm "flips a coin" (with probability p, typically 0.5 or 0.25). If heads, promote the element to the next level. Keep flipping until tails (or a maximum level is reached). This randomization gives the skip list its probabilistic balance — no rotations needed.
Search algorithm
- Start at the top-left (highest level, head sentinel).
- Move right along the current level until the next element is greater than the target (or null).
- Drop down one level.
- Repeat until you find the target or reach the bottom level without finding it.
This is like taking an express train (high levels skip many elements), then transferring to local trains (lower levels for fine-grained search).
Complexity
| Operation | Expected | Worst case |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Space | O(n) | O(n log n) |
The worst case (all elements promoted to the top) is astronomically unlikely — similar to quicksort's worst case.
Advantages over balanced trees
- No rotations: AVL and red-black trees require complex rotation logic to maintain balance. Skip lists achieve balance probabilistically.
- Simple concurrent implementation: lock-free skip lists are much easier to implement than lock-free balanced trees. Java's
ConcurrentSkipListMapuses this. - Range queries: the bottom level is a sorted linked list, so range scans are trivial.
Real-world usage
- Redis sorted sets (ZSET): Redis uses skip lists for its sorted set data type, enabling O(log n) rank-based and range operations.
- LevelDB/RocksDB memtable: the in-memory write buffer uses a skip list for fast sorted insertion.
- Java ConcurrentSkipListMap: a thread-safe sorted map built on skip lists.
Real-Life: Redis Sorted Sets
Redis's sorted set (ZSET) maps members to scores and supports operations like:
ZADD leaderboard 1500 "alice"— insert with scoreZRANGEBYSCORE leaderboard 1000 2000— range query by scoreZRANK leaderboard "alice"— rank (position in sorted order)
Internally, Redis uses a skip list for the sorted set. Here is why:
- O(log n) insert/delete: adding or removing a player from the leaderboard is fast.
- O(log n + k) range queries: finding all players with scores between 1000-2000 descends the skip list to the start of the range, then walks the bottom level — k elements for k results.
- O(log n) rank: by augmenting each forward pointer with a "span" (how many elements it skips), Redis can compute rank without traversing the entire list.
Redis chose skip lists over balanced trees because:
- The implementation is simpler and easier to debug.
- They naturally support range operations via the sorted bottom level.
- Concurrent access patterns (Redis is single-threaded, but the simplicity matters for maintenance).
LevelDB memtable: when you write a key-value pair to LevelDB, it goes into an in-memory skip list. When the memtable is full, it is flushed to an SSTable on disk. The skip list enables fast sorted insertion (important for write-heavy workloads) and efficient in-order iteration (needed for the flush).