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.

class Node<T> { T x; Node<T>[] next; Node(T ix, int h) { x = ix; next = (Node<T>[])Array.newInstance(Node.class, h+1); } int height() { return next.length - 1; } }

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 .

opendatastructures.org