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 n)$ time.

The length of an edge

For this to be possible, we need a way to follow the search path for the $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_r$. We define the length of every edge in $L_0$ as $1$. The length of an edge, $e$, in $L_r$, $r > 0$, is defined as the sum of the lengths of the edges below $e$ in $L_{r−1}$. Equivalently, the length of $e$ is the number of edges in $L_0$ below $e$. See the illustration below for an example of a skiplist with the lengths of its edges shown.