Skip list basics : search and insert

What is Skip List?

In last few posts, we discussed about singly linked lists, circular linked lists and doubly linked lists. Today, we will learn something related to singly linked list with something extra. This list is called as Skip List.

To understand skip list, follow one simple example. Example is of any subway or metro railway system. In any metro system, there is concept of fast and slow train. Fast train stops at major stops where as slow one stops at stations which are not covered by fast. Make it clear that slow train also stops on stations on which fast train stops and not every slow train stops at every station. Let’s take below figure as our route map.

skip list examples

Now say I want to go from station A and E. What should I do to reach my destination station as soon as possible. Start at A in fast train, get down at station prior to my destination, take slow train and reach my destination. In above route, I will get down at D and take slow at D to reach E.

skip list implementation

That is the typical concept of skip list. In example, we skip stations which we were sure that are not destinations.

Skip list goals

Skip list starts with goal in mind that how to make search more efficient in list. In typical linked list, to search an item, we need to scan through all nodes of list before the it. This makes complexity of search on list O(N).  Idea is can we skip lot of nodes before node which is to be searched is located. That leads to hierarchy of sorted linked lists.

Skip list is a data structure which can be considered as generalization of singly linked lists. Like in singly linked list, insertion and removal are simple and on top of that, search or retrieval in skip lists is also very efficient as compared to singly linked list.

Skip list looks like this:

search in skip list

Below is comparison chart of complexity of various operations on skip list and normal list :

Operation            Normal list                  Skip list
Insertion            O(N) at end                  O(log N)
                     O(1) at front
Deletion             O(N)                         O(log N)
Retrieval            O(N)                         O(log N)
Ordered traversal    O(N)                         O(N)

How to create skip list?

Problem of above list that it will take a long time before we reach the middle of list. If middle of sorted list can be reached efficiently, we can apply binary search algorithm like in array which will be O(log n) complexity.

To make above list a skip list follow below steps:

1. Start with singly linked list, which is in sorted order
2. Add every alternate node (even node) to level 2. This list skip one node of singly linked list between two nodes.
3. Add every alternate node of list at level 2 to this level. This level will contain n/4 nodes of original list.
4. Continue till h levels where there will be no node to be move to upper level.

How to search an element in skip list?

Algorithm is same as explained in example of subway.

1. Start with the top most level of list.
2. See if there are elements to be searched in it. If yes, check if next element is not null and greater than the key we are looking for? If yes, then move to lower level and repeat step 2.
3. If next element is not null and not less than key, move to next element and repeat step 2.

Let’s say we want to search number 8 in above skip list.

insert in skip list

Start from the top, check next node which is greater than key are looking for. So move down. Check next node which is 5. 5 is less than key 8, hence continue and check next node which is 9, which is greater, so move down at node 5.  Again check next which is 7 and less than key 8, hence move to 7. Check next of 7 at this level, which is 9, greater than key. Hence move down at 7 and check the next node at that level. Next node is 8, the key are looking for. Number of nodes traversed, 1 (to start with), 5, 7 and 8.

In next post, we will discuss how to implement skip lists, their randomized nature, and various applications of skip list.

Please share if you have any suggestion or feedback. Also, if you want to contribute to this blog, it is more than welcome, and paid too. Share if you liked the content, sharing is caring.