A skip list starts as an ordinary sorted linked list, which only manages O(n) search, and stacks randomized express lanes on top of it. The bottom layer holds every node. Each layer above holds roughly half the nodes of the layer below, acting as a shortcut that skips over the nodes in between. Search starts at the top layer and drops down a level whenever the next node would overshoot the target, landing on O(log n) expected time without a single rotation.
What changed in 2026
- Skip lists remain a standard choice inside high-throughput in-memory systems, prized for being simpler to implement correctly under concurrent access than a balanced tree.
- They stay a fixture of "explain a probabilistic data structure" interview questions, precisely because the randomization insight differs from anything a rotation-based tree teaches.
- Lock-free and wait-free skip list variants continue to see use in high-concurrency caches and in-memory stores, since inserting a node only touches a small, local set of pointers.
The core idea: express lanes over a linked list
Picture a sorted linked list, then add a second layer above it containing roughly every other node, acting as a shortcut that skips two nodes at a time. Add a third layer with roughly a quarter of the nodes, skipping four at a time, and so on. Which nodes get promoted to each layer is decided randomly, classically by flipping a coin per node per layer: heads promotes it one layer higher and flips again; tails stops. That randomization is the entire balancing mechanism, achieving search speed comparable to a red-black tree without needing rotations or recoloring.
How search and insert work
def search(head, target, top_level):
node = head
for level in range(top_level, -1, -1):
while node.forward[level] and node.forward[level].key < target:
node = node.forward[level]
node = node.forward[0]
return node if node and node.key == target else None
Level assignment for a new node uses the same coin-flip idea:
import random
def random_level(p=0.5, max_level=16):
level = 0
while random.random() < p and level < max_level:
level += 1
return level
Insert walks down to find the right position at each level (same as search), then splices the new node into every layer up to its randomly chosen level.
Skip list vs balanced binary trees
| Property |
Skip list |
Red-black / AVL tree |
| Balancing mechanism |
Randomization (coin flips) |
Deterministic rotations and recoloring |
| Search, insert, delete |
O(log n) expected |
O(log n) worst case, guaranteed |
| Implementation complexity |
Simpler, no rotation logic |
More complex, several rotation cases |
| Concurrency friendliness |
Easier to make lock-free |
Harder, rotations touch multiple nodes |
| Worst case |
O(n), extremely unlikely with good randomness |
O(log n), guaranteed regardless |
Where skip lists show up in real systems
Redis uses a skip list internally for its sorted set type, paired with a hash table for constant-time membership checks, because the skip list makes ordered range queries (like fetching the top ten scores) a simple walk along the bottom layer. Some storage engines built around log-structured merge trees use skip lists for their in-memory write buffer, where lock-friendly concurrent inserts matter more than a hard worst-case guarantee.
Common pitfalls
Setting a fixed maximum level too low for the data size. Search degrades toward O(n) if the number of layers cannot grow with the amount of data stored.
Using a biased or low-quality random source for level promotion. The O(log n) expected performance depends on genuinely random coin flips; a biased generator quietly breaks the guarantee.
Assuming skip lists guarantee worst-case O(log n) the way a red-black tree does. They only guarantee it in expectation — astronomically likely, but not absolute.
Reinventing one when a standard library sorted container is already fast enough. Skip lists earn their complexity in concurrent or range-query-heavy scenarios, not as a default replacement for a simple ordered map.
FAQ
Is a skip list actually a list or a tree?
Structurally it is layers of linked lists, not a tree — but it behaves like a balanced search structure because of how the layers are built.
Is skip list performance actually guaranteed?
Only in expectation. With good randomization, worst-case-like behavior is astronomically unlikely, but it is not a hard guarantee the way the O(log n) bound of a red-black tree is.
Why would Redis use a skip list instead of a balanced tree?
Skip lists are simpler to implement correctly, easier to reason about under concurrent access, and support range queries naturally by walking the bottom layer.
Do skip lists need to be rebalanced?
No — there is no rebalancing step at all. The probabilistic construction keeps the expected shape balanced without any rotations.
Where to go next