Skip lists
A lot of people love New York—and so do we. It has many qualities that are hard to describe; it is a crazy (in a good way), lively city that brings together many cultures, backgrounds, ethnicities, activities, and opportunities. New York also features a large public transport network, almost like cities in Europe.
What does any of this have to do with skip lists? A subway system can be expressed as a simple list of stops (expressed in street numbers, a common thing in the USA): 14 -> 23 -> 28 -> 33 -> 42 -> 51 -> 59 -> 68 . However, the New York subway system has something called express trains which reduce the number of stops to cover larger distances faster.
Suppose someone wants to go from stop 14 to stop 51. Instead of seeing ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access