A skip list is a probabilistic ordered structure: a base linked list with multiple "express lane" forwarding pointers above it. Each node is randomly promoted to higher levels, giving O(log n) expected search/insert/delete. Used in Redis sorted sets, LevelDB, and Java's ConcurrentSkipListMap.
| Average | Worst | Space | ||||||
|---|---|---|---|---|---|---|---|---|
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | Worst |
Θ(log n) |
Θ(log n) |
Θ(log n) |
Θ(log n) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n log n) |
Insert: flip a coin to choose a level (geometric distribution — half of nodes at level 0, a quarter at level 1, etc.). Search: start at the top level, walk forward until the next key is too large, drop down a level, repeat. Each level halves the work, giving expected O(log n).
import random
MAX_LEVEL = 16
P = 0.5
class _Node:
__slots__ = ("key", "forward")
def __init__(self, key, level):
self.key = key
self.forward = [None] * (level + 1)
class SkipList:
def __init__(self):
self.head = _Node(None, MAX_LEVEL)
self.level = 0
def _random_level(self):
lv = 0
while random.random() < P and lv < MAX_LEVEL:
lv += 1
return lv
def search(self, key): # O(log n) expected
x = self.head
for i in range(self.level, -1, -1):
while x.forward[i] and x.forward[i].key < key:
x = x.forward[i]
x = x.forward[0]
return x is not None and x.key == key
def insert(self, key): # O(log n) expected
update = [self.head] * (MAX_LEVEL + 1)
x = self.head
for i in range(self.level, -1, -1):
while x.forward[i] and x.forward[i].key < key:
x = x.forward[i]
update[i] = x
lv = self._random_level()
if lv > self.level:
self.level = lv
n = _Node(key, lv)
for i in range(lv + 1):
n.forward[i] = update[i].forward[i]
update[i].forward[i] = n
sl = SkipList()
for k in [3, 6, 1, 8, 2, 9, 4]:
sl.insert(k)
print(sl.search(8)) # True
print(sl.search(7)) # FalseConcurrentSkipListMap.Level 0 is an ordinary sorted linked list containing every key. Each higher level is a sparser sorted list containing a random subset of the level below; on average half of the nodes appear on level 1, a quarter on level 2, and so on. A search starts at the head on the highest level and moves right while the next key is smaller than the target. When the next key is too large or the list ends, it drops one level and continues. Because each level skips about twice as far as the one below, the expected number of moves per level is constant, and there are about log2(n) levels, giving O(log n) expected search.
The analysis is easiest backwards: retracing the search path from the found node to the head, each step either goes up a level (if the node was promoted, probability 1/2) or left. The expected number of left moves before going up is therefore at most 2 per level, so the expected path length is at most about 2 log2(n). The worst case is O(n), when every node happens to land on level 0, but the probability of a significantly longer-than-expected search shrinks exponentially with n.
Insertion reuses the search: during the descent the algorithm remembers, for every level, the last node it visited before dropping (the update array). It then draws a random level using repeated coin flips, creates a node with that many forward pointers and splices it after update[i] on each level. No rotations or rebalancing are needed; balance is maintained in expectation by randomness alone. Deletion is symmetrical: find the predecessors, unlink the node on every level where it appears, and lower the list's level if the top levels become empty.
def delete(self, key):
update = [self.head] * (MAX_LEVEL + 1)
x = self.head
for i in range(self.level, -1, -1):
while x.forward[i] and x.forward[i].key < key:
x = x.forward[i]
update[i] = x
x = x.forward[0]
if x is None or x.key != key:
return False
for i in range(len(x.forward)):
if update[i].forward[i] is x:
update[i].forward[i] = x.forward[i]
while self.level > 0 and self.head.forward[self.level] is None:
self.level -= 1
return True
def range_query(self, lo, hi):
"""All keys in [lo, hi]: O(log n + k)."""
x = self.head
for i in range(self.level, -1, -1):
while x.forward[i] and x.forward[i].key < lo:
x = x.forward[i]
x = x.forward[0]
while x and x.key <= hi:
yield x.key
x = x.forward[0]
SkipList.delete = delete
SkipList.range_query = range_query
print(list(sl.range_query(2, 6))) # [2, 3, 4, 6]
print(sl.delete(4), sl.search(4)) # True FalseRange queries are where skip lists shine compared with hash tables: after an O(log n) descent to the first key in range, the bottom level is a sorted linked list that can be walked in order. This is exactly how Redis serves ZRANGEBYSCORE on sorted sets.
| Structure | Ordered | Search | Concurrency | Implementation |
|---|---|---|---|---|
| Skip list | yes | O(log n) expected | lock-free variants are practical | short |
| Red-black / AVL tree | yes | O(log n) worst | rotations touch several nodes | longer |
| Hash table | no | O(1) average | striped locks | short |
| B-tree | yes | O(log n) | latch coupling | long, disk-oriented |
Choose a skip list for in-memory ordered maps where simplicity or concurrent access matters more than guaranteed worst-case bounds. Insertions only modify the predecessors on each level, which keeps contention local; this is why Java chose a skip list for ConcurrentSkipListMap and why LevelDB and RocksDB use one for their in-memory write buffer (memtable).
MAX_LEVEL should be about log2 of the maximum expected size; 16 levels suit up to roughly 65,000 elements at P = 0.5, 32 covers billions.