Part 4 · 1 chapters · ~8 min

Skip Lists

Probabilistic balance with coin flips, search, insert and delete in expected O(log n), why skip lists are simpler to make concurrent than balanced trees, and their use in Redis sorted sets, LSM memtables and Java's concurrent collections.

5

Express lanes by coin flip

code
function randomLevel(max = 16) { let l = 1; while (l < max && Math.random() < 0.5) l++; return l; }
// insert: find the predecessor at each level, then splice the new node into levels 1..randomLevel()
// expected space: n + n/2 + n/4 + … ≈ 2n pointers; expected search: O(log n)
A SKIP LIST
a sorted linked list with express lanes chosen by coin flips
level 3head → 30 → NILlevel 2head → 10 → 30 → 50level 1head → 10 → 20 → 30 → 40 → 50 → 60
swipe the figure sideways, or tap expand for full screen
1/4
the base
Level 1 is an ordinary sorted linked list: finding an element is O(n).
a sorted linked listO(n) alone