Skiplists ‐ Basic Structure - WilfullMurder/DataStructures-Java GitHub Wiki

Theoretically, a skiplist is a sequence of singly-linked lists L₀,...,L_h where each list L_r contains a subset of the items L_r-1. Starting with the input list L₀ that contains n items we then construct L₁ from L₀. L₂ from L₁, and so forth. 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 is heads. This process ends once we have created a list L_r that is empty. An example of a skiplist is shown in Fig.1.

For an element, x, in a skiplist, we refer to the height of x as the largest value, r, such that x appears in L_r. So, as an example, elements only appearing in L₀ have height 0. You may (or may not) notice that the height of x correlates with the following experiment: How many times will a coin toss show heads if it is tossed repeatedly until tails is shown? We would expect to toss the coin twice before getting tails (but don't count the last toss), so, the answer is that the expected height of a node is 1. The height of the skiplist is the height of the tallest node.

At the head of every list is a node, the sentinel, which acts as a dummy node (like the dummy node in a doubly-linked list) for the list. The foundational property of skiplists is that there is a short path, the search path, from the sentinel in L_h to every node in L₀. Fabricating the search path for a node, u, is straightforward (see Fig.2), we simply start at the top left of corner of the skiplist (corresponding to the sentinel in L_h) and always go right unless that would overshoot u, in which case we step down into the list below.

More specifically, to fabricate the search path for the node, u, in L₀, we begin at the sentinel, w, in L_h. Then, we examine w.next. If w.next contains an item that appears before u in L₀, we then set w=w.next. Else, we move down and continue the search at the occurence of w in the list L_h-1, continuing in this manner until we find the predecessor of u in L₀.

We can show (and prove) that the search path is quite short:

The expected length of the search path for any node, u, in L₀ is at most 2logn+O(1)=O(logn)

A space-efficient method of implementing a skiplist is to define a node, u, that incorporates a data value, x, and an array of pointers where u.next[i] points to u's successor in the list L_i. So, the data x in a node is referenced only once, even though x may appear in several lists.

The sections Skiplists ‐ an efficient Sorted Set and Skiplists ‐ an efficient Random‐Access List consider two different implementations of skiplists. In each implementation, L₀ stores the main structure (a list or sorted set of elements). The main difference between these structures is in how a search path is navigated; specifically, they diverge in how they decide if a search path should go down into L_r-1 or go right within L_r.