A SkiplistSSet uses a skiplist structure to implement the SSet interface. Used this way, the list L₀ stores elements of the SSet in sorted order. The find(x) method follows the search path for the smallest value, y, where y≥x.

Following the search path for y is straightforward: when positioned at some node, u, in L_r, we look to the right at u.next[i]. If x > u.next[i].x, then we step to the right in L_r; else, we move down into L_r-1. Each step (regardless of direction) only takes constant time; so, by Lemma Skip.1, the expected running time of find(x) is O(logn).

Before we can add an element, we need to simulate tossing coins to determine the height, k, of a new node. To do this we pick a random integer, z, and count the number of trailing 1's in the binary representation of z. It should be noted that this method is not an exact replication of the coin-tossing experiment as the value of k will always be less than the number of bits in an int. Nevertheless, this has a negligable impact unless the number of elements in the structure is greater than 2³² = 4294967296.

To implement the add(x) method, we search for x and then splice x into a few lists L₀,...,L_k, where k is selected using the above (pickHeight()) method. The least complicated way of achieving this is to use an array, stack, that tracks the nodes at which the search path goes down from the some list L_r into L_r-1. More accurately, stack[r] is the node in L_r where the search path proceeded into L_r-1. The nodes being modified to insert x are the nodes stack[0],...,stack[k] (See Fig.1).

Removing an element is achieved in a similar manner, but without the need for stack to track the search path. The removal can be achieved as we follow the search path. We search for x afn each time the search moves down from a node, u, we check if u.next=x and id so, we splice u out of the list (see Fig.2).

The following theorem summarizes the performance of skiplists when implementing sorted sets:

SkiplistSSet implements the SSet interface. A SkiplistSSet supports the operations add(x), remove(x), and find(x) in O(logn) expected time per operation.