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
,
,
, and
. We can also implement an `SSet` in which
all operations run in
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.

- 4.1 The Basic Structure
- 4.2
`SkiplistSSet`: An Efficient`SSet`Implementation - 4.3
`SkiplistList`: An Efficient Random-Access`List`Implementation - 4.4 Analysis of Skiplists
- 4.5 Discussion and Exercises

opendatastructures.org