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 the doors open and close five times, they can go there getting off at the third stop. In fact, this is how New Yorkers use the trains 4, 5, and 6 between 14th Street (Union Square) and 51st Street. Turned on its side, the subway plan...