Intro :- Skip list is a data structure that can be used as a alternative to balanced trees.Skip list built in layers as shown below.
L-1 – Layer 1 : Full part
L-2 – Layer 2: Sub Part
L-2 is an ordered linked list. If we apply find,insert and delete operation, complexity will be O(n) because the list must be scanned node by node from the head to the relevant node.
Explanation :-
In this case (Skip list) we have two layer and to search an element (let suppose 26) we start searching the element from layer 2 we move as far as the next node is not greater than the required node. As we can see 35 is greater than 26 so we will move to down layer (i.e L-1) from node 2 (i.e. 20) and will move further until relevant node is not found.
Complexity :-
In simple linked list that contains n node , to perform search operation it requires n number of comparisons. In this case complexity will be the sum of the nodes of layer 2 and nodes in a segment (i.e no. of nodes of layer 1 between two layer-2 nodes ).
Myprogworld 