Introduction to Skiplist

Skiplist overview

Here, we discuss a beautiful data structure: the skiplist, which has a variety of applications. Using a skiplist we can implement a List that has $O(\log n)$ time implementations of get(i), set(i, x), add(i, x), and remove(i). We can also implement an SSet in which all operations run in $O(\log n)$ expected time.

The efficiency of skiplists relies on their use of randomization. When a new element is added to a skiplist, the skiplist uses random coin tosses to determine the height of the new element. The performance of skiplists is expressed in terms of expected running times and path lengths. This expectation is taken over the random coin tosses used by the skiplist. In the implementation, the random coin tosses used by a skiplist are simulated using a pseudo-random number (or bit) generator.

Skiplist structure

Conceptually, a skiplist is a sequence of singly-linked lists $L_0,\cdots,L_h.$ Each list $L_r$ contains a subset of the items in $L_{r−1}$. We start with the input list $L_0$ that contains $n$ items and construct $L_1$ from $L_0, L_2$ from $L_1$, and so on. The items in $L_r$ are obtained by tossing a coin for each element, $x$, in $L_{r−1}$ and including $x$ in $L_r$ if the coin turns up as heads. This process ends when we create a list $L_r$ that is empty. An example of a skiplist is shown below: