Conceptually, a skiplist is a sequence of singly-linked lists . Each list contains a subset of the items in . We start with the input list that contains items and construct from , from , and so on. The items in are obtained by tossing a coin for each element, , in and including in if the coin turns up as heads. This process ends when we create a list that is empty. An example of a skiplist is shown in Figure 4.1.
For an element, , in a skiplist, we call the height of the largest value such that appears in . Thus, for example, elements that only appear in have height 0. If we spend a few moments thinking about it, we notice that the height of corresponds to the following experiment: Toss a coin repeatedly until it comes up as tails. How many times did it come up as heads? The answer, not surprisingly, is that the expected height of a node is 1. (We expect to toss the coin twice before getting tails, but we don't count the last toss.) The height of a skiplist is the height of its tallest node.
At the head of every list is a special node, called the sentinel, that acts as a dummy node for the list. The key property of skiplists is that there is a short path, called the search path, from the sentinel in to every node in . Remembering how to construct a search path for a node, , is easy (see Figure 4.2) : Start at the top left corner of your skiplist (the sentinel in ) and always go right unless that would overshoot , in which case you should take a step down into the list below.
More precisely, to construct the search path for the node in , we start at the sentinel, , in . Next, we examine . If contains an item that appears before in , then we set . Otherwise, we move down and continue the search at the occurrence of in the list . We continue this way until we reach the predecessor of in .
The following result, which we will prove in Section 4.4, shows that the search path is quite short:
A space-efficient way to implement a skiplist is to define a Node, , as consisting of a data value, , and an array, , of pointers, where points to 's successor in the list . In this way, the data, , in a node is referenced only once, even though may appear in several lists.
The next two sections of this chapter discuss two different applications of skiplists. In each of these applications, stores the main structure (a list of elements or a sorted set of elements). The primary difference between these structures is in how a search path is navigated; in particular, they differ in how they decide if a search path should go down into or go right within .