SpecializedSpecialized Structures

Skip List

A sorted linked list with randomised express lanes stacked on top, giving expected O(log n) search, insert, and delete without any rebalancing.

Learn Skip List →
headheadheadhead33h277h212h119191919h4252525h3313131h344h1NILNILNILNIL
Towers (key·height)
3·h27·h212·h119·h425·h331·h344·h1
1/36A skip list of 7 sorted keys. Level 0 is an ordinary sorted linked list; every level above it is an express lane holding a random subset of the keys, and each key's tower height came from repeated coin flips.
Head sentinelCursorVisited on the search pathKey foundNewly spliced nodeOvershoot — too far right
PseudocodeLearn Skip List →
1search(target):
2  x = head; level = top
3    while x.next[level] exists and x.next[level].key <= target: x = x.next[level]
4    otherwise drop: level -= 1        # overshot, so search a finer lane
5  found if x.key == target
6insert(key):
7  height = 1; while coinFlip() is heads and height < maxLevel: height += 1
8  splice the node into levels 0..height-1 after the recorded predecessors
Variables
keys7
levels4
maxLevel4
Complexity
access O(log n)
search O(log n)
insert O(log n)
delete O(log n)
Speed