Subsections


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.
\includegraphics[width=\textwidth ]{figs-python/skiplist-lengths}

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}$.


\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{find\_pred}(...
...bf{return}} \ensuremath{\ensuremath{\mathit{u}}}\\
\end{flushleft}\end{leftbar}

\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{get}(\ensure...
...bf{return}} \ensuremath{\ensuremath{\mathit{y}}}\\
\end{flushleft}\end{leftbar}

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.
\includegraphics[width=\textwidth ]{figs-python/skiplist-addix}

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.
\includegraphics[scale=0.90909]{figs-python/skiplist-lengths-splice}

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


\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{add}(\ensure...
...nsuremath{\mathit{i}}, \ensuremath{\mathit{w}})}\\
\end{flushleft}\end{leftbar}

\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{add}(\ensure...
...bf{return}} \ensuremath{\ensuremath{\mathit{u}}}\\
\end{flushleft}\end{leftbar}

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.
\includegraphics[width=\textwidth ]{figs-python/skiplist-removei}

\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{remove}(\ens...
...k} \textbf{return}} \ensuremath{x}\hspace*{1em} \\
\end{flushleft}\end{leftbar}

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.

opendatastructures.org