No. 03Data structures
Skip list
Express lanes, funded by coin flips.
Published
A sorted linked list knows where everything belongs. Finding something can still mean visiting a tedious number of neighbours.
Try it: find 7, walking versus skipping
Find 7. Compare walking with skipping.
Level 3
- start
- 7
Level 2
- start
- 3
- 7
Level 1
- start
- 1
- 3
- 5
- 7
- 9
Search for 7Found
- Skip-list comparisons
- 6
- Plain walk comparisons
- 5
- Level 3: 7 is not < target, drop down
- Level 2: 3 < target, move to 3
- Level 2: 7 is not < target, drop down
- Level 1: 5 < target, move to 5
- Level 1: 7 is not < target, drop down
- Bottom: check 7, found
This tiny layout lost to the plain walk. The logarithmic claim is about expected cost on many keys.
Level 3
- start
- 7
Level 2
- start
- 3
- 7
Level 1
- start
- 1
- 3
- 5
- 7
- 9
Search for 6Not present
- Skip-list comparisons
- 6
- Plain walk comparisons
- 5
- Level 3: 7 is not < target, drop down
- Level 2: 3 < target, move to 3
- Level 2: 7 is not < target, drop down
- Level 1: 5 < target, move to 5
- Level 1: 7 is not < target, drop down
- Bottom: check 7, not the target
This tiny layout lost to the plain walk. The logarithmic claim is about expected cost on many keys.
Five keys with fixed towers. Counts describe this layout only.
Why?
Random promotion means about half the nodes reach each next level up, so on many keys a search touches roughly log n levels with a few steps each. On five keys the overhead of the top levels can cost more than it saves.
A skip list adds higher links that jump over some of those neighbours. To search, move forward while the next key is still before your target. If the next jump would go too far, drop to a lower level and continue. Eventually, check the candidate on the bottom list.
Try finding 7, then change the tower layout and try again. Count the actual comparisons, including the jumps you considered but couldn't take.
Random promotion gives some nodes taller towers without constantly rebalancing a tree. Under the usual randomisation, search has expected logarithmic cost. That word “expected” is doing honest work: a tiny or unlucky layout can lose to a plain walk. The express lane occasionally has traffic too.