SkiplistList: An Efficient Random-Access List
Explore the implementation of SkiplistList, a data structure that supports list operations like get, set, add, and remove in O(log n) expected time. Understand how edge lengths help navigate the skiplist efficiently and how elements are inserted and removed, allowing you to handle random access in lists effectively using skiplists.
We'll cover the following...
A SkiplistList implements the List interface using a skiplist structure. In a SkiplistList, 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 time.
The length of an edge
For this to be possible, we need a way to follow the search path for the element in . The easiest way to do this is to define the notion of the length of an edge in some list, . We define the length of every edge in as ...