4. Skiplists

In this chapter, we discuss a beautiful data structure: the skiplist, which has a variety of applications. Using a skiplist we can implement a List that is fast for all the operations $\mathtt{get(i)}$, $\mathtt{set(i,x)}$, $\mathtt{add(i,x)}$, and $\mathtt{remove(i)}$. We can also implement an SSet in which all operations run in $O(\log \ensuremath{\mathtt{n}})$ expected time.

Skiplists rely on randomization for their efficiency. In particular, a skiplist uses random coin tosses when an element is inserted to determine the height of that element. The performance of skiplists is expressed in terms of expected running times and lengths of paths. 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.