Skip list (Java)

From LiteratePrograms

Other implementations: C | C++ | Java

This article describes an implementation of the skip list data structure written in Java.

Traditionally balanced trees have been used to efficiently implement Set and HashMap style data structures. Balanced tree algorithms are characterized by the need to continually rebalance the tree as operations are performed. This is necessary in order to assure good performance.

Skip Lists are a data structure that was developed by William Pugh as a probabilistic alternative to balanced trees. The balancing of a Skip List is achieved through the use of a random number generator.

The benefit of the Skip List is that the algorithms for search, insertion and deletion are rather simple. This provides improved constant time overhead as compared to balanced trees. The algorithms involved are also relatively easy to understand.

In a singly linked list each node contains one pointer to the next node in the list. A node in a Skip List contains an array of pointers. The size of this array is chosen at random (between 0 and some MAX_LEVEL) at the time when the node is created. The size of this array determines the level of the node. For example, a level 3 node has 4 forward pointers, indexed from 0 to 3. The pointer at index 0 (called the level 0 forward pointer) always points to the immediate next node in the list. The other pointers however point to nodes further down the list, and as such if followed allow portions of the list to be skipped over. A level i pointer points to the next node in the list that has level >= i.

What follows is an implementation of a (sorted) Set data structure based on Skip Lists, written in Java.

<<SkipSet.java>>=
SkipNode class
SkipSet class

Contents 1 Random Levels 2 Structure Definitions 3 Printing a SkipSet 4 Search Algorithm 5 Insert Algorithm 6 Delete Algorithm 7 Main function

Random Levels

Before getting to the main algorithms it is a good idea to tackle the problem of generating random levels for nodes. Each node that is created will have a random level between 0 and MAX_LEVEL inclusive.

The desired function will return a random level between 0 and MAX_LEVEL. A probability distribution where half of the nodes that have level i pointers also have level i+1 pointers is used. This gives us a 50% chance of the random_level() function returning 0, a 25% chance of returning 1, a 12.5% chance of returning 2 and so on.

<<Defines>>=
public static final double P = 0.5;

<<Random Level Function>>=
public static int randomLevel() {
    int lvl = (int)(Math.log(1.-Math.random())/Math.log(1.-P));
    return Math.min(lvl, MAX_LEVEL);
} 

Structure Definitions

Each element in the list is stored in a node. The level of the node is chosen randomly when the node is created. Each SkipNode stores an array of forward pointers as well as a value which represents the element stored in the node. The type of this element can be any class type which implements the Comparable interface, because we will need to order them later.

The maximum level index is 6. Java arrays are indexed starting at 0, therefore each node will have between one and seven forward pointers.

<<Defines>>=
public static final int MAX_LEVEL = 6;

<<SkipNode class>>=
class SkipNode<E extends Comparable<? super E>>
{
    public final E value;
    public final SkipNode<E>[] forward; // array of pointers
    SkipNode Constructor
}

To create a SkipNode we must first allocate memory for the node itself then allocate memory for the array of forward pointers.

The implementation of skip lists given by William Pugh states that the list should be terminated by a special NIL node that stores a value greater than any legal value. This stipulation was made so that the algorithms described in his paper would be very simple as they never had to explicitly check for pointers pointing at NIL. I will instead set the initial value of all pointer fields to null.

A level 0 node will have one forward pointer, a level 1 node will have two forward pointers and so on. Therefore we need to add one to the level when allocating memory for the array of forward pointers.

<<SkipNode Constructor>>=
@SuppressWarnings("unchecked")
public SkipNode(int level, E value) 
{
    forward = new SkipNode[level + 1];
    this.value = value;
}

A structure that represents a SkipSet is defined. It stores a pointer to a header node. The value stored in the header node is irrelevant and is never accessed. The current level of the set is also stored as this is needed by the insert, delete and search algorithms.

To create a SkipSet we must first allocate memory for the structure and then allocate memory for the header node. The initial level of the set is 0 because Java arrays are indexed starting at 0.

<<SkipSet class>>=
public class SkipSet<E extends Comparable<? super E>>
{
    Defines
    Random Level Function
    public final SkipNode<E> header = new SkipNode<E>(MAX_LEVEL, null);
    public int level = 0;
    Print Function
    Search Function
    Insert Function
    Delete Function
    Main Function
}

Printing a SkipSet

Before getting to the algorithms for insert, delete and search, let us first start off with a function that will print the contents of a skip set to a string. This function simply traverses the level 0 pointers and visits every node while printing out the values.

<<Print Function>>=
public String toString()
{
    StringBuilder sb = new StringBuilder();
    sb.append("{");
    SkipNode<E> x = header.forward[0];
    while (x != null) {
        sb.append(x.value);
        x = x.forward[0];
        if (x != null)
            sb.append(",");
    }    
    sb.append("}");
    return sb.toString();
}

Search Algorithm

The search algorithm will return true if the given value is stored in the set, otherwise false.

The pointer x is set to the header node of the list. The search begins at the topmost pointer of the header node according to the current level of the list. The forward pointers at this level are traversed until either a NULL pointer is encountered or a value greater than the value being searched for is encountered. When this occurs we attempt to continue the search at the next lower level until we have traversed as far as possible. At this point x will point at the node with the greatest value that is less than the value being searched for. In the case that the search value is less than any value in the list, or if the list is empty, then x will still be pointing at the header node.

Finally the level 0 pointer is traversed once. So now there are three possibilities for x.

• x is pointing at the node with the value we are searching for.
• x is pointing at a node with value greater than the value we are searching for.
• x is null.

In the first case the search was successful.

<<Find Node>>=
for (int i = level; i >= 0; i--) {
    while (x.forward[i] != null && x.forward[i].value.compareTo(searchValue) < 0) {
        x = x.forward[i];
    }
}
x = x.forward[0];

<<Search Function>>=
public boolean contains(E searchValue)
{
    SkipNode<E> x = header;
    Find Node
    return x != null && x.value.equals(searchValue);
}

Insert Algorithm

To insert a value we first perform the same kind of search as in the search algorithm. But, in order to insert a new node into the list we must maintain an array of pointers to the nodes that must be updated.

<<Find and record updates>>=
for (int i = level; i >= 0; i--) {
    while (x.forward[i] != null && x.forward[i].value.compareTo(value) < 0) {
        x = x.forward[i];
    }
    update[i] = x; 
}
x = x.forward[0];

If a node is found with the same value as the value that is to be inserted then nothing should be done (a mathematical set cannot contain duplicates). Otherwise we must create a new node and insert it into the list.

<<Insert Function>>=
@SuppressWarnings("unchecked")
public void insert(E value)
{
    SkipNode<E> x = header;	
    SkipNode<E>[] update = new SkipNode[MAX_LEVEL + 1];
    Find and record updates
    if (x == null || !x.value.equals(value)) {        
        int lvl = randomLevel();
        Record header updates
        Insert new node
    }
}

If the new node is greater than any node already in the list then the header node must be updated and the level of the list must be set to the new level.

<<Record header updates>>=
if (lvl > level) {
    for (int i = level + 1; i <= lvl; i++) {
        update[i] = header;
    }
    level = lvl;
}

Two things must be done to insert the node. We must make the new node x point at what the nodes in the update vector are currently pointing at. Then we update the nodes in the |update| vector to point at x.

<<Insert new node>>=
x = new SkipNode<E>(lvl, value);
for (int i = 0; i <= lvl; i++) {
    x.forward[i] = update[i].forward[i];
    update[i].forward[i] = x;
}

Delete Algorithm

The deletion algorithm starts the same way as the insertion algorithm. We declare an update array and then search for the node to be deleted. If the node is found we set the nodes in the update array to point at what |x| is pointing at. This effectively removes x from the list and so the memory occupied by the node may be freed.

<<Delete Function>>=
@SuppressWarnings("unchecked")
public void delete(E value)
{
    SkipNode<E> x = header;	
    SkipNode<E>[] update = new SkipNode[MAX_LEVEL + 1];
    Find and record updates
    if (x.value.equals(value)) {
        Remove x from list
        Decrease list level
    }
}

<<Remove x from list>>=
for (int i = 0; i <= level; i++) {
    if (update[i].forward[i] != x)
        break;
    update[i].forward[i] = x.forward[i];
}

After deleting the node we must check to see if the level of the list must be lowered.

<<Decrease list level>>=
while (level > 0 && header.forward[level] == null) {
    level--;
}

Main function

For simple illustration purposes we create a SkipSet and perform some tests.

<<Main Function>>=
public static void main(String[] args) {
    SkipSet<Integer> ss = new SkipSet<Integer>();
    System.out.println(ss);
    ss.insert(5);
    ss.insert(10);
    ss.insert(7);
    ss.insert(7);
    ss.insert(6);
    if (ss.contains(7)) {
        System.out.println("7 is in the list");
    }
    System.out.println(ss);
    ss.delete(7);
    System.out.println(ss);
    if (!ss.contains(7)) {
        System.out.println("7 has been deleted");
    }
}

Download code