4.3 SkiplistList: An Efficient Random-Access List

A SkiplistList implements the List interface using a skiplist structure. In a SkiplistList, $L_0$ contains the elements of the list in the order in which they appear in the list. As in a SkiplistSSet, elements can be added, removed, and accessed in $O(\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})$ time.

For this to be possible, we need a way to follow the search path for the $\ensuremath{\ensuremath{\mathit{i}}}$th element in $L_0$. The easiest way to do this is to define the notion of the length of an edge in some list, $L_{\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}}$. We define the length of every edge in $L_{0}$ as 1. The length of an edge, $\ensuremath{\ensuremath{\mathit{e}}}$, in $L_{\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}}$, $\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}>0$, is defined as the sum of the lengths of the edges below $\ensuremath{\ensuremath{\mathit{e}}}$ in $L_{\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}-1}$. Equivalently, the length of $\ensuremath{\ensuremath{\mathit{e}}}$ is the number of edges in $L_0$ below $\ensuremath{\ensuremath{\mathit{e}}}$. See Figure 4.5 for an example of a skiplist with the lengths of its edges shown. Since the edges of skiplists are stored in arrays, the lengths can be stored the same way:

Figure 4.5: The lengths of the edges in a skiplist.

The useful property of this definition of length is that, if we are currently at a node that is at position $\ensuremath{\ensuremath{\mathit{j}}}$ in $L_0$ and we follow an edge of length $\ell$, then we move to a node whose position, in $L_0$, is $\ensuremath{\ensuremath{\ensuremath{\mathit{j}}}}+\ell$. In this way, while following a search path, we can keep track of the position, $\ensuremath{\ensuremath{\mathit{j}}}$, of the current node in $L_0$. When at a node, $\ensuremath{\ensuremath{\mathit{u}}}$, in $L_{\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}}$, we go right if $\ensuremath{\ensuremath{\mathit{j}}}$ plus the length of the edge $\ensuremath{\ensuremath{\mathit{u}}.\ensuremath{\mathit{next}}[\ensuremath{\mathit{r}}]}$ is less than $\ensuremath{\ensuremath{\mathit{i}}}$. Otherwise, we go down into $L_{\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}-1}$.

Since the hardest part of the operations $\ensuremath{\mathrm{get}(\ensuremath{\mathit{i}})}$ and $\ensuremath{\mathrm{set}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ is finding the $\ensuremath{\ensuremath{\mathit{i}}}$th node in $L_0$, these operations run in $O(\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})$ time.

Adding an element to a SkiplistList at a position, $\ensuremath{\ensuremath{\mathit{i}}}$, is fairly simple. Unlike in a SkiplistSSet, we are sure that a new node will actually be added, so we can do the addition at the same time as we search for the new node's location. We first pick the height, $\ensuremath{\ensuremath{\mathit{k}}}$, of the newly inserted node, $\ensuremath{\ensuremath{\mathit{w}}}$, and then follow the search path for $\ensuremath{\ensuremath{\mathit{i}}}$. Any time the search path moves down from $L_{\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}}$ with $\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}\le \ensuremath{\ensuremath{\ensuremath{\mathit{k}}}}$, we splice $\ensuremath{\ensuremath{\mathit{w}}}$ into $L_{\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}}$. The only extra care needed is to ensure that the lengths of edges are updated properly. See Figure 4.6.

Figure 4.6: Adding an element to a SkiplistList.

Note that, each time the search path goes down at a node, $\ensuremath{\ensuremath{\mathit{u}}}$, in $L_{\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}}$, the length of the edge $\ensuremath{\ensuremath{\mathit{u}}.\ensuremath{\mathit{next}}[\ensuremath{\mathit{r}}]}$ increases by one, since we are adding an element below that edge at position $\ensuremath{\ensuremath{\mathit{i}}}$. Splicing the node $\ensuremath{\ensuremath{\mathit{w}}}$ between two nodes, $\ensuremath{\ensuremath{\mathit{u}}}$ and $\ensuremath{\ensuremath{\mathit{z}}}$, works as shown in Figure 4.7. While following the search path we are already keeping track of the position, $\ensuremath{\ensuremath{\mathit{j}}}$, of $\ensuremath{\ensuremath{\mathit{u}}}$ in $L_0$. Therefore, we know that the length of the edge from $\ensuremath{\ensuremath{\mathit{u}}}$ to $\ensuremath{\ensuremath{\mathit{w}}}$ is $\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}-\ensuremath{\ensuremath{\ensuremath{\mathit{j}}}}$. We can also deduce the length of the edge from $\ensuremath{\ensuremath{\mathit{w}}}$ to $\ensuremath{\ensuremath{\mathit{z}}}$ from the length, $\ell$, of the edge from $\ensuremath{\ensuremath{\mathit{u}}}$ to $\ensuremath{\ensuremath{\mathit{z}}}$. Therefore, we can splice in $\ensuremath{\ensuremath{\mathit{w}}}$ and update the lengths of the edges in constant time.

Figure 4.7: Updating the lengths of edges while splicing a node $\ensuremath{\ensuremath{\mathit{w}}}$ into a skiplist.

This sounds more complicated than it is, for the code is actually quite simple:

By now, the implementation of the $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ operation in a SkiplistList should be obvious. We follow the search path for the node at position $\ensuremath{\ensuremath{\mathit{i}}}$. Each time the search path takes a step down from a node, $\ensuremath{\ensuremath{\mathit{u}}}$, at level $\ensuremath{\ensuremath{\mathit{r}}}$ we decrement the length of the edge leaving $\ensuremath{\ensuremath{\mathit{u}}}$ at that level. We also check if $\ensuremath{\ensuremath{\mathit{u}}.\ensuremath{\mathit{next}}[\ensuremath{\mathit{r}}]}$ is the element of rank $\ensuremath{\ensuremath{\mathit{i}}}$ and, if so, splice it out of the list at that level. An example is shown in Figure 4.8.

Figure 4.8: Removing an element from a SkiplistList.

4.3.1 Summary

The following theorem summarizes the performance of the SkiplistList data structure:

Theorem 4..2   A SkiplistList implements the List interface. A SkiplistList supports the operations $\ensuremath{\mathrm{get}(\ensuremath{\mathit{i}})}$, $\ensuremath{\mathrm{set}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$, $\ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$, and $\ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ in $O(\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})$ expected time per operation.