Data Structures Using C, 2nd Edition by Pearson

480 Data Structures Using C

It may be noted that in level 1, links point to every second element in the list. In level 2, the links point to

every fourth element in the list. Thus, it can be deduced that a link in the ith level will point to 2*ith element

in the list. A point worth noting is that the last node of the skip list is pointed by links of all levels.

Now the search within the skip list shall take O(log n) time as it will follow binary search pattern.

For example, the search for ‘53’ will follow the route shown in Figure 10.27.

The algorithm that searches a value VAL in the skip list is given below:

Algorithm

skipListSearch ()

{