• 4 Skiplists
• 4.1 The Basic Struc­ture
• 4.2 SkiplistSSet: An Ef­fi­cient SSet
• 4.2.1 Sum­mary
• 4.3 SkiplistList: An Ef­fi­cient Ran­dom-Ac­cess List
• 4.3.1 Sum­mary
• 4.4 Analy­sis of Skiplists
• 4.5 Dis­cus­sion and Ex­er­cises

In this chap­ter, we dis­cuss a beau­ti­ful data struc­ture: the skiplist, which has a va­ri­ety of ap­pli­ca­tions. Using a skiplist we can im­ple­ment a List that has $O(\log n)$ time im­ple­men­ta­tions of get(i), set(i,x), add(i,x), and remove(i). We can also im­ple­ment an SSet in which all op­er­a­tions run in $O(\log \texttt{n})$ ex­pected time.

The ef­fi­ciency of skiplists re­lies on their use of ran­dom­iza­tion. When a new el­e­ment is added to a skiplist, the skiplist uses ran­dom coin tosses to de­ter­mine the height of the new el­e­ment. The per­for­mance of skiplists is ex­pressed in terms of ex­pected run­ning times and path lengths. This ex­pec­ta­tion is taken over the ran­dom coin tosses used by the skiplist. In the im­ple­men­ta­tion, the ran­dom coin tosses used by a skiplist are sim­u­lated using a pseudo-ran­dom num­ber (or bit) gen­er­a­tor.

4.1 The Basic Struc­ture

Con­cep­tu­ally, a skiplist is a se­quence of singly-linked lists $L_0,\ldots,L_h$. Each list $L_r$ con­tains a sub­set of the items in $L_{r-1}$. We start with the input list $L_0$ that con­tains n items and con­struct $L_1$ from $L_0$, $L_2$ from $L_1$, and so on. The items in $L_r$ are ob­tained by toss­ing a coin for each el­e­ment, x, in $L_{r-1}$ and in­clud­ing x in $L_r$ if the coin turns up as heads. This process ends when we cre­ate a list $L_r$ that is empty. An ex­am­ple of a skiplist is shown in Fig­ure 4.1.

Fig­ure 4.1 A skiplist con­tain­ing seven el­e­ments.

For an el­e­ment, x, in a skiplist, we call the height of x the largest value $r$ such that x ap­pears in $L_r$. Thus, for ex­am­ple, el­e­ments that only ap­pear in $L_0$ have height $0$. If we spend a few mo­ments think­ing about it, we no­tice that the height of x cor­re­sponds to the fol­low­ing ex­per­i­ment: Toss a coin re­peat­edly until it comes up as tails. How many times did it come up as heads? The an­swer, not sur­pris­ingly, is that the ex­pected height of a node is 1. (We ex­pect to toss the coin twice be­fore get­ting tails, but we don't count the last toss.) The height of a skiplist is the height of its tallest node.

At the head of every list is a spe­cial node, called the sen­tinel, that acts as a dummy node for the list. The key prop­erty of skiplists is that there is a short path, called the search path, from the sen­tinel in $L_h$ to every node in $L_0$. Re­mem­ber­ing how to con­struct a search path for a node, u, is easy (see Fig­ure 4.2) : Start at the top left cor­ner of your skiplist (the sen­tinel in $L_h$) and al­ways go right un­less that would over­shoot u, in which case you should take a step down into the list below.

More pre­cisely, to con­struct the search path for the node u in $L_0$, we start at the sen­tinel, w, in $L_h$. Next, we ex­am­ine w.next. If w.next con­tains an item that ap­pears be­fore u in $L_0$, then we set $\texttt{w}=\texttt{w.next}$. Oth­er­wise, we move down and con­tinue the search at the oc­cur­rence of w in the list $L_{h-1}$. We con­tinue this way until we reach the pre­de­ces­sor of u in $L_0$.

Fig­ure 4.2 The search path for the node con­tain­ing $4$ in a skiplist.

The fol­low­ing re­sult, which we will prove in Sec­tion 4.4, shows that the search path is quite short:

A space-ef­fi­cient way to im­ple­ment a skiplist is to de­fine a Node, u, as con­sist­ing of a data value, x, and an array, next, of point­ers, where u.next[i] points to u's suc­ces­sor in the list $L_{\texttt{i}}$. In this way, the data, x, in a node is ref­er­enced only once, even though x may ap­pear in sev­eral lists.

    class Node<T> {
        T x;
        Node<T>[] next;
        Node(T ix, int h) {
            x = ix;
            next = (Node<T>[])Array.newInstance(Node.class, h+1);
        }
        int height() {
            return next.length - 1;
        }
    }

The next two sec­tions of this chap­ter dis­cuss two dif­fer­ent ap­pli­ca­tions of skiplists. In each of these ap­pli­ca­tions, $L_0$ stores the main struc­ture (a list of el­e­ments or a sorted set of el­e­ments). The pri­mary dif­fer­ence be­tween these struc­tures is in how a search path is nav­i­gated; in par­tic­u­lar, they dif­fer in how they de­cide if a search path should go down into $L_{r-1}$ or go right within $L_r$.

4.2 SkiplistSSet: An Ef­fi­cient SSet

A SkiplistSSet uses a skiplist struc­ture to im­ple­ment the SSet in­ter­face. When used in this way, the list $L_0$ stores the el­e­ments of the SSet in sorted order. The find(x) method works by fol­low­ing the search path for the small­est value y such that $\texttt{y}\ge\texttt{x}$:

    T find(T x) {
        Node<T> u = findPredNode(x);
        return u.next[0] == null ? null : u.next[0].x;
    }
    Node<T> findPredNode(T x) {
        Node<T> u = sentinel;
        int r = h;
        while (r >= 0) {
            while (u.next[r] != null && c.compare(u.next[r].x,x) < 0)
                u = u.next[r];   // go right in list r
            r--;               // go down into list r-1
        }
        return u;
    }

Fol­low­ing the search path for y is easy: when sit­u­ated at some node, u, in $L_{\texttt{r}}$, we look right to u.next[r].x. If $\texttt{x}>\texttt{u.next[r].x}$, then we take a step to the right in $L_{\texttt{r}}$; oth­er­wise, we move down into $L_{\texttt{r}-1}$. Each step (right or down) in this search takes only con­stant time; thus, by Lemma 4.1, the ex­pected run­ning time of find(x) is $O(\log \texttt{n})$.

Be­fore we can add an el­e­ment to a SkipListSSet, we need a method to sim­u­late toss­ing coins to de­ter­mine the height, k, of a new node. We do so by pick­ing a ran­dom in­te­ger, z, and count­ing the num­ber of trail­ing $1$s in the bi­nary rep­re­sen­ta­tion of z:⁷This method does not ex­actly repli­cate the coin-toss­ing ex­per­i­ment since the value of k will al­ways be less than the num­ber of bits in an int. How­ever, this will have neg­li­gi­ble im­pact un­less the num­ber of el­e­ments in the struc­ture is much greater than $2^{32}=4294967296$.

    int pickHeight() {
        int z = rand.nextInt();
        int k = 0;
        int m = 1;
        while ((z & m) != 0) {
            k++;
            m <<= 1;
        }
        return k;
    }

To im­ple­ment the add(x) method in a SkiplistSSet we search for x and then splice x into a few lists $L_0$,…,$L_{\texttt{k}}$, where k is se­lected using the pickHeight() method. The eas­i­est way to do this is to use an array, stack, that keeps track of the nodes at which the search path goes down from some list $L_{\texttt{r}}$ into $L_{\texttt{r}-1}$. More pre­cisely, stack[r] is the node in $L_{\texttt{r}}$ where the search path pro­ceeded down into $L_{\texttt{r}-1}$. The nodes that we mod­ify to in­sert x are pre­cisely the nodes $\texttt{stack[0]},\ldots,\texttt{stack[k]}$. The fol­low­ing code im­ple­ments this al­go­rithm for add(x):

    boolean add(T x) {
        Node<T> u = sentinel;
        int r = h;
        int comp = 0;
        while (r >= 0) {
            while (u.next[r] != null 
                   && (comp = c.compare(u.next[r].x,x)) < 0)
                u = u.next[r];
            if (u.next[r] != null && comp == 0) return false;
            stack[r--] = u;          // going down, store u
        }
        Node<T> w = new Node<T>(x, pickHeight());
        while (h < w.height())
            stack[++h] = sentinel;   // height increased
        for (int i = 0; i < w.next.length; i++) {
            w.next[i] = stack[i].next[i];
            stack[i].next[i] = w;
        }
        n++;
        return true;
    }

Fig­ure 4.3 Adding the node con­tain­ing $3.5$ to a skiplist. The nodes stored in stack are high­lighted.

Re­mov­ing an el­e­ment, x, is done in a sim­i­lar way, ex­cept that there is no need for stack to keep track of the search path. The re­moval can be done as we are fol­low­ing the search path. We search for x and each time the search moves down­ward from a node u, we check if $\texttt{u.next.x}=\texttt{x}$ and if so, we splice u out of the list:

    boolean remove(T x) {
        boolean removed = false;
        Node<T> u = sentinel;
        int r = h;
        int comp = 0;
        while (r >= 0) {
            while (u.next[r] != null 
                   && (comp = c.compare(u.next[r].x, x)) < 0) {
                u = u.next[r];
            }
            if (u.next[r] != null && comp == 0) {
                removed = true;
                u.next[r] = u.next[r].next[r];
                if (u == sentinel && u.next[r] == null)
                    h--;  // height has gone down
            }
            r--;
        }
        if (removed) n--;
        return removed;
    }

Fig­ure 4.4 Re­mov­ing the node con­tain­ing $3$ from a skiplist.

4.2.1 Sum­mary

The fol­low­ing the­o­rem sum­ma­rizes the per­for­mance of skiplists when used to im­ple­ment sorted sets:

4.3 SkiplistList: An Ef­fi­cient Ran­dom-Ac­cess List

A SkiplistList im­ple­ments the List in­ter­face using a skiplist struc­ture. In a SkiplistList, $L_0$ con­tains the el­e­ments of the list in the order in which they ap­pear in the list. As in a SkiplistSSet, el­e­ments can be added, re­moved, and ac­cessed in $O(\log \texttt{n})$ time.

For this to be pos­si­ble, we need a way to fol­low the search path for the ith el­e­ment in $L_0$. The eas­i­est way to do this is to de­fine the no­tion of the length of an edge in some list, $L_{\texttt{r}}$. We de­fine the length of every edge in $L_{0}$ as 1. The length of an edge, e, in $L_{\texttt{r}}$, $\texttt{r}>0$, is de­fined as the sum of the lengths of the edges below e in $L_{\texttt{r}-1}$. Equiv­a­lently, the length of e is the num­ber of edges in $L_0$ below e. See Fig­ure 4.5 for an ex­am­ple of a skiplist with the lengths of its edges shown. Since the edges of skiplists are stored in ar­rays, the lengths can be stored the same way:

Fig­ure 4.5 The lengths of the edges in a skiplist.

    class Node {
        T x;
        Node[] next;
        int[] length;
        Node(T ix, int h) {
            x = ix;
            next = (Node[])Array.newInstance(Node.class, h+1);
            length = new int[h+1];
        }
        int height() {
            return next.length - 1;
        }
    }

The use­ful prop­erty of this de­f­i­n­i­tion of length is that, if we are cur­rently at a node that is at po­si­tion j in $L_0$ and we fol­low an edge of length $\ell$, then we move to a node whose po­si­tion, in $L_0$, is $\texttt{j}+\ell$. In this way, while fol­low­ing a search path, we can keep track of the po­si­tion, j, of the cur­rent node in $L_0$. When at a node, u, in $L_{\texttt{r}}$, we go right if j plus the length of the edge u.next[r] is less than i. Oth­er­wise, we go down into $L_{\texttt{r}-1}$.

    Node findPred(int i) {
        Node u = sentinel;
        int r = h;
        int j = -1;   // index of the current node in list 0
        while (r >= 0) {
            while (u.next[r] != null && j + u.length[r] < i) {
                j += u.length[r];
                u = u.next[r];
            }
            r--;
        }
        return u;
    }

    T get(int i) {
        return findPred(i).next[0].x;
    }
    T set(int i, T x) {
        Node u = findPred(i).next[0];
        T y = u.x;
        u.x = x;
        return y;
    }

Since the hard­est part of the op­er­a­tions get(i) and set(i,x) is find­ing the ith node in $L_0$, these op­er­a­tions run in $O(\log \texttt{n})$ time.

Adding an el­e­ment to a SkiplistList at a po­si­tion, i, is fairly sim­ple. Un­like in a SkiplistSSet, we are sure that a new node will ac­tu­ally be added, so we can do the ad­di­tion at the same time as we search for the new node's lo­ca­tion. We first pick the height, k, of the newly in­serted node, w, and then fol­low the search path for i. Any time the search path moves down from $L_{\texttt{r}}$ with $\texttt{r}\le \texttt{k}$, we splice w into $L_{\texttt{r}}$. The only extra care needed is to en­sure that the lengths of edges are up­dated prop­erly. See Fig­ure 4.6.

Fig­ure 4.6 Adding an el­e­ment to a SkiplistList.

Note that, each time the search path goes down at a node, u, in $L_{\texttt{r}}$, the length of the edge u.next[r] in­creases by one, since we are adding an el­e­ment below that edge at po­si­tion i. Splic­ing the node w be­tween two nodes, u and z, works as shown in Fig­ure 4.7. While fol­low­ing the search path we are al­ready keep­ing track of the po­si­tion, j, of u in $L_0$. There­fore, we know that the length of the edge from u to w is $\texttt{i}-\texttt{j}$. We can also de­duce the length of the edge from w to z from the length, $\ell$, of the edge from u to z. There­fore, we can splice in w and up­date the lengths of the edges in con­stant time.

Fig­ure 4.7 Up­dat­ing the lengths of edges while splic­ing a node w into a skiplist.

This sounds more com­pli­cated than it is, for the code is ac­tu­ally quite sim­ple:

    void add(int i, T x) {
        Node w = new Node(x, pickHeight());
        if (w.height() > h) 
            h = w.height();
        add(i, w);
    }

    Node add(int i, Node w) {
        Node u = sentinel;
        int k = w.height();
        int r = h;
        int j = -1; // index of u
        while (r >= 0) {
            while (u.next[r] != null && j+u.length[r] < i) {
                j += u.length[r];
                u = u.next[r];
            }
            u.length[r]++; // accounts for new node in list 0
            if (r <= k) {
                w.next[r] = u.next[r];
                u.next[r] = w;
                w.length[r] = u.length[r] - (i - j);
                u.length[r] = i - j;
            }
            r--;
        }
        n++;
        return u;
    }

By now, the im­ple­men­ta­tion of the remove(i) op­er­a­tion in a SkiplistList should be ob­vi­ous. We fol­low the search path for the node at po­si­tion i. Each time the search path takes a step down from a node, u, at level r we decre­ment the length of the edge leav­ing u at that level. We also check if u.next[r] is the el­e­ment of rank i and, if so, splice it out of the list at that level. An ex­am­ple is shown in Fig­ure 4.8.

Fig­ure 4.8 Re­mov­ing an el­e­ment from a SkiplistList.

    T remove(int i) {
        T x = null;
        Node u = sentinel;
        int r = h;
        int j = -1; // index of node u
        while (r >= 0) {
            while (u.next[r] != null && j+u.length[r] < i) {
                j += u.length[r];
                u = u.next[r];
            }
            u.length[r]--;  // for the node we are removing
            if (j + u.length[r] + 1 == i && u.next[r] != null) {
                x = u.next[r].x;
                u.length[r] += u.next[r].length[r];
                u.next[r] = u.next[r].next[r];
                if (u == sentinel && u.next[r] == null)
                    h--;
            }
            r--;
        }
        n--;
        return x;
    }

4.3.1 Sum­mary

The fol­low­ing the­o­rem sum­ma­rizes the per­for­mance of the SkiplistList data struc­ture:

4.4 Analy­sis of Skiplists

In this sec­tion, we an­a­lyze the ex­pected height, size, and length of the search path in a skiplist. This sec­tion re­quires a back­ground in basic prob­a­bil­ity. Sev­eral proofs are based on the fol­low­ing basic ob­ser­va­tion about coin tosses.

The next two lem­mata tell us that skiplists have lin­ear size:

The fol­low­ing the­o­rem sum­ma­rizes the re­sults in this sec­tion:

4.5 Dis­cus­sion and Ex­er­cises

Skiplists were in­tro­duced by Pugh [62] who also pre­sented a num­ber of ap­pli­ca­tions and ex­ten­sions of skiplists [61]. Since then they have been stud­ied ex­ten­sively. Sev­eral re­searchers have done very pre­cise analy­ses of the ex­pected length and vari­ance of the length of the search path for the ith el­e­ment in a skiplist [45,44,58]. De­ter­min­is­tic ver­sions [53], bi­ased ver­sions [8,26], and self-ad­just­ing ver­sions [12] of skiplists have all been de­vel­oped. Skiplist im­ple­men­ta­tions have been writ­ten for var­i­ous lan­guages and frame­works and have been used in open-source data­base sys­tems [71,63]. A vari­ant of skiplists is used in the HP-UX op­er­at­ing sys­tem ker­nel's process man­age­ment struc­tures [42]. Skiplists are even part of the Java 1.6 API [55].