Question

1.Note that the skip list defines MAX_LEVEL as the largest number of levels a particular node could have. Is there a point when this MAX level would tend to reduce performance? Can you quantify that point? What happens to performance?

Answer 1

We have Linked Lists for Easy to insert & delete in O(1) time and we don’t need to estimate total memory needed .But we have some drawbacks of Linked List too i.e. in Linked list it is hard to search in less than O(n) time and hard to jump to the middle for eg. binary search doesn’t work.

So to fix these drowbacks we have Skip list that has good data structure for a dictionary ADT. Skip list was invented around 1990 by Bill Pugh. It is a generalization of sorted linked lists so simple to implement . Expected search time in Skip list is O(log n).It has randomized data structure that uses random coin flips to build the data structure.

Here is the example of perfect skip list because it has-

1. Keys in sorted order.
2. O(log n) levels
3. Each higher level contains 1/2 the elements of the level below it.

Header & sentinel nodes are in every level

1. Nodes are of variable size: - contain between 1 and O(log n) pointers.
2. Pointers point to the start of each node (picture draws pointers horizontally for visual clarity).
3. Called skip lists because higher level lists let you skip over many items.

When search for k:

If k = key, done!

If k < next key, go down a level

If k ≥ next key, go right

In other words we can say to find an item, we scan along the shortest list until we would “pass” the desired item. At that point, we drop down to a slightly more complete list at one level lower.