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, ...