Skip to Main Content
Data Structures Using C, 2nd Edition by Pearson
book

Data Structures Using C, 2nd Edition by Pearson

by A. K. Sharma
May 2024
Intermediate to advanced content levelIntermediate to advanced
521 pages
14h 12m
English
Pearson India
Content preview from 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 ()
{
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Data Structures Using C

Data Structures Using C

Samir Kumar Bandyopadhyay, Kashi Nath Dey
Intermediate C Programming, 2nd Edition

Intermediate C Programming, 2nd Edition

Yung-Hsiang Lu, George K. Thiruvathukal

Publisher Resources

ISBN: 9781299831582