Skip list visualizer

Type the keys to insert, in order, and press "Build list". A key on its own gets a random height from coin flips with probability p; write 30:3 to give 30 height 3, as many exercises specify, and x30 to delete 30. Then search, insert or delete single keys: the drawing marks the nodes the search moved through and where it dropped down, and the side panel lists every comparison.

• "Flip the coins again" rebuilds the same keys with new random heights, so you can see how much the shape varies.
• "Copy link" saves the keys, heights and coin flips in the address.

A skip list keeps keys in a sorted linked list, the bottom level, and adds higher levels that each contain a random subset of the level below. Every node is on level 1; with probability p it is also on level 2, with probability p² on level 3, and so on. The higher levels act as express lanes: a search runs along the top, where nodes are far apart, and drops a level whenever it would overshoot.

Because heights are chosen at random when a node is inserted and never changed, a skip list needs none of the rotations or recolouring of balanced trees. The price is that its O(log n) cost holds only on average, over the coin flips, not in every case.

1. Search starts at the head on the highest level, moves right while the next key is smaller than the target, and drops down a level when the next key is larger or missing. On level 1, the next node is either the target or proof that it is absent.
2. Insert runs the same search, remembering the last node visited on every level, draws the new node's height, and links it in after those nodes on each of its levels.
3. Delete runs the search and unlinks the node on every level it occupies; if the top levels become empty, the list's height shrinks.

William Pugh's analysis bounds the expected cost of a search in a list of n keys by L/p + 1/(1 − p) steps, where L = log_1/p n. Average comparisons per successful search in this page's model, over random lists, against that bound:

• Redis sorted sets. Large sorted sets are a skip list plus a hash table; the source sets p = 1/4 and at most 32 levels, and each link stores how many nodes it spans so that rank queries are fast.
• LevelDB and RocksDB memtables. LevelDB's in-memory table is a skip list with a branching factor of 4 and at most 12 levels. Writers need a lock, but reads proceed without any locking.
• Java's ConcurrentSkipListMap provides a sorted concurrent map with expected logarithmic cost, which is simpler to build without locks than a balanced tree.

Both give logarithmic search, insertion and deletion, and both keep keys in order for range scans. A balanced tree such as a red-black tree guarantees its bound in the worst case and tends to use memory more compactly. A skip list is shorter to write, needs no rebalancing, and an insertion only touches the pointers next to the new node, which makes concurrent versions much easier. The bottom level is a plain linked list, so iterating in order is trivial.

William Pugh of the University of Maryland introduced skip lists in "Skip Lists: A Probabilistic Alternative to Balanced Trees" in Communications of the ACM in 1990, arguing that they match balanced trees in expected performance while being simpler to implement. They became a standard part of data structure courses and, later, of databases and key-value stores that need ordered, concurrent in-memory indexes.