Introducing the Skip List data structure – Arrays, collections and data structures

113. Introducing the Skip List data structure

The Skip List data structure is a probabilistic data structure built on top of a linked list. A Skip List uses an underlying linked list for keeping a sorted list of items, but it also provides the capability to skip certain items in order to speed up operations such as insert, delete, and find. Its Big O goals are listed in the following figure:

Figure 5.16 – Big (O) for Skip List

A Skip List has two types of layers. The base layer (or the lower layer, or layer 0) consists of a regular linked list that holds the sorted list of all items. The rest of the layers contain sparse items and act as an “express line” meant to speed up the search, insert, and delete items. The following figure helps us to visualize a Skip List with three layers:

Figure 5.17 – Skip List sample

So, this Skip List holds on layer 0 the items 1, 2, 3, 4, 5, 8, 9, 10, 11, and 34 and it has two express lines (layer 1 and layer 2) containing sparse items. Next, let’s see how we can find a certain item.

Implementing contains(Integer data)

Searching certain items starts on layer n, continues layer n-1, and so on until layer 0. For instance, let’s assume that we want to find item 11.We start on layer 2 and continue running on this layer until we find a node >= 11. Since the value 11 doesn’t exist on layer 2, we search for an item less than 11 and we find 10.We get down on layer 1 and continue searching. Based on the same logic we find item 10 again. Layer 1 doesn’t contain item 11 either. If it had contained it then we would have stopped the search.We go down again, this time to layer 0 (the base layer containing all items), and continue searching until we find item 11. The following figure depicts our search path:

Figure 5.18 – Finding an item in a Skip List

By following the highlighted path we can easily notice that we skipped a significant number of items until we found item 11.In code lines, this operation can be implemented as follows:

public boolean contains(Integer data) {
  Node cursorNode = head;
      
  for (int i = topLayer – 1; i >= 0; i–) {
    while (cursorNode.next[i] != null) {
      if (cursorNode.next[i].getData() > data) {
        break;
      }
      if (cursorNode.next[i].getData().equals(data)) {
        return true;
      }
      cursorNode = cursorNode.next[i];
    }
  }
  return false;
}

Next, let’s see how we can insert a new item.

Implementing insert(Integer data)

Inserting a new item takes place on a randomly chosen layer. In other words, the layer of an item is chosen randomly at insertion time. We can insert it on an existing layer or create a new layer, especially for this new item. We can create new layers until we hit an arbitrary chosen MAX_NUMBER_OF_LAYERS (we have MAX_NUMBER_OF_LAYERS = 10).During the insertion algorithm, we follow these steps meant to search for the proper place for the item to insert:

If the item of the next node is less than the item to insert then we continue moving forward on the same layer.

If the item of the next node is greater than the item to insert then we save the pointer to the current node and continue by moving one layer down. The search continues from here.

At some point, we will reach the base layer (Layer 0). Since this layer holds all items, we know for sure that we will find here a slot for the new item.

In the following figure, item 7 was inserted on Layer 1:

Figure 5.19 – Inserting an item in a Skip List

The implementation is straightforward. :

public void insert(Integer data) {
  int layer = incrementLayerNo();
  Node newNode = new Node(data, layer);
  Node cursorNode = head;
  for (int i = topLayer – 1; i >= 0; i–) {
    while (cursorNode.next[i] != null) {
      if (cursorNode.next[i].getData() > data) {
        break;
      }
      cursorNode = cursorNode.next[i];
    }
    if (i <= layer) {
      newNode.next[i] = cursorNode.next[i];
      cursorNode.next[i] = newNode;
    }
  }
  size++;
}

The incrementLayerNo() is a method that randomly decides the layer on which the new item will be inserted.

Implementing delete(Integer data)

Deleting an item is a simple operation. We start from the top layer, find the item to delete, and delete it. The acceptable challenge is to pay attention to eliminating the item by correctly linking the remaining nodes. The implementation is simple:

public boolean delete(Integer data) {
  Node cursorNode = head;
  boolean deleted = false;
      
  for (int i = topLayer – 1; i >= 0; i–) {
    while (cursorNode.next[i] != null) {
      if (cursorNode.next[i].getData() > data) {
        break;
      }
      if (cursorNode.next[i].getData().equals(data)) {                  
        cursorNode.next[i] = cursorNode.next[i].next[i];
        deleted = true;
        size–;
        break;
      }
      cursorNode = cursorNode.next[i];
    }
  }
  return deleted;
}

Challenge yourself to implement a Skip List on top of the Java built-in LinkedList. It will be fun and give you the chance to explore the Skip List data structure a step further.