__Skip Lists__

__Skip Lists__

*Link**e**d list *is the simplest of all dynamic data structures implementing a *Dictionary*. How- ever, the complexity of *Search *operation is *O*(*n*) in a *Linked list*. Even the *Insert *and *Delete** *operations require *O*(*n*) time if we do not specify the exact position of the item in the list. *Skip List *is a novel structure, where using randomness, we construct a number of progressively smaller lists and maintain this collection in a clever way to provide a data structure that is competitive to balanced tree structures. The main advantage oﬀered by skip list is that the codes implementing the dictionary operations are very simple and resemble list operations. No complicated structural transformations such as *rotations *are done and yet the expected time complexity of *Dictionary *operations on *Skip Lists *are quite comparable to that of AVL trees or splay trees. *Skip Lists *are introduced by Pugh [6].

Then, we say that the collection *S*0*, S*1*, S*2*,…**, S**r *deﬁnes a *leveling with **r **level**s on **S*. The keys in *S**i *are said to be in level *i, *0 *≤ **i **≤ **r*. The set *S*0 is called the base level for the leveling scheme. Notice that there is exactly one empty level, namely *S**r *. The level number *l*(*k*) of a key *k **∈ **S *is deﬁned by

For an eﬃcient implementation of the dictionary, instead of working with the current set *S *of keys, we would rather work with a leveling of *S*. The items of *S**i *will be put in the *increasing order *in a linked list denoted by *L**i*. We attach the special keys *−**∞ *at the beginning and +*∞ *at the end of each list *L**i *as sentinels. In practice, *−**∞ *is a key value that is smaller than any key we consider in the application and +*∞ *denotes a key value larger than all the possible keys. A leveling of *S *is implemented by maintaining all the lists *L*0*, L*1*, L*2*,…**, L**r *with some more additional links as shown in Figure 13.1. Speciﬁcally, the box containing a key *k *in *L**i *will have a pointer to the box containing *k *in *L**i**−*1. We call such pointers *descent pointers*. The links connecting items of the same list are called *ho**rizontal pointers*. Let *B *be a pointer to a box in the skip list. We use the notations *H**next*[*B*], and *D**next*[*B*], for the horizontal and descent pointers of the box pointed by *B** *respectively. The notation *k**e**y*[*B*] is used to denote the key stored in the box pointed by *B*.

The name of the skip list is nothing but a pointer to the box containing *−**∞ *in the *r*th level as shown in the ﬁgure. From the Figure 13.1 it is clear that *L**i *has horizontal pointers that skip over several intermediate elements of *L**i**−*1. That is why this data structure is called the *Skip List*.

How do we arrive at a leveling for a given set? We may construct *S**i*+1 from *S**i *in a systematic, deterministic way. While this may not pose any problem for a static search problem, it will be extremely cumbersome to implement the dynamic dictionary operations. This is where randomness is helpful. To get *S**i*+1 from *S**i*, we do the following. For each element *k *of *S**i *toss a coin and include *k *in *S**i*+1 iﬀ we get *success *in the coin toss. If the coin is *p*-biased, we expect *| **S**i*+1 *| *to be roughly equal to *p **| **S**i **|*. Starting from *S*, we may repeatedly obtain sets corresponding to successive levels. Since the coin tosses are independent, there is another useful, and equivalent way to look at our construction. For each key *k *in *S*, keep tossing a coin until we get a *failure*. Let *h *be the number of successes before the ﬁrst failure. Then, we include *k *in *h *further levels treating *S *= *S*0 as the base level. In other words, we include *k *in the sets *S*1*, S*2*,…**, S**h*. This suggests us to deﬁne a random variable *Z**i *for each key *k**i **∈ **S*0 to be the number of times we toss a p-biased coin before we obtain a *failure*. Since *Z**i *denotes the number of additional copies of *k**i *in the skip list, the value *maximum**{**Z**i *: 1 *≤ **i **≤ **n**} *deﬁnes the highest nonempty level. Hence, we have,

where *r *is the number of levels and *| **S**L **| *is the number of boxes or the space complexity measure of the *Skip List*. In the expression for *| **S**L **| *we have added *n *to count the keys in the base level and 2*r *+ 2 counts the sentinel boxes containing +*∞ *and *−**∞ *in each level.