Skip List
A skip list is a probabilistic data structure that layers multiple linked lists on top of each other. The bottom level contains all elements in sorted order; each higher level acts as an express lane, skipping over elements to enable fast traversal. When you insert a value, a series of coin flips decides how many levels it occupies. The result: expected O(log n) search, insertion, and deletion — competitive with balanced trees, but far simpler to implement.
Expected height = O(log n) · Search time = O(log n) · Promotion probability p = 0.5
The skip list idea
Invented by William Pugh in 1990, the skip list is a beautifully simple alternative to balanced binary search trees. The key insight is that maintaining perfect balance is expensive — but probabilistic balance is cheap and works almost as well. A skip list is built from multiple levels of sorted linked lists. Every element appears in the bottom level. Each element is independently “promoted” to the next higher level with probability p (typically 1/2). Higher levels act as express lanes, letting searches skip over large sections of the list.
Search algorithm
To search for a value, start at the top-left (the head of the highest level). Move right along the current level until the next node’s value would overshoot the target, then drop down one level and continue. This zig-zag path from top-left to the target is the search path. On average, each level cuts the remaining distance roughly in half, yielding O(log n) expected time — the same as a balanced BST. The path is highlighted in gold in the visualization above.
Insertion and the coin flip
To insert a value, first search for its position (establishing update pointers at each level). Then flip a coin repeatedly: each “heads” promotes the element one more level. On average, an element reaches height 1/(1−p) levels. With p = 0.5, the expected height is 2 levels. The maximum level of any element in a list of n items is O(log n) with high probability. This randomized process is what gives skip lists their elegant simplicity — no rotations, no rebalancing, just coin flips.
Comparison with linked lists and trees
A plain sorted linked list requires O(n) time to search, insert, or delete. A balanced BST (AVL, red-black) achieves O(log n) worst-case but requires complex rebalancing logic. The skip list achieves O(log n) expected time with a trivially simple algorithm. The trade-off is that the worst case is O(n) — though this happens with astronomically low probability. Skip lists are used in practice in systems like Redis, LevelDB, and Apache Lucene.