Java Reference
In-Depth Information
HEAD
5
25
30
31
42
58
62
69
0
(A)
HEAD
5
25
30
31
42
58
62
69
0
1
(B)
HEAD
5
25
30
31
42
58
62
69
0
1
2
(C)
Figure16.2
Illustration of the Skip List concept. (a) A simple linked list.
(b) Augmenting the linked list with additional pointers at every other node. To
find the node with key value 62, we visit the nodes with values 25, 31, 58, and 69,
then we move from the node with key value 58 to the one with value 62. (c) The
ideal Skip List, guaranteeing O(log n) search time. To find the node with key
value 62, we visit nodes in the order 31, 69, 58, then 69 again, and finally, 62.
/
**
SkiplistSearch
*
/
publicEfind(KeysearchKey){
SkipNode<Key,E>x=head; //Dummyheadernode
for(inti=level;i>=0;i--) //Foreachlevel...
while((x.forward[i]!=null)&&//goforward
(searchKey.compareTo(x.forward[i].key())>0))
x=x.forward[i]; //Goonelaststep
x=x.forward[0];//Movetoactualrecord,ifitexists
if((x!=null)&&(searchKey.compareTo(x.key())==0))
returnx.element(); //Gotit
elsereturnnull; //Itsnotthere
}
Figure16.3
Implementation for the Skip List
find
function.
