Subsections


4.3 $ \mathtt{SkiplistList}$: An Efficient Random-Access $ \mathtt{List}$ Implementation

A $ \mathtt{SkiplistList}$ implements the $ \mathtt{List}$ interface on top of a skiplist structure. In a $ \mathtt{SkiplistList}$, $ L_0$ contains the elements of the list in the order they appear in the list. Just like with a $ \mathtt{SkiplistSSet}$, elements can be added, removed, and accessed in $ O(\log \ensuremath{\mathtt{n}})$ time.

For this to be possible, we need a way to follow the search path for the $ \mathtt{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{\mathtt{r}}}$. We define the length of every edge in $ L_{0}$ as 1. The length of an edge, $ \mathtt{e}$, in $ L_{\ensuremath{\mathtt{r}}}$, $ \ensuremath{\mathtt{r}}>0$, is defined as the sum of the lengths of the edges below $ \mathtt{e}$ in $ L_{\ensuremath{\mathtt{r}}-1}$. Equivalently, the length of $ \mathtt{e}$ is the number of edges in $ L_0$ below $ \mathtt{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{figs/skiplist-lengths}

  struct Node {
    T x;
    int height;     // length of next
    int *length;
    Node **next;
  };

The useful property of this definition of length is that, if we are currently at a node that is at position $ \mathtt{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{\mathtt{j}}+\ell$. In this way, while following a search path, we can keep track of the position, $ \mathtt{j}$, of the current node in $ L_0$. When at a node, $ \mathtt{u}$, in $ L_{\ensuremath{\mathtt{r}}}$, we go right if $ \mathtt{j}$ plus the length of the edge $ \mathtt{u.next[r]}$ is less than $ \mathtt{i}$, otherwise we go down into $ L_{\ensuremath{\mathtt{r}}-1}$.

  Node* findPred(int i) {
    Node *u = sentinel;
    int r = h;
    int j = -1;   // the index of the current node in list 0
    while (r >= 0) {
      while (u->next[r] != NULL && j + u->length[r] < i) {
        j += u->length[r];
        u = u->next[r];
      }
      r--;
    }
    return u;
  }
  T get(int i) {
    return findPred(i)->next[0]->x;
  }
  T set(int i, T x) {
    Node *u = findPred(i)->next[0];
    T y = u->x;
    u->x = x;
    return y;
  }

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

Adding an element to a $ \mathtt{SkiplistList}$ at a position, $ \mathtt{i}$, is fairly straightforward. Unlike in a $ \mathtt{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, $ \mathtt{k}$, of the newly inserted node, $ \mathtt{w}$, and then follow the search path for $ \mathtt{i}$. Anytime the search path moves down from $ L_{\ensuremath{\mathtt{r}}}$ with $ \ensuremath{\mathtt{r}}\le \ensuremath{\mathtt{k}}$, we splice $ \mathtt{w}$ into $ L_{\ensuremath{\mathtt{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 $ \mathtt{SkiplistList}$.
\includegraphics{figs/skiplist-addix}

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

Figure 4.7: Updating the lengths of edges while splicing a node $ \mathtt{w}$ into a skiplist.
\includegraphics{figs/skiplist-lengths-splice}

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

  void add(int i, T x) {
    Node *w = newNode(x, pickHeight());
    if (w->height > h)
      h = w->height;
    add(i, w);
  }
  Node* add(int i, Node *w) {
    Node *u = sentinel;
    int k = w->height;
    int r = h;
    int j = -1; // index of u
    while (r >= 0) {
      while (u->next[r] != NULL && j + u->length[r] < i) {
        j += u->length[r];
        u = u->next[r];
      }
      u->length[r]++; // to account for new node in list 0
      if (r <= k) {
        w->next[r] = u->next[r];
        u->next[r] = w;
        w->length[r] = u->length[r] - (i - j);
        u->length[r] = i - j;
      }
      r--;
    }
    n++;
    return u;
  }

By now, the implementation of the $ \mathtt{remove(i)}$ operation in a $ \mathtt{SkiplistList}$ should be obvious. We follow the search path for the node at position $ \mathtt{i}$. Each time the search path takes a step down from a node, $ \mathtt{u}$, at level $ \mathtt{r}$ we decrement the length of the edge leaving $ \mathtt{u}$ at that level. We also check if $ \mathtt{u.next[r]}$ is the element of rank $ \mathtt{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 $ \mathtt{SkiplistList}$.
\includegraphics{figs/skiplist-removei}
  T remove(int i) {
    T x = NULL;
    Node *u = sentinel, *del;
    int r = h;
    int j = -1; // index of node u
    while (r >= 0) {
      while (u->next[r] != NULL && j + u->length[r] < i) {
        j += u->length[r];
        u = u->next[r];
      }
      u->length[r]--; // for the node we are removing
      if (j + u->length[r] + 1 == i && u->next[r] != NULL) {
        x = u->next[r]->x;
        u->length[r] += u->next[r]->length[r];
        del = u->next[r];
        u->next[r] = u->next[r]->next[r];
        if (u == sentinel && u->next[r] == NULL)
          h--;
      }
      r--;
    }
    deleteNode(del);
    n--;
    return x;
  }

4.3.1 Summary

The following theorem summarizes the performance of the $ \mathtt{SkiplistList}$ data structure:

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

opendatastructures.org