Skip lists are [[randomness|randomized]] algorithms that serve as alternatives to the balanced [[binary search tree]], first discovered by Bill Pugh in the late 1980's. Imagine a city transportation system with express trains, local trains, and buses. The simple idea is to take the most express route to any destination by taking the express train as far as it will take you before overshooting, switching to the local train, and finally taking the bus for the last mile. In skip lists, randomness is used to assign stops to each type of transportation. When inserting a new element, toss a coin to determine whether to assign the new element to each more express option. Like the binary search tree, the height of the skip list has a high probability of being $\Theta(\log_2 n)$, which means that search, insert and delete will also run in expected time $\Theta(\log_2 n)$.