Skip Lists

A plain sorted linked list is easy to update but slow to search — finding a value means walking node by node from the front, an average of half the list every time. A skip list fixes this by building extra layers of links above the base list, where each higher layer skips over more nodes, like an express subway line that only stops at every fourth station instead of every station.

Concretely, when a node is inserted, a coin is flipped (conceptually) to decide how many layers it participates in: most nodes only sit in the base layer, roughly half also get promoted one layer up, a quarter two layers up, and so on. A search starts at the top, sparsest layer and moves right until it would overshoot, then drops down a layer and repeats, narrowing in on the target with far fewer hops than walking the base list directly. This randomized layering gives search, insert, and delete all roughly logarithmic time on average, without the rebalancing logic a balanced tree needs.

In practice, skip lists are a common choice for the internal structure of a price level in a limit order book, since they support fast ordered insertion and deletion of orders at each price with less bookkeeping overhead than a red-black tree.