SkiplistList: An Efficient Random-Access List

Learn to implement a SkiplistList.

A SkiplistList implements the List interface using a skiplist structure. In a SkiplistList, L0L_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(logn)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 ithi^{th} element in L0L_0. The easiest way to do this is to define the notion of the length of an edge in some list, LrL_r. We define the length of every edge in L0L_0 as 11. The length of an edge, ee, in LrL_r, r>0r > 0, is defined as the sum of the lengths of the edges below ee in Lr1L_{r−1}. Equivalently, the length of ee is the number of edges in L0L_0 below ee. 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