A skip list adds layers of forward links to a sorted list. Follow a search for key 9 and see why random promotion gives expected logarithmic updates.
Skip list
A skip list is a sorted linked list with extra layers of forward links that let a search skip over intervening keys. The base level contains every key, and each higher level contains a subset of the level below. A replay tool could use a skip list to maintain the ask-side price levels of an order book as they appear and disappear, then scan them from a given price upward.
Follow a link or drop a level
Take five toy keys, 2, 4, 7, 9 and 12. All five appear on the base level, and only 7 and 12 appear above it. The head is a sentinel that gives the search a starting point at either level.
Start at the upper head. The next key is 7, which is below 9, so follow the link. This skips the base keys 2 and 4.
From 7, the next upper key is 12. That overshoots 9, so drop to the base level at 7.
The next base key is 9. Inspect it and confirm the match.
Toy skip list. The base level holds 2, 4, 7, 9 and 12. The upper level holds 7 and 12. To find 9, follow the upper link from Head to 7, reject the link to 12, drop at 7 and follow the base link to 9.
The dashed link exists in the list. The search leaves it unused because 12 is above the target.
At each level, move right while the next key is strictly below the target. When you reach the base level and can go no further by that rule, the next node is the first key at or above the target, if such a node exists. Check equality for an exact lookup, or walk forward from that node for a range scan. To insert or delete a key, record the predecessor at each level during the search, then reconnect the links on the levels the node occupies. Pugh, A Skip List Cookbook, §2.1
Where the expected speed comes from
The diagram fixes the levels to make the path easy to trace. In the standard randomised skip list, each new key gets a height at insertion. It starts at the base and keeps moving up with a fixed probability p at each step, independently across steps and keys, until a promotion fails or an optional height cap is reached. Each level has an expected fraction p of the keys on the preceding level, up to that cap.
With n keys and an uncapped height or a cap sized for the intended list capacity, search, insertion and deletion take expected O(logn) time and the structure uses expected O(n) space. A range scan returning k keys adds O(k) work once the start is found. The expectation is over the heights assigned at insertion. Searches of the same key in an unchanged list follow the same path. A draw with every key confined to the base can still require a full linear scan. Pugh, Skip Lists, analysis and space requirements
In the replay example, a second order at an existing ask price changes the quantity stored at that key. A new price calls for an insertion, and a price that loses its last order calls for a deletion. The skip list keeps prices ordered for the scan. If the replay tracks order priority within a price, that belongs in the data stored at the price level.
The SelfMadeQuant lesson on Arrays, Linked Lists, Stacks, and Queues illustrates how a base list follows and reconnects node links. A preview is public and the full lesson requires membership.
