SkipList.java

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class SkipList {
    private static class SkipListNode {
        private final int value;
        private final SkipListNode[] next;

        public SkipListNode(int value, int level) {
            this.value = value;
            this.next = new SkipListNode[level];
        }
    }

    private final Random random = new Random();
    private SkipListNode head = new SkipListNode(0, 33);
    private int levels = 1;

    void insert(int value) {
        if (contains(value)) {
            return;
        }
        int level = 0;
        for (int r = random.nextInt(); (r & 1) == 1; r >>= 1) {
            level++;
            if (level == levels) {
                levels++;
                break;
            }
        }
        SkipListNode current = head;
        SkipListNode newNode = new SkipListNode(value, level + 1);
        for (int i = levels - 1; i >= 0; i--) {
            while (current.next[i] != null) {
                if (current.next[i].value > value) {
                    break;
                }
                current = current.next[i];
            }

            if (i <= level) {
                newNode.next[i] = current.next[i];
                current.next[i] = newNode;
            }
        }
    }

    boolean contains(int value) {
        SkipListNode current = head;
        for (int i = levels - 1; i >= 0; i--) {
            while (current.next[i] != null) {
                if (current.next[i].value == value) {
                    return true;
                }
                current = current.next[i];
            }
        }
        return false;
    }

    boolean remove(int value) {
        SkipListNode current = head;
        boolean found = false;
        for (int i = levels - 1; i >= 0; i--) {
            while (current.next[i] != null) {
                if (current.next[i].value == value) {
                    current.next[i] = current.next[i].next[i];
                    found = true;
                    break;
                }
                current = current.next[i];
            }
        }
        return found;
    }

    List<Integer> list() {
        SkipListNode current = head.next[0];
        List<Integer> items = new ArrayList<>();
        while (current != null) {
            items.add(current.value);
            current = current.next[0];
        }
        return items;
    }
}