Skip Lists in Java: The Probabilistic Alternative to Balanced Trees

A Skip List is a probabilistic data structure that allows for fast search, insertion, and deletion in a sorted list of elements. It is often described as a "multi-layered linked list."

While balanced trees like AVL or Red-Black trees use complex rotations to maintain $O(\log N)$ performance, Skip Lists use randomness to achieve the same result with much simpler code.

The Core Concept: Layers of "Express Lanes"

Imagine a standard sorted linked list. To find an element, you must traverse it linearly. A Skip List adds multiple layers of linked lists:

1. Layer 0: The base layer containing all elements.
2. Layer 1: A "skip" layer containing roughly half the elements.
3. Layer 2: A "skip" layer containing roughly a quarter of the elements.
4. Layer $h$: The top layer containing very few elements.

To search, you start at the top layer and move right as long as the next element is smaller than your target. If it's larger, you drop down to the next layer and repeat.

Skip List Implementation in Java (Simplified)

import java.util.Random;

class Node {
    int value;
    Node[] next; // Array of pointers for each level

    Node(int value, int level) {
        this.value = value;
        this.next = new Node[level + 1];
    }
}

public class SkipList {
    private static final int MAX_LEVEL = 16;
    private int currentLevel = 0;
    private Node head = new Node(-1, MAX_LEVEL);
    private Random random = new Random();

    // Probabilistically determine the level for a new node
    private int randomLevel() {
        int level = 0;
        while (random.nextFloat() < 0.5 && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

    public void insert(int value) {
        Node[] update = new Node[MAX_LEVEL + 1];
        Node curr = head;

        // Find the insertion point at each level
        for (int i = currentLevel; i >= 0; i--) {
            while (curr.next[i] != null && curr.next[i].value < value) {
                curr = curr.next[i];
            }
            update[i] = curr;
        }

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

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

    public boolean search(int value) {
        Node curr = head;
        for (int i = currentLevel; i >= 0; i--) {
            while (curr.next[i] != null && curr.next[i].value < value) {
                curr = curr.next[i];
            }
        }
        curr = curr.next[0];
        return curr != null && curr.value == value;
    }
}

Skip List vs. Balanced Trees

Real-World Applications

1. Redis: The Sorted Set (ZSET) in Redis is implemented using a Skip List.
2. Lucene: The indexing engine behind Elasticsearch uses Skip Lists for efficient term lookups.
3. LevelDB: Google's key-value store uses Skip Lists in its MemTable.

Summary

Skip Lists are a brilliant example of how randomness can simplify complex problems. By trading a small amount of memory for a much simpler implementation, they provide a robust alternative to balanced trees. If you're building a high-concurrency system or need a sorted structure that's easy to debug, the Skip List is a tool you should definitely have in your arsenal.