A sorted list is easy to search if it is an array: jump to the middle, then the middle of the half, and so on. But insert into an array and you must shift everything. A linked list inserts easily, yet finding anything means walking from the start. Computer scientists solved this with balanced trees such as AVL trees, which stay shallow by rotating nodes after every change. They work well, and they are fiddly to write correctly.
In 1990 William Pugh proposed something much simpler. Take a sorted linked list and add express lanes above it. Decide which items get express stops by flipping a coin. The result is a skip list. It searches in about log n steps on average, with code short enough to write in an afternoon.
A skip list keeps items in sorted order with several layers of links. Each item climbs to higher layers by luck, so higher layers hold fewer items and let searches jump far. Randomness replaces the careful rebalancing of a tree.
The express-lane idea
Think of a subway. A local train stops at every station. An express train stops at only some. To travel far, ride the express to the station nearest your destination, then switch to the local. A skip list layers several such lines on top of each other.
To search for a key, start at the top-left. Move right while the next key on this level is smaller than your target. When the next key would overshoot, drop down one level and continue. At the bottom level, the next item is either your key or proof that it is not there.
It is the same trick as flipping through a dictionary. You first jump by thick groups of pages, then by thinner groups, then page by page.
