Java Reference
In-Depth Information
/
**
Insertarecordintotheskiplist
*
/
publicvoidinsert(Keyk,EnewValue){
intnewLevel=randomLevel();//Newnode'slevel
if(newLevel>level) //Ifnewnodeisdeeper
AdjustHead(newLevel); // adjusttheheader
//Trackendoflevel
SkipNode<Key,E>[]update=
(SkipNode<Key,E>[])newSkipNode[level+1];
SkipNode<Key,E>x=head; //Startatheadernode
for(inti=level;i>=0;i--){//Findinsertposition
while((x.forward[i]!=null)&&
(k.compareTo(x.forward[i].key())>0))
x=x.forward[i];
update[i]=x; //Trackendatleveli
}
x=newSkipNode<Key,E>(k,newValue,newLevel);
for(inti=0;i<=newLevel;i++){ //Spliceintolist
x.forward[i]=update[i].forward[i];//Whoxpointsto
update[i].forward[i]=x; //Whoypointsto
}
size++;
//Incrementdictionarysize
}
Figure16.4
Implementation for the Skip List
Insert
function.
The ideal Skip List of Figure 16.2(c) has been organized so that (if the first and
last nodes are not counted) half of the nodes have only one pointer, one quarter
have two, one eighth have three, and so on. The distances are equally spaced; in
effect this is a “perfectly balanced” Skip List. Maintaining such balance would be
expensive during the normal process of insertions and deletions. The key to Skip
Lists is that we do not worry about any of this. Whenever inserting a node, we
assign it a level (i.e., some number of pointers). The assignment is random, using
a geometric distribution yielding a 50% probability that the node will have one
pointer, a 25% probability that it will have two, and so on. The following function
determines the level based on such a distribution:
/
**
Pickalevelusingageometricdistribution
*
/
intrandomLevel(){
intlev;
for(lev=0;DSutil.random(2)==0;lev++);//Donothing
returnlev;
}
Once the proper level for the node has been determined, the next step is to find
where the node should be inserted and link it in as appropriate at all of its levels.
Figure 16.4 shows an implementation for inserting a new value into the Skip List.
Figure 16.5 illustrates the Skip List insertion process. In this example, we
begin by inserting a node with value 10 into an empty Skip List. Assume that
randomLevel
returns a value of 1 (i.e., the node is at level 1, with 2 pointers).
Because the empty Skip List has no nodes, the level of the list (and thus the level
