Skip list in java

Question

I was going through data structures in java under the topic Skip list and I came across the following:

In a skip list of n nodes, for each k and i such that 1 ≤ k ≤lg n and 1 ≤ i ≤ n/2k–1⎦ – 1, the node in position 2k–1 · i points to the node in position 2k–1 · (i + 1). This means that every second node points to the node two positions ahead, every fourth node points to the node four positions ahead, and so on, as shown in Figure 3.17a. This is accomplished by having different numbers of reference fields in nodes on the list: Half of the nodes have just one reference field, one-fourth of the nodes have two reference fields, one-eighth of the nodes have three reference fields, and so on. The number of reference fields indicates the level of each node, and the number of levels is maxLevel = ⎣lg n⎦ + 1.

And the figure is : A skip list with (a) evenly and (b) unevenly spaced nodes of different levels; (c) the skip list with reference nodes clearly shown.

I don't understand the mathematical part and what exactly the sktip list is and even nodes?

Answer 1

Ok let me try to make you understand this.

A skip list is a data-structure which definitely makes your searches faster in a list of given elements.

A better analogy would be a network of subway in any of the bigger cities. Imagine there are 90 stations to cover and there are different lines (Green, Yellow and Blue).

The Green line only connects the stations numbered 0, 30, 60 and 90 The Yellow line connects 0, 10, 20, 30, 40, 50, 60, 70, 80 and 90 The blue line connects all the station from 0 through 90.

If you want to board the train at station 0 and want to get down at 75. What is the best strategy?

Common sense would suggest to board a train on Green line from station 0 and get down at station 60. Board another train on Yellow line from station 60 and get down at station 70. Board another train on Blue line from station 70 and get down at 75.

Any other way would have been more time consuming.

Now replace the stations with the nodes and lines with three individual lists (the set of these lists are called skip list).

And just imaging that you wanted to search an element at a node containing the value 75.

I hope this explains what Skip Lists are and how they are efficient.

In the traditional approach of searching, you could have visited each node and got to 75 in 75 hops. In case of binary search you would have done it in logN In skip list you can do the same in 1 + 1 + 15 in our particular case. You can do the math, seems to be simple though :)

EDIT: Evenly spaced nodes & Unevenly spaced nodes As you can see my analogy, it has equal number of stations between each node on each line. This is evenly spaced nodes. It is an ideal situation.

To understand it better we need to understand the creation of Skip Lists.

In the early stages of its construction there is only one list (the blue line) and each new node is first added to the list at an appropriate location. When the number of nodes in the blue line increases then there comes a need to create another list (yellow line) and promote one of the nodes to list 2. (PS: The first and the last element of list 1 is always promoted to the newly added list in the skip lists set). Hence, the moment a new list is added it will have three nodes.

Promotion Strategy : How to find out which node to promote from the bottom most list(blue line) to the upper lists (yellow line and green line).

The best way to decide is randomly :) So lets say upon addition of a new node, we flip a coin to see if it can be promoted to the second list. if yes, then we add it to the second list and then flip a coin again to check if it has to be added in the third list or not.

So you see, if you use this random mechanism, there might arrive situations where the nodes are unevenly spaced. :)

Hope this helps.