Skip List: search, insert with coin flips, delete

The idea: a sorted list with express lanes

A skip list keeps its keys in a sorted linked list, and then adds more linked lists on top of it. Each node is a tower of 1 to MAX_LEVEL forward pointers. Level 0 links every node. Level 1 links only the towers that are at least 2 tall, level 2 only the towers at least 3 tall, and so on. The higher levels are express lanes: they let a search jump over many keys at once, then slow down near the target.

The page uses MAX_LEVEL = 4 (levels L0 to L3), a coin with p = 1/2, and keys from 1 to 99. The list level is the height of the tallest tower; searches start there. Every lane ends at NIL.

Search: right or down

Start at the head on the top used level. Look at the next node on this level. If its key is smaller than the key you want, move right to it. If it is larger, or it is NIL, drop one level and look again. When you drop off level 0, the next node on level 0 either holds the key or the key is not in the list (Demo: search 44, level by level; Demo: search a missing key (30)).

The canvas colours the node you stand on orange, the path behind you blue, and outlines the next node being compared. The line under the list counts the key comparisons.

Insert: update[ ], coin flips, splice

1. Search for the key, and on each level remember the last node before it. That array is update[ ]: update[i] is the node whose level-i pointer will point to the new node.
2. Flip a coin to pick the height: start at 1, and add a level for every heads, until the first tails or MAX_LEVEL. Half the towers stay at height 1, a quarter reach 2, an eighth reach 3.
3. If the new height is above the list level, the extra levels start at the head: update[i] = head, and the list level grows (Demo: insert 60 with height 4).
4. Splice one level at a time: new.next[i] = update[i].next[i], then update[i].next[i] = new.

To make the demos repeatable, the coin is a seeded random generator: the same seed always gives the same flips. The height menu can also force the outcome, for example "force 3 (H H T)" (Demo: insert 22, coin H H T; Demo: insert 40, first flip tails; Demo: six inserts with seeded coin flips).

Delete

Search with update[ ] again. If the next node on level 0 holds the key, then on every level the tower reaches, set update[i].next[i] = x.next[i], and free the node. If the top lane is now empty, lower the list level (Demo: delete 25, the tallest tower: lane L2 empties and the list level drops from 3 to 2).

Why searches are O(log n) on average

With p = 1/2, about n/2 towers reach level 1, n/4 reach level 2, and so on, so there are about log₂ n levels. Walking the search path backwards, each step goes up with probability p and left otherwise, so on each level you expect about 1/p = 2 moves. That gives about 2 log₂ n comparisons, O(log n), and n / (1 − p) = 2n pointers in total.

This is an average over the coin flips, not a guarantee. If every flip comes up tails, the skip list is a plain linked list and a search walks every key (Demo: unlucky vs lucky coins, search 70: 11 comparisons with all towers at height 1, 5 with ideal heights). With real random flips such bad luck is very unlikely for large n, and the key order does not matter: sorted input is as good as random input.

Skip list vs balanced tree

	Skip list	Balanced BST (AVL, red-black)
Search, insert, delete	O(log n) expected	O(log n) worst case
Keeping balance	random heights, no rebalancing	rotations and recolouring
Changes per insert	one pointer per level of the new tower	can rotate and recolour up the path
Range scan	walk level 0 in order	in-order traversal (or a threaded tree)
Concurrency	local changes, lock-free versions are simple	a rotation touches several nodes
Memory	about 2 pointers per key (p = 1/2), 1.33 (p = 1/4)	2 child pointers + colour or height

Where skip lists are used

• Redis sorted sets (ZADD, ZRANGE, ZRANK): p = 1/4, ZSKIPLIST_MAXLEVEL = 32, and each pointer stores a span so ranks can be counted. See how a Redis sorted set is stored.
• LevelDB and RocksDB memtables: new writes go into a skip list (kBranching = 4, kMaxHeight = 12) before they are flushed to an SSTable; see LSM tree vs B-tree.
• Java ConcurrentSkipListMap and ConcurrentSkipListSet: a sorted map that many threads can update without a global lock.

See also binary search trees, red-black trees and linked lists for the structures a skip list builds on.

The same layered idea, applied to a graph of vectors, is HNSW vector search.

For O(log n) prefix sums over an array that keeps changing, see the Fenwick tree.

Another O(log n) structure, built for range sums and range updates, is the segment tree.

A treap is the tree-shaped cousin: randomness (a priority per node) instead of coin-flip heights, also O(log n) expected.

What the page leaves out

The page keeps keys only (no values or scores), at most 14 of them, and only 4 levels so the towers fit on screen; real lists use 12 to 32 levels. It leaves out backward pointers (Redis keeps one on level 0 for reverse scans), the spans that give rank queries, early exit when an upper level already hits the key, duplicate keys, finger search, deterministic skip lists (1-2-3 skip lists), and the compare-and-swap tricks of lock-free skip lists.

References

William Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees" (CACM, 1990)

Redis source: t_zset.c (zslInsert, zslDelete, zslRandomLevel)

LevelDB source: db/skiplist.h

Java ConcurrentSkipListMap