A skip list is a sorted linked list with express lanes above it. Each element picks its top lane when it is inserted, by flipping a coin until it comes up tails, and nothing is ever rebalanced. On the lab's opening tape, 10 of 16 keys reach at least the first express lane, the tallest reaches the fifth, and a search costs 77/16 hops on average with a worst case of 8 — against a reference curve of 2 log₂ n = 8.000, which is not a count.
Core ideas
The hard idea is that the structure is never repaired. The other two are how a level is chosen and what the printed reference curve is for.
Level 0 is the sorted list of every key. A key appears at level k + 1 with probability a half, independently, so level k holds about n/2ᵏ⁺¹ keys and the levels form a geometric cascade. A search starts at the top left, moves right while the next key does not overshoot the target, and drops a level when it does. Each drop roughly halves the interval that remains to be searched.
When a key is inserted it flips a coin until it comes up tails; the number of heads is its top level. That decision involves no other key, no global counter and no rebalancing, and it is never changed. The lab shows this directly: change n and the existing keys' levels do not move, because each one was decided from that key's own place on the tape.
The expected search cost is O(log n), and the panel draws 2 log₂ n as a dashed curve beside the hops it counted. That curve is sampled at double precision, no verdict is read off it, and at sixteen keys on this tape it reads 8.000 where the counted mean is 77/16 = 4.813. The counted number is the one this page computed.
The material
The levels, the search, the counted hops, and the reference curve that is labelled rather than quoted.
A skip list on a sorted set of keys is a sequence of linked lists L₀ ⊇ L₁ ⊇ L₂ ⊇ …. L₀ contains every key. Each key in Lₖ appears in Lₖ₊₁ with probability 1/2, independently of every other key. A key's level is the highest list it appears in.
Equivalently, and this is how the lab builds it: each key reads the coin tape at its own position and takes the length of the run of heads there as its level. The tape is the reader's, chosen by a seed, so the structure is reproducible without being fixed — and the coins come from the prime-modulus stream, because the low bit of a power-of-two-modulus generator is not a coin and a structure built from one would have levels that repeat on a short cycle.
To find a target, start at the leftmost node of the highest level. Repeatedly: if the next node at this level exists and its key is not greater than the target, move to it; otherwise drop one level. Stop at level 0. Each move and each drop is a hop, and the hops are what the lab counts.
Keys 10 to 160. The tape gives levels 1, 1, 2, 0, 0, 4, 0, 1, 0, 0, 1, 4, 1, 0, 1, 1, so 10 of the 16 keys reach at least level 1 and two reach level 4. Searching for key 120, which is at level 4, takes 2 hops; searching for key 100, which is at level 0 and is the second of two consecutive level-0 keys, takes 8. The mean over all sixteen searches is 77/16 = 4.813 and the worst is 8.
Those two searches are the lesson in miniature. Key 120 is one of the two tallest nodes, so the top-level walk reaches it in two hops. Key 100 has level 0 and must be reached by descending all the way and walking, so it costs 8. Same structure, same tape, a factor of four between two lookups — and the mean of the sixteen is a fraction, because a mean of integers is.
The right-hand column is what the geometric cascade predicts and the middle column is what this tape produced. They are in the same neighbourhood and they are not equal: 10 keys present at level 1 against a predicted 8, and 2 at level 4 against a predicted 0.5. Level 3 is the row worth staring at — no key has 3 as its top level, and two keys are nevertheless present there, because a key at level 4 appears at every level below it.
That distinction between “top level is k” and “present at level k” is the commonest confusion in reading a skip list, and it is why the panel prints both columns. The first is a partition of the keys and adds to n; the second is a nested family and decreases as k grows.
The expected number of levels is O(log n) and the expected search cost is O(log n) as well: at each level the walk passes a constant number of nodes in expectation before dropping, because the probability that the next node is present one level up is a half. This course does not prove a concentration result around that expectation — the tail bound needed is a Chernoff bound and this course excludes it — so what is available is an expectation and the counts on screen.
So the panel draws 2 log₂ n as a dashed reference and labels it. At sixteen keys it reads 8.000 and the counted mean is 4.813; at eight keys it reads 6.000 and a different tape counted 3.250. The curve is not a bound, not an asymptote that has been proved here, and not a prediction; it is a familiar shape to read the counted points against, and the panel says so in those terms.
The search cost is also a random variable in the same way a treap's depth is, and for the same reason: the coins belong to the structure. A worst case of 8 hops on sixteen keys is this tape's worst case, and another tape gives another. Nothing here bounds it, and the honest statement is the one the panel makes — the mean is 77/16, the worst observed is 8, and both are counts on the structure drawn above them.
An AVL tree guarantees a height, always, and pays with a stored height per node, a case analysis over four rotation shapes, and a rebalancing pass on every insertion and deletion. A skip list guarantees an expectation, and pays with nothing at all: an insertion writes a few pointers at the levels the coin chose, and no other node is touched. There is no global structure to maintain, which is the whole point of the design.
That absence is also what makes a skip list easy to get right and easy to make concurrent, and it is what makes its worst case unbounded. Which of those matters more is a question about the system rather than about the structure — the same question Universal Hashing asked about whether anyone can choose your keys.
Interactive
Each key picks its own level from a coin, and nothing is ever rebuilt
Method
Count the hops. Then ask what the count is a count of.
A key's level is the run of heads at its position. That is the only input to the shape, and it means the structure can be rebuilt from the seed alone — which is what makes every number on the page reproducible.
The first partitions the keys and adds to n; the second is nested and decreases. The panel prints both, and the level-3 row of the opening tape has 0 in the first column and 2 in the second.
A tall key is found from the top in a couple of hops; a level-0 key behind a tall one costs the descent and the walk. On the opening tape those are 2 hops and 8, and the spread is what the mean is a mean of.
2 log₂ n reads 8.000 at sixteen keys where the counted mean is 4.813. It is there to show the counted points growing like a logarithm. Nothing on the page is decided by it and the panel says so.
Keys 10 through 160, levels from the tape, and the cost of finding each one. The mean of the last column is the panel's headline figure.
Key 60 costs one hop and key 100 costs eight, and both are in the same structure. The mean 77/16 is an exact fraction because it is the average of sixteen integers, and it is not the cost of any search: no lookup costs 4.8125 hops. That is the same distinction as everywhere else on this course, arriving here as an average over queries rather than over seeds.
The counted mean sits well below the dashed 8.000. Do not read that as the structure beating its bound — 2 log₂ n is not a bound, and at n = 8 on another tape the counted mean was 3.250 against a reference of 6.000. The curve is a shape, the points are counts, and the panel keeps them in different colours for that reason.
For a faded rehearsal, move the tape seed and predict what happens to the level column before the page redraws. The supplied first move is this: each key's level is read from its own position on the tape, so a new tape gives new levels for every key at once. Say whether the number promoted above level 0 should stay near half of 16, then check several seeds — and then say why changing n instead leaves the existing keys' levels alone.
You should be able to read each key's level off the tape, describe the search as move-right-or-drop, count its hops, distinguish top level from presence at a level, and say what the dashed curve is and is not.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.