# SkiplistList: An Efficient Random-Access List

Learn to implement a SkiplistList.

## We'll cover the following

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 below illustration for an example of a skiplist with the lengths of its edges shown.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy