Skip List

A sorted, multi-level linked list — search rides express lanes and transfers down; insert flips coins to pick a level.

Search O(log n) expected Insert / Delete O(log n) expected Space O(n) Worst case O(n)

value

Slow Fast

current node scanning right found / new node not found update[] predecessor

Insert a value to watch the coin flips pick its level.

Press Insert, Search, or Delete. Search moves right while the next node < target, then drops down a level.

Elements: 0 Levels: 1 Steps: 0 log₂ n: 0

Operation	Expected	Worst Case	Note
Search	O(log n)	O(n)	worst case astronomically improbable
Insert	O(log n)	O(n)	descent + O(level) splice
Delete	O(log n)	O(n)	descent + unlink per level
Min	O(1)	O(1)	head.forward[0]
Range [lo,hi]	O(log n + k)	O(n)	descend, then walk base list
Space	O(n)	O(n log n)	~2n pointers at p=0.5