# 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.

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.

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:

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.