Skip Lists

skip list is a data structure, which makes the searching of element faster in sorted list. The idea is very simple, create multiple layers, so we can skip some nodes immediately while searching.

For example, consider the below figure, where there are 11 nodes and 2 layers. Layer1 contains 3 elements (10,37, 98), Layer2 contains 11 elements (10, 20, 23, 29, 34, 37, 59, 76, 85, 91, 98).

Suppose we want to search for an element 76, we start from first node of layer1 i.e, 10 and traverse the next nodes in layer1 until we find a node with data greater than or equal to 76. with this we stop our search in between 37 and 98. We are simply skipping the elements between 10 and 37. 

                                                             Home