A skip list is a probabilistic data structure that allows O(log n) search, insertion, and deletion on an ordered sequence, similar to a balanced BST but dramatically simpler to implement correctly in a concurrent environment. Skip lists are used in Redis (sorted sets), LevelDB (memtable), and lucene (in-memory index segments). Understanding skip lists is valuable for system design interviews covering in-memory ordered indexes and their concurrent variants.
Structure: Layered Linked Lists
A skip list is a hierarchy of linked lists. The bottom layer (level 0) is a standard sorted linked list containing all elements. Each higher layer is a subset of the layer below, with nodes promoted randomly. Level 1 contains ~half the nodes of level 0; level 2 contains ~half of level 1; and so on. The maximum height is O(log n). To search: start at the topmost layer, traverse right until the next node exceeds the target, drop down one level, repeat until level 0. Expected O(log n) nodes visited.
const maxLevel = 32
const probability = 0.5
type SkipNode struct {
key float64
value interface{}
forward []*SkipNode // next pointers for each level
}
func (sl *SkipList) Search(key float64) interface{} {
curr := sl.header
for i := sl.level - 1; i >= 0; i-- {
for curr.forward[i] != nil && curr.forward[i].key < key {
curr = curr.forward[i] // move right at level i
}
// key not found at this level, drop down
}
curr = curr.forward[0]
if curr != nil && curr.key == key {
return curr.value
}
return nil
}
func randomLevel() int {
level := 1
for rand.Float64() < probability && level < maxLevel {
level++
}
return level
}Insertion and the Update Array
Insertion uses an update array to track the rightmost node at each level that is less than the insertion key. After the search phase (same traversal as lookup), update[i] holds the predecessor at level i. Generate a random level for the new node. For each level up to the new node level, splice the new node in after update[i]. The update array makes insertion O(log n) with simple pointer manipulation — no rotations or rebalancing needed, unlike AVL trees or red-black trees.
Redis Sorted Sets: Skip List + Hash Map
Redis sorted sets (ZADD/ZRANK/ZRANGE) use a skip list for score-ordered traversal combined with a hash map for O(1) score lookup by member. The skip list stores (score, member) pairs ordered by score. ZRANGE with index range is O(log n + k) where k is result count. ZRANGEBYSCORE is O(log n + k). The hash map supports ZSCORE in O(1). This dual structure enables both score-based range queries and member-to-score lookups efficiently. The skip list outperforms balanced BSTs in this scenario because it requires no global rebalancing and supports forward iteration trivially.
Concurrent Skip Lists
Skip lists have a significant advantage over trees in concurrent environments: fine-grained locking is straightforward. Each node can be individually locked. The lock-free ConcurrentSkipListMap in Java uses CAS (compare-and-swap) operations for wait-free reads and lock-free insertions. The key insight: a failed CAS on a node pointer means another thread modified it — retry from the nearest safe point. Trees require global restructuring (rotations) that is hard to make lock-free, while skip lists only modify a constant number of pointers per insert.
Key Interview Discussion Points
- Expected vs. worst case: O(log n) expected, O(n) worst case (all nodes promoted to max level) — acceptable for probabilistic structures
- Space: O(n) expected with probability p=0.5, since each node appears in 1/(1-p) = 2 levels on average
- Cache performance: skip lists have poor cache locality vs. B-trees (scattered memory allocations vs. contiguous pages)
- LevelDB memtable: uses a skip list as the in-memory write buffer before flushing to SSTables, chosen for simplicity and lock-free reads
- Deterministic skip lists: use a balanced distribution scheme instead of randomization for predictable O(log n) worst case