SkipList Implementation in Java

1. Overview

In this article, we’ll explore the fundamentals of the SkipList data structure and walk through a Java implementation. SkipLists are versatile and can be applied to various domains and problems due to their efficient search, insert, and delete operations and relatively straightforward implementation compared to more complex data structures like balanced trees.

2. What Is a SkipList?

A SkipList data structure allows fast search, insert, and delete operations. It achieves this by maintaining several layers of sorted linked lists. The bottom layer contains all the elements in the list, while each successive layer acts as an “express lane”, containing shortcuts for a subset of the elements below it.

These express lanes allow SkipLists to achieve faster search times by jumping over several elements in a single step.

3. Basic Concepts

• Levels: A SkipList consists of several levels. The bottom level (level 0) is a regular linked list of all elements. Each higher level acts as an “express lane”, containing fewer elements and skipping over multiple elements in the lower levels.
• Probability and height: The number of levels at which an element appears is determined probabilistically.
• Head pointers: Each level has a head pointer that points to the first element of that level, facilitating fast access to each level’s elements.

4. Java Implementation

For our Java implementation, we’ll focus on a simplified version of a SkipList that supports basic operations: search, insert, and delete. We’ll use a fixed maximum number of levels for simplicity, although we can adjust this dynamically based on the size of the list.

4.1. Defining the Node Class

First, let’s define a Node class representing an element in the SkipList. Each node will contain a value and an array of pointers to the next node at each level.

class Node {
    int value;
    Node[] forward; // array to hold references to different levels

    public Node(int value, int level) {
        this.value = value;
        this.forward = new Node[level + 1]; // level + 1 because level is 0-based
    }
}

4.2. The SkipList Class

Then, we need to create the SkipList class to manage the nodes and levels:

public class SkipList {
    private Node head;
    private int maxLevel;
    private int level;
    private Random random;

    public SkipList() {
        maxLevel = 16; // maximum number of levels
        level = 0; // current level of SkipList
        head = new Node(Integer.MIN_VALUE, maxLevel);
        random = new Random();
    }
}

4.3. Insert Operation

Now, let’s add an insert method to our SkipList class. This method will insert a new element into the SkipList, ensuring the structure remains efficient:

public void insert(int value) {
    Node[] update = new Node[maxLevel + 1];
    Node current = this.head;

    for (int i = level; i >= 0; i--) {
        while (current.forward[i] != null && current.forward[i].value < value) {
            current = current.forward[i];
        }
        update[i] = current;
    }

    current = current.forward[0];

    if (current == null || current.value != value) {
        int lvl = randomLevel();

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

        Node newNode = new Node(value, lvl);
        for (int i = 0; i <= lvl; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }
}

4.4. Search Operation

The search method traverses the SkipList from the top level down to level 0, moving forward at each level as long as the next node’s value is less than the search value:

public boolean search(int value) {
    Node current = this.head;
    for (int i = level; i >= 0; i--) {
        while (current.forward[i] != null && current.forward[i].value < value) {
            current = current.forward[i];
        }
    }
    current = current.forward[0];
    return current != null && current.value == value;
}

4.5. Delete Operation

Finally, the delete operation removes a value from the SkipList if it exists. Similar to insert, it also needs to update the forward references of the preceding nodes at all levels where the deleted node was present:

public void delete(int value) {
    Node[] update = new Node[maxLevel + 1];
    Node current = this.head;

    for (int i = level; i >= 0; i--) {
        while (current.forward[i] != null && current.forward[i].value < value) {
            current = current.forward[i];
        }
        update[i] = current;
    }
    current = current.forward[0];

    if (current != null && current.value == value) {
        for (int i = 0; i <= level; i++) {
            if (update[i].forward[i] != current) break;
            update[i].forward[i] = current.forward[i];
        }

        while (level > 0 && head.forward[level] == null) {
            level--;
        }
    }
}

5. Time Complexity

The beauty of SkipLists lies in their efficiency:

• Search, insert, and delete operations have an average time complexity of O(log n), where n is the number of elements in the list.
• The space complexity is O(n), considering additional pointers at multiple levels for each element.

6. Advantages

SkipLists come with their own set of advantages and disadvantages, of course. Let’s explore the advantages first:

• The simplicity of implementation: Compared to balanced trees like AVL or Red-Black trees, SkipLists are easier to implement and still provide similar average-case performance for search, insertion, and deletion operations.
• Efficient operations: SkipLists offer efficient average-case time complexities of O(log n) for search, insert, and delete operations.
• Probabilistic balancing: Instead of strict rebalancing rules (as in AVL trees or Red-Black trees), SkipLists use a probabilistic method to maintain balance. This randomization often leads to more evenly balanced structures without the need for complex rebalancing code.
• Concurrency: SkipLists can be more amenable to concurrent access/modification. Lock-free and fine-grained locking strategies are easier to implement in SkipLists, making them suitable for concurrent applications.

7. Disadvantages

Now, let’s look at some of their disadvantages:

• Space overhead: Each node stores multiple forward pointers to other nodes, leading to higher space consumption than a singly-linked list or a binary tree.
• Randomization: While beneficial for balance and simplicity, the probabilistic approach introduces randomness into the structure’s performance. The performance can vary slightly between runs, unlike with deterministic data structures.

8. Conclusion

SkipLists offer a compelling alternative to more traditional balanced tree structures, with their probabilistic approach providing both efficiency and simplicity. Our Java implementation offers a solid foundation for understanding how SkipLists work.