Understanding Skip Lists

First Lets try to understand why do we need skip lists?

Lets suppose we have a sorted linked list which looks something like this 👇

1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9

Sorted linked lists are known for maintaining elements in a sorted order. Despite their simplicity, they have a critical limitation: searching for an element has a time complexity of O(n) because we have to move from one node to other and keep doing it till we don't get the desired value, which can be inefficient for large datasets.

So what can we do????

What we can do is we can create one more lane something like this 👇

1 --------------------------------------------- 9
|                       |                       |
1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9

Now if we want to search for 7 what we can do we will go from 1 to 5 and then we can search 7 so this will reduce the overall time complexity.

So basically skip lists were introduced as a scalable alternative to sorted linked lists and balanced trees. They allow for faster search operations, typically offering O(log n) complexity, by adding additional forward pointers and levels to the traditional linked list structure.

Implementing skip lists involves creating nodes with forward pointers that span multiple layers. The number of layers and the distance each pointer skips are usually determined randomly.

Skip lists are an elegant solution that combines the simplicity of linked lists with the efficiency of balanced search algorithms. They are a powerful tool for managing sorted data structures in a scalable and efficient manner.