10.7* Skip lists

A skip list is not a tree, or at least not the kind of tree that we have talked about previously. It can be thought of as a very specialised implementation of a general (nonbinary) tree, but it is more common to think of it as a collection of linked lists.

At the lowest level it is a standard sorted linked list. Then there is a sparser linked list, containing only approximately half of the nodes (meaning that the rest of the nodes are skipped). And then there is an even sparser list, including only one quarter of the nodes. This continues so that we have a logarithmic number of sparser and sparser linked lists.

When searching for a value in a skip list, we can use the sparser linked lists to quickly jump over uninteresting nodes. Inserting a value is done using randomness, where we roll a die to decide how many of the lists should contain the new value. This makes skip lists a randomised data structure, which means that we cannot guarantee that the operations are efficient, but we can say that they are logarithmic with extremely high probability. Therefore, the expected worst-case complexity of skip lists are logarithmic, O(\log(n)).

This section presents a probabilistic search structure called the skip list. Like the BST, skip lists are designed to overcome a basic limitation of array-based and linked lists: Either search or update operations require linear time. The skip list is an example of a probabilistic data structure, because it makes some of its decisions at random.

Skip lists provide an alternative to the BST and related tree structures. The primary problem with the BST is that it may easily become unbalanced. The 2-3 Tree is guaranteed to remain balanced regardless of the order in which data values are inserted, but it is rather complicated to implement. The AVL tree and the splay tree are also guaranteed to provide good performance, but at the cost of added complexity as compared to the BST. The skip list is easier to implement than known balanced tree structures. The skip list is not guaranteed to provide good performance (where good performance is defined as O(\log(n)) search, insertion, and deletion time), but it will provide good performance with extremely high probability (unlike the BST which has a good chance of performing poorly). As such it represents a good compromise between difficulty of implementation and performance.

We can continue adding pointers to selected nodes in this way – give a third pointer to every fourth node, give a fourth pointer to every eighth node, and so on – until we reach the ultimate of \log(n) pointers in the first and middle nodes for a list of n nodes. To search, start with the bottom row of pointers, going as far as possible and skipping many nodes at a time. Then, shift up to shorter and shorter steps as required. With this arrangement, the worst-case number of accesses is O(\log(n)).

We will store with each skip list node an array named forward that stores the pointers. Position forward[0] stores a level 0 pointer, forward[1] stores a level 1 pointer, and so on:

datatype SkipNode:
    value
    level: Int
    forward = new Array(level + 1) of SkipNodes

The skip list object includes data member level that stores the highest level for any node currently in the skip list. The skip list stores a header node named head with level+1 pointers where the head level is initially 0 and the level is set to -1 for the empty list. The start of the SkipList class follows:

datatype SkipList:
    head = new SkipNode(null, null, 0)
    size = 0
    level = -1

The contains operation works as follows.

contains(skiplist, key):
    x = skiplist.head  // Dummy header node
    for i in skiplist.level, skiplist.level-1 .. 0:  // For each level...
        while x.forward[i] is not null and key > x.forward[i].key:  // ...go forward
            x = x.forward[i]  // Go one last step
    x = x.forward[0]  // Move to actual record, if it exists
    if x is not null and key == x.key:
        return true  // Got it
    else:
        return false  // It's not there

The ideal skip list is organised so that (if the head node is not counted) half of the nodes have only one pointer, one quarter have two, one eighth have three, and so on. And ideally, the distances would be equally spaced; in effect this is a “perfectly balanced” skip list. Maintaining such balance would be expensive during the normal process of insertions and deletions. The key to skip lists is that we do not worry about any of this. Whenever inserting a node, we assign it a level (that is, some number of pointers). The assignment is random, using a geometric distribution yielding a 50% probability that the node will have one pointer, a 25% probability that it will have two, and so on. The following function determines the level based on such a distribution.

randomLevel():
    level = 0
    while random() < 0.5:
        level += 1
    return level

Once the proper level for the node has been determined, the next step is to find where the node should be inserted and link it in as appropriate at all of its levels. Here is an implementation for inserting a new value into the skip list followed by a visualisation of the process. Note that we build an update array as we progress through the skip list, so that we can update the pointers for the nodes that will precede the one being inserted.

put(skiplist, key, value):
    newLevel = randomLevel()            // New node's level
    if newLevel > skiplist.level:       // If new node is deeper...
        adjustHead(skiplist, newLevel)  // ...adjust the header
    // Track end of level:
    update = new Array(skiplist.level + 1)
    x = skiplist.head                   // Start at header node
    for i in skiplist.level .. 1, 0:    // Find insert position
        while x.forward[i] is not null and key > x.forward[i].key:
            x = x.forward[i]
        update[i] = x     // Track end at level i
    x = x.forward[0]      // Move to actual record, if it exists
    if x is not null and key == x.key:
        x.value = value   // The key exists: update the value
    else:
        // Otherwise, create a new node and insert it into place:
        y = new SkipNode(key, value, newLevel)
        for i in 0 .. newLevel:  // Splice into list
            y.forward[i] = update[i].forward[i]  // Who y points to
            update[i].forward[i] = y  // Who points to y
        size += 1

adjustHead(skiplist, newLevel):
    temp = skiplist.head
    skiplist.head = new SkipNode(null, null, newLevel)
    for i in 0 .. skiplist.level:
        skiplist.head.forward[i] = temp.forward[i]
    skiplist.level = newLevel

The remove function is similar to insertion in that the update array is built as part of searching for the record to be deleted. Then those nodes specified by the update array have their forward pointers adjusted to point around the node being deleted.

A newly inserted node could have a high level generated by randomLevel, or a low level. It is possible that many nodes in the skip list could have many pointers, leading to unnecessary insert cost and yielding poor (that is, O(n)) performance during search, because not many nodes will be skipped. Conversely, too many nodes could have a low level. In the worst case, all nodes could be at level 0, equivalent to a regular linked list. If so, search will again require O(n) time. However, the probability that performance will be poor is quite low. There is only one chance in 1024 that ten nodes in a row will be at level 0. The motto of probabilistic data structures such as the skip list is “Don’t worry, be happy”. We simply accept the results of randomLevel and expect that probability will eventually work in our favour. The advantage of this approach is that the algorithms are simple, while requiring only O(\log(n)) time for all operations in the average case. For a skip list of size n, the expected memory usage is 2n. This is because a level l node needs l+1 forward pointers, but occurs with probability 2^{(l+1)}. So a skip list is expected to have \sum_{l=0}^{l=\infty} (l+1)/2^{(l+1)} pointers, which is 2. Thus, the number of pointers needed by both the BST and the skip list are expected to be the same.

In practice, the skip list will probably have better performance than a BST storing the same data. The BST can have bad performance caused by the order in which data are inserted. For example, if n nodes are inserted into a BST in increasing order of their key values, then the BST will look like a linked list with the deepest node at depth n-1. If the data inserted over the life of the BST could be randomly ordered, then the probability distribution for the cost of the insert and search operations would be similar to that of the skip list. The problem for the BST is that this randomisation does not happen in fact, but rather the BST is constrained by the actual order of inputs and searches.

In contrast, the skip list’s performance does not depend on the order in which values are inserted into the list. In a sense, the data are “randomised” automatically as part of the skip list’s probabilistic behaviour when the depths of the nodes are selected. As the number of nodes in the skip list increases, the probability of encountering the worst case decreases geometrically. Thus, the skip list illustrates a tension between the theoretical worst case (in this case, O(n) for a skip list operation), and a rapidly increasing probability of average-case performance of O(\log(n)), that characterises probabilistic data structures.