# 4.3: SkiplistList - An Efficient Random-Access List

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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 \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_{\mathtt{r}}$$. We define the length of every edge in $$L_{0}$$ as 1. The length of an edge, $$\mathtt{e}$$, in $$L_{\mathtt{r}}$$, $$\mathtt{r}>0$$, is defined as the sum of the lengths of the edges below $$\mathtt{e}$$ in $$L_{\mathtt{r}-1}$$. Equivalently, the length of $$\mathtt{e}$$ is the number of edges in $$L_0$$ below $$\mathtt{e}$$. See Figure $$\PageIndex{1}$$ 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 $$\PageIndex{1}$$: The lengths of the edges in a skiplist.
    class Node {
T x;
Node[] next;
int[] length;
@SuppressWarnings("unchecked")
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 $$\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_{\mathtt{r}}$$, we go right if $$\mathtt{j}$$ plus the length of the edge $$\texttt{u.next[r]}$$ is less than $$\mathtt{i}$$. Otherwise, we go down into $$L_{\mathtt{r}-1}$$.

    Node findPred(int i) {
Node u = sentinel;
int r = h;
int j = -1;   // 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.x;
}
T set(int i, T x) {
if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
Node u = findPred(i).next;
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 \mathtt{n})$$ time.

Adding an element to a SkiplistList at a position, $$\mathtt{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, $$\mathtt{k}$$, of the newly inserted node, $$\mathtt{w}$$, and then follow the search path for $$\mathtt{i}$$. Any time the search path moves down from $$L_{\mathtt{r}}$$ with $$\mathtt{r}\le \mathtt{k}$$, we splice $$\mathtt{w}$$ into $$L_{\mathtt{r}}$$. The only extra care needed is to ensure that the lengths of edges are updated properly. See Figure $$\PageIndex{2}$$. Figure $$\PageIndex{2}$$: Adding an element to a SkiplistList.

Note that, each time the search path goes down at a node, $$\mathtt{u}$$, in $$L_{\mathtt{r}}$$, the length of the edge $$\texttt{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 $$\PageIndex{3}$$. 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 $$\mathtt{i}-\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 $$\PageIndex{3}$$: Updating the lengths of edges while splicing a node $$\mathtt{w}$$ into a skiplist.

This sounds more complicated than it is, for 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();
}

    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]++; // accounts 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 $$\texttt{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 $$\PageIndex{4}$$. Figure $$\PageIndex{4}$$: 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;
}


## $$\PageIndex{1}$$ Summary

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

Theorem $$\PageIndex{1}$$.

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 \mathtt{n})$$ expected time per operation.

4.3: SkiplistList - An Efficient Random-Access List is shared under a CC BY license and was authored, remixed, and/or curated by Pat Morin.