Skip lists are a relatively new data structure. This is an ordered list where the nodes are connected together at multiple levels. Different levels of connected nodes need not be uniform. This allows the skip list to skip items during a search. Each level is an ordered list in itself. Every node has a level and is connected to different nodes in the same level. This allows data structure operations to skip through the list. Example is the following list where there are two levels.
Level 1 connections E ----------> X
Level 0 connections A ->; B -> E -> F -> G->X -> Y -> Z
Level 0 list is the same as a linked list. E has connections has two levels. If a search was for say 'G'. The algorithms is as follows Start at Level 1, X > F so we move down at 'E' and then proceed at level 0 from E till G is found. Nodes A and B were skipped.
SkipList Search Algorithm:
1) Start from the top level proceed until level 0
a) Move to the right until a node with node Key < search Key
b) Jump to the next lower level.
2) If 1a resulted in an exit in level 0, the next node could be the search node. else it is absent.
Level 0 connections A -> B -> E -> G->X -> Y -> Z. We need to insert H with level 3 then, at level 1 we drop down at E and also at G in level 0. So, G->next = H at level 0, E-> next = H at level 1, F -> next = X at level 1 and at level 2 H is linked to head and tail of the list.
Level 2 connections *<-H->*
Level 1 connections E ----------->H-> X
Level 0 connections A -> B -> E -> F -> G->H->X -> Y -> Z
Runtime of Skip Lists: Dictionary operations on skip lists take O(Log(n)) time. Finding each new node's level is done in random as follows
Comparison of Skip List, Splay Binary Search Trees and Hash Table
For a serious input of 56000 word dictionary, the search operations on Skip lists, Splay Trees and Hash Table is as follows. Skip list took 40 comparisons at 11 levels to find the word 'Skip' in the dictionary.
Splay tree took less time than the skip list at