Skip Lists
A skip list stacks progressively sparser linked lists on top of a sorted one. Each level is an express lane over the level below, so a search descends instead of scanning — O(log n) expected, with coin flips replacing all the rebalancing code a tree needs.
Express Lanes Over a Sorted List
A sorted linked list is easy to maintain but slow to search: reaching the kth element means following k pointers, so lookup is O(n) even though the data is ordered. Binary search is impossible because there is no random access to jump to the midpoint.
A skip list fixes this by adding layers. The bottom layer is the ordinary sorted linked list containing every element. Above it sits a sparser list containing roughly half the elements, above that one with a quarter, and so on. Each higher layer acts as an express lane, skipping over elements the layer below must visit one at a time.
The analogy is a metro system: the local line stops everywhere, the express line stops at every fourth station, and travelling far means riding the express as long as possible before dropping to the local for the final approach.
Structurally, a node that appears at level k also appears at every level below it, so a node is really a tower of forward pointers — one per level it reaches. Searching moves horizontally along a level and vertically down between them.
With each layer holding half of the one beneath, there are O(log n) layers, and a search examines a constant number of nodes per layer. That gives O(log n) search over a structure built entirely from linked lists, with no tree and no rotations anywhere.
- The bottom layer is a complete sorted linked list
- Each higher layer holds roughly half the nodes below it
- A node is a tower of forward pointers, one per level it reaches
- O(log n) layers, constant work per layer
Searching, Inserting, and the Coin Flip
Search starts at the head of the topmost level. At each step, look at the next node on the current level. If its key is smaller than the target, move right. If it is larger — or there is no next node — drop down one level and repeat. When you drop below the bottom level, the element either sits at the current position or does not exist.
The rule is worth stating as one sentence: move right while you can, drop down when the next node overshoots. The path traced is a staircase, and it is the same path for search, insertion, and deletion.
Insertion performs that search while recording the last node visited at each level — the update path. The new element is then spliced into the bottom list at the found position. The question is how many levels it should also appear in, and here the structure does something unusual: it flips a coin.
Starting at level 1, flip repeatedly; while the flip comes up heads, promote the node one level higher. With a fair coin, a node reaches level 1 always, level 2 with probability 1/2, level 3 with probability 1/4, and level k with probability 1/2^(k−1). That distribution is exactly what produces the halving structure — on average, without ever measuring or enforcing it.
This is what makes skip lists remarkable. A balanced tree inspects its own shape and performs rotations to correct it; a skip list never looks at its shape at all. The layer distribution emerges from randomness, and no rebalancing code exists.
Deletion runs the same search, then unlinks the node from every level it appears in using the recorded update path. Both insertion and deletion are O(log n) expected, dominated by the search.
A practical detail: the promotion probability need not be 1/2. Using p = 1/4 — as Redis does — produces fewer levels and fewer pointers per node, saving memory at the cost of slightly more horizontal steps per search. A maximum level cap is also imposed so an unlucky run of heads cannot allocate an unbounded tower.
- Move right while the next key is smaller; drop down when it overshoots
- Record the last node visited per level — that is the update path
- Promote a new node with repeated coin flips, halving each time
- No rebalancing exists; the distribution emerges from randomness
Expected, Not Guaranteed
The complexity claim needs stating carefully, because it differs in kind from a balanced tree's.
A skip list is O(log n) expected for search, insertion and deletion. An AVL or red-black tree is O(log n) guaranteed. The skip list's worst case is O(n) — if every coin flip came up tails, every node would sit only at level 1 and the structure would be a plain linked list.
That worst case is not an input the adversary can choose, which is the crucial difference from an unbalanced BST. A binary search tree degenerates on sorted input, which is common and predictable. A skip list degenerates only on an unlucky random number sequence, independent of what data arrives — so no attacker controlling the keys can force it.
The probability of genuinely bad behaviour is negligible. The chance that a skip list of a thousand elements exceeds twice its expected height is vanishingly small, and the bound tightens as n grows. In practice the expected bound is what you get.
Space is O(n) expected. Each node holds on average two forward pointers with p = 1/2 — one at level 1, half a pointer's worth at level 2, and so on, summing to 2. Lowering p to 1/4 reduces this to about 1.33 pointers per node.
Because the bottom layer is a complete sorted list, range queries are natural: find the start in O(log n), then walk the bottom level sequentially. This is the same advantage a B+ tree's linked leaves provide, and it is why skip lists suit ordered-set workloads rather than pure lookup.
| Skip list | AVL / red-black | |
|---|---|---|
| Search, insert, delete | O(log n) expected | O(log n) guaranteed |
| Worst case | O(n), on unlucky randomness | O(log n) |
| Degenerates on sorted input? | No | No (a plain BST does) |
| Implementation | Simple — no rotations | Rotation cases, colour rules |
| Concurrency | Localised pointer updates | Rebalancing locks subtrees |
| Space | ~2 pointers per node | 2 pointers plus metadata |
- Expected O(log n); worst case O(n) but only from bad randomness
- No input, sorted or adversarial, can force the worst case
- Space is about two pointers per node at p = 1/2
- The complete bottom layer makes range queries a sequential walk
Terms, operations, and practical uses
Structure and layers
- Express LanesHigher layers in the skip list that contain fewer nodes, allowing traversal to skip over large sections of the bottom layer.
- Bottom LayerThe foundational layer (Layer 0) which is a standard sorted linked list containing every single inserted element.
- TowerThe vertical column of nodes representing a single element across multiple layers.
Algorithms
- Probabilistic BalancingFlipping a virtual coin to decide if a newly inserted node should be promoted to the next higher layer.
- Drop DownThe action of moving to a lower layer during a search when the next node in the current layer is greater than the target.
- Update ArrayAn array used during insertion to remember the right-most nodes visited at each layer so the new node can be spliced in correctly.
Comparisons and uses
- O(log N) ExpectedSkip lists guarantee O(log N) time mathematically on average, but could theoretically degrade to O(N) if the coin flips are extremely unlucky.
- ConcurrencySkip lists are easier to make thread-safe than balanced trees because updates are highly localized and don't require global rotations.
- Redis Sorted SetsThe most famous real-world implementation of a skip list, used to rank elements quickly by score.
Searching in a Skip List
class SkipNode:
def __init__(self, value, levels):
self.value = value
self.next = [None] * levels
def search_skip_list(head, target):
current = head
for level in range(len(head.next) - 1, -1, -1):
while current.next[level] and current.next[level].value < target:
current = current.next[level]
candidate = current.next[0]
return candidate is not None and candidate.value == target
# three layers; the express lanes skip over 50
head = SkipNode(None, 3)
n50, n70 = SkipNode(50, 3), SkipNode(70, 3)
head.next = [n50, n50, n70]
n50.next = [n70, n70, None]
print('Found', 70 if search_skip_list(head, 70) else 'nothing')#include <iostream>
#include <vector>
using namespace std;
struct SkipNode {
int value;
vector<SkipNode*> next;
SkipNode(int value, int levels) : value(value), next(levels, nullptr) {
}
};
bool searchSkipList(SkipNode* head, int target) {
SkipNode* current = head;
for (int level = static_cast<int>(head->next.size()) - 1; level >= 0; --level) {
while (current->next[level] != nullptr && current->next[level]->value < target) {
current = current->next[level];
}
}
SkipNode* candidate = current->next[0];
return candidate != nullptr && candidate->value == target;
}
int main() {
// three layers; the express lanes skip over 50
SkipNode* head = new SkipNode(0, 3);
SkipNode* n50 = new SkipNode(50, 3);
SkipNode* n70 = new SkipNode(70, 3);
head->next = {n50, n50, n70};
n50->next = {n70, n70, nullptr};
cout << "Found ";
if (searchSkipList(head, 70)) cout << 70 << '\n';
else cout << "nothing\n";
}public class Main {
static class SkipNode {
int value;
SkipNode[] next;
SkipNode(int value, int levels) {
this.value = value;
this.next = new SkipNode[levels];
}
}
static boolean searchSkipList(SkipNode head, int target) {
SkipNode current = head;
for (int level = head.next.length - 1; level >= 0; --level) {
while (current.next[level] != null && current.next[level].value < target) {
current = current.next[level];
}
}
SkipNode candidate = current.next[0];
return candidate != null && candidate.value == target;
}
public static void main(String[] args) {
// three layers; the express lanes skip over 50
SkipNode head = new SkipNode(0, 3);
SkipNode n50 = new SkipNode(50, 3);
SkipNode n70 = new SkipNode(70, 3);
head.next = new SkipNode[]{n50, n50, n70};
n50.next = new SkipNode[]{n70, n70, null};
System.out.println("Found " + (searchSkipList(head, 70) ? "70" : "nothing"));
}
}Step through it
Running on Find 70 in a 3-layer skip list
Read all 11 Steps
- A sorted linked list searches in O(n) Values 10, 30, 50, 70, 90 in a plain linked list must be walked one node at a time. Sorted order does not help, because a list has no way to jump to the middle.
- Add express lanes above A skip list stacks sparser copies of the list on top. Each level is a shortcut over the level below, so a search can travel far in one hop and only descends when it overshoots.
- Search 70: start top-left Begin at the head on the highest level, L2. Starting high is what makes the search logarithmic — the top lane crosses the most ground per step.
- L2: next is 70, not past the target On L2 the next node is 70, and 70 is not greater than the target 70, so move right. That single hop skipped over 30 and 50 entirely.
- L2: next is null, drop to L1 Nothing follows 70 on L2, so the lane is exhausted. Descend to L1 at the same node rather than moving right — dropping never loses progress already made.
- L1: next is 90, too far — drop to L0 90 > 70, so moving right would overshoot. Descend again to L0, the level that contains every node.
- L0: current value is 70 At the bottom level the node under the cursor is the target itself. The search touched three nodes instead of the four a linear walk would have needed, and the gap widens fast as the list grows.
- A miss stops at the predecessor Searching for 60 follows the same descent and lands on 50 with 70 next. Since 70 ≠ 60, the value is absent — and 50 is exactly the node a new 60 would be inserted after, so search and insert share one traversal.
- Levels are chosen by coin flip On insert a node takes level 1, then flips a coin: heads promotes it a level, tails stops. Half the nodes reach L1, a quarter reach L2, and so on, giving the halving structure without any rebalancing code.
- O(log n) expected, not guaranteed Because heights are random, an unlucky run can leave every node at level 1 and degrade the search to O(n). The bound is probabilistic — but the odds fall off exponentially, so it holds in practice.
- Why use one over a balanced tree A skip list matches a red-black tree's O(log n) search, insert, and delete while being far simpler to implement — no rotations, no colour rules. Its per-node forward arrays also make concurrent, lock-free updates easier, which is why Redis and LevelDB use them for ordered data.
Why Anyone Chooses One
Given that balanced trees offer a stronger guarantee, the case for skip lists rests on two practical advantages.
Implementation simplicity. A red-black tree's insertion and deletion involve numerous cases, colour invariants and rotations, and deletion in particular is something few people write correctly from memory. A skip list is linked-list splicing plus a random level — perhaps fifty lines, with no case analysis. When a structure has to be written, reviewed and maintained by hand, that difference is worth a great deal.
Concurrency, which is the stronger argument. A balanced tree's rebalancing rotates nodes that may be far from the insertion point, so a concurrent implementation must lock a subtree or an entire path, and lock-free versions are notoriously difficult. A skip list modifies only the forward pointers along the update path, which are localised and independent per level — so fine-grained locking works naturally, and lock-free implementations using compare-and-swap are tractable.
This is why Java's ConcurrentSkipListMap exists and is the standard concurrent ordered map: there is no comparably practical concurrent red-black tree in the standard library.
Redis uses skip lists for its sorted sets, paired with a hash table — the hash gives O(1) member lookup, the skip list maintains score order for range queries and rank operations. It uses p = 1/4 and a level cap of 32. LevelDB and RocksDB use one for the in-memory memtable, where concurrent writes and ordered iteration are both required. Apache Lucene uses skip pointers over posting lists on the same principle.
The case against is straightforward: a skip list uses more memory than a compact B-tree, has worse cache locality than an array-backed structure, and offers only a probabilistic bound. For single-threaded ordered maps a red-black tree is generally the better choice, which is why std::map and TreeMap use one.
The summary worth remembering: choose a skip list when concurrency or implementation simplicity matters more than a worst-case guarantee.
- Roughly fifty lines against a red-black tree's case analysis
- Updates are localised, so fine-grained and lock-free versions are practical
ConcurrentSkipListMap, Redis sorted sets, LevelDB memtables- Single-threaded ordered maps still favour a balanced tree