4.3 SkiplistList: An Efficient Random-Access List Implementation

A SkiplistList implements the List interface on top of a skiplist structure. In a SkiplistList, $L_0$ contains the elements of the list in the order they appear in the list. Just like with a 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.

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

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) {
        if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
        return findPred(i).next[0].x;
    }
    T set(int i, T x) {
        if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
        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 SkiplistList at a position, $\mathtt{i}$, is fairly straightforward. 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, $\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 SkiplistList.

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.

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

    void add(int i, T x) {
        if (i < 0 || i > n) throw new IndexOutOfBoundsException();
        Node w = new Node(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 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 SkiplistList.

    T remove(int i) {
        if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
        T x = null;
        Node u = sentinel;
        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];
                u.next[r] = u.next[r].next[r];
                if (u == sentinel && u.next[r] == null)
                    h--;
            }
            r--;
        }
        n--;
        return x;
    }

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