Skip List

A randomized alternative to balanced trees for ordered data. Every item lives in an ordinary sorted linked list, but coin flips promote some items into higher "express lanes" that let search, insert, and delete skip over long runs of the list in expected O(log n) time, no rotations or rebalancing required.

How it works

The bottom lane (level 0) is a plain sorted linked list containing every key. When a key is inserted, its height (how many lanes it participates in) is chosen by repeated coin flips: start at level 0, and for as long as the flip comes up heads (probability p, usually 0.5), climb one more level. This makes roughly half as many nodes reach each successive level, forming express lanes that shortcut over the bottom list the same way an express train skips local stops.

search() starts at the top-most lane at the head node and moves forward as long as the next node's key is still less than the target. When the next node would overshoot (or there is no next node in that lane), it drops down one level and continues -- repeating until it reaches level 0, where the next node is either the target or proof it doesn't exist.

insert() runs the same downward walk, remembering the last node visited at each level (the "update" list). The new node is spliced in at level 0 and at every level up to its randomly chosen height, re-pointing each remembered predecessor's forward pointer. delete() does the same walk and un-splices the node from every level it appeared in.

Interactive demo

Size0
Lanes in use1
Max level16
p0.5
L0
H
NIL
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new SkipList(maxLevel?, p?)Allocate a sentinel head node with maxLevel lanes; p is the per-level promotion probability.O(maxLevel) space overhead
insert(key): booleanInsert a key at a randomly chosen height, splicing it into every lane up to that height.O(log n) expected
search(key) / contains(key): booleanWalk down from the top lane, following forward pointers that stay below the target.O(log n) expected
delete(key): booleanLocate the key and un-splice it from every lane it appears in.O(log n) expected
toSortedKeys(): number[]Read off all keys in ascending order from the bottom lane.O(n) time

References

Original papers

Library implementations

Real-world use cases