4.1 The Basic Structure

Conceptually, a skiplist is a sequence of singly-linked lists $ L_0,\ldots,L_h$. Each list $ L_r$ contains a subset of the items in $ L_{r-1}$. We start with the input list $ L_0$ that contains $ \ensuremath{\ensuremath{\mathit{n}}}$ items and construct $ L_1$ from $ L_0$, $ L_2$ from $ L_1$, and so on. The items in $ L_r$ are obtained by tossing a coin for each element, $ \ensuremath{\ensuremath{\mathit{x}}}$, in $ L_{r-1}$ and including $ \ensuremath{\ensuremath{\mathit{x}}}$ in $ L_r$ if the coin turns up as heads. This process ends when we create a list $ L_r$ that is empty. An example of a skiplist is shown in Figure 4.1.

Figure 4.1: A skiplist containing seven elements.
\includegraphics[width=\textwidth ]{figs-python/skiplist}

For an element, $ \ensuremath{\ensuremath{\mathit{x}}}$, in a skiplist, we call the height of $ \ensuremath{\ensuremath{\mathit{x}}}$ the largest value $ r$ such that $ \ensuremath{\ensuremath{\mathit{x}}}$ appears in $ L_r$. Thus, for example, elements that only appear in $ L_0$ have height 0. If we spend a few moments thinking about it, we notice that the height of $ \ensuremath{\ensuremath{\mathit{x}}}$ 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 $ L_h$ to every node in $ L_0$. Remembering how to construct a search path for a node, $ \ensuremath{\ensuremath{\mathit{u}}}$, is easy (see Figure 4.2) : Start at the top left corner of your skiplist (the sentinel in $ L_h$) and always go right unless that would overshoot $ \ensuremath{\ensuremath{\mathit{u}}}$, in which case you should take a step down into the list below.

More precisely, to construct the search path for the node $ \ensuremath{\ensuremath{\mathit{u}}}$ in $ L_0$, we start at the sentinel, $ \ensuremath{\ensuremath{\mathit{w}}}$, in $ L_h$. Next, we examine $ \ensuremath{\ensuremath{\mathit{w}}.\ensuremath{\mathit{next}}}$. If $ \ensuremath{\ensuremath{\mathit{w}}.\ensuremath{\mathit{next}}}$ contains an item that appears before $ \ensuremath{\ensuremath{\mathit{u}}}$ in $ L_0$, then we set $ \ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}=\ensuremath{\ensuremath{\ensuremath{\mathit{w}}.\ensuremath{\mathit{next}}}}$. Otherwise, we move down and continue the search at the occurrence of $ \ensuremath{\ensuremath{\mathit{w}}}$ in the list $ L_{h-1}$. We continue this way until we reach the predecessor of $ \ensuremath{\ensuremath{\mathit{u}}}$ in $ L_0$.

Figure 4.2: The search path for the node containing $ 4$ in a skiplist.
\includegraphics[width=\textwidth ]{figs-python/skiplist-searchpath}

The following result, which we will prove in Section 4.4, shows that the search path is quite short:

Lemma 4..1   The expected length of the search path for any node, $ \ensuremath{\ensuremath{\mathit{u}}}$, in $ L_0$ is at most $ 2\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}} + O(1) = O(\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})$.

A space-efficient way to implement a skiplist is to define a Node, $ \ensuremath{\ensuremath{\mathit{u}}}$, as consisting of a data value, $ \ensuremath{\ensuremath{\mathit{x}}}$, and an array, $ \ensuremath{\ensuremath{\mathit{next}}}$, of pointers, where $ \ensuremath{\ensuremath{\mathit{u}}.\ensuremath{\mathit{next}}[\ensuremath{\mathit{i}}]}$ points to $ \ensuremath{\ensuremath{\mathit{u}}}$'s successor in the list $ L_{\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}}$. In this way, the data, $ \ensuremath{\ensuremath{\mathit{x}}}$, in a node is referenced only once, even though $ \ensuremath{\ensuremath{\mathit{x}}}$ may appear in several lists.

The next two sections of this chapter discuss two different applications of skiplists. In each of these applications, $ L_0$ 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 $ L_{r-1}$ or go right within $ L_r$.