Skip Lists — let’s make it simple!

What are skip lists? The idea is actually quite intuitive. Let’s look at a real life example : You are travelling from Algoland (an imaginary city) and as a tourist, you would like to visit different places and cover as many spots as possible.

As seen in the image below : there are two subway lines — the pink one and the green one. Sheryl would like to visit queueland from algoland. Which subway line should she follow? Should she jump between subway lines?

One way could be — to take the green line, go through four stops — algoland, array land, stack land, trieland -> queueland.

The other option could be to take the pink line — start from algoland, travel to trieland, switch lines to the green line and travel to queueland from trieland.

Which one would be faster? Just looking at the number of nodes stopped at would tell us that taking the pink line, then jumping to the green line will be faster.

Algorithm

Let’s assume we have a linkedlist of sorted nodes :

2 -> 4 -> 23 -> 32 -> 41 -> 57 -> 68 -> 89 -> 91

If we have to search a number in this list, we would have to traverse through this list with a linear time complexity. Now, what would make searching for a number easier/faster? Maybe binary search? But, how…