java有跳过列表实现吗

I find ConcurrentSkipListSet http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListSet.html在 Java Collection Framework 中，它是通过跳跃列表进行备份的。但是Java中有跳过列表吗？一组在我的用例中不起作用。我需要一个支持重复项的可索引列表。

这个答案晚了 3 年，但我希望它对那些从现在开始想要 Java 跳过列表的人有用:)

该解决方案允许按照您的要求进行重复。我大致遵循这里的指南http://igoro.com/archive/skip-lists-are-fascinating http://igoro.com/archive/skip-lists-are-fascinating，所以复杂度与此相似，除了delete成本 O(nlogn) - 因为我不费心使用双链接节点，我想这样做会带来delete降至 O(logn)。

代码包括：接口、实现该接口的跳表、节点类。它也是通用的。

您可以调整参数LEVELS为了性能，但请记住时空权衡。

import java.util.Random;

interface SkippableList<T extends Comparable<? super T>> {
    int LEVELS = 5;

    boolean delete(T target);
    void print();
    void insert(T data);
    SkipNode<T> search(T data);
}

public class SkipList<T extends Comparable<? super T>> implements SkippableList<T> {

    public static void main(String[] args) {
        SkipList<Integer> sl = new SkipList<>();
        int[] data = {4,2,7,0,9,1,3,7,3,4,5,6,0,2,8};
        for (int i : data) {
            sl.insert(i);
        }

        sl.print();
        sl.search(4);

        sl.delete(9);
        sl.print();

        sl.insert(69);
        sl.print();
        sl.search(69);
    }

    private final SkipNode<T> head = new SkipNode<>(null);
    private final Random rand = new Random();

    @Override
    public void insert(T data) {
        SkipNode<T> SkipNode = new SkipNode<>(data);
        for (int i = 0; i < LEVELS; i++) {
            if (rand.nextInt((int) Math.pow(2, i)) == 0) { //insert with prob = 1/(2^i)
                insert(SkipNode, i);
            }
        }
    }

    @Override
    public boolean delete(T target) {
        System.out.println("Deleting " + target.toString());
        SkipNode<T> victim = search(target, false);
        if (victim == null) return false;
        victim.data = null;

        for (int i = 0; i < LEVELS; i++) {
            head.refreshAfterDelete(i);
        }

        System.out.println();
        return true;
    }

    @Override
    public SkipNode<T> search(T data) {
        return search(data, true);
    }

    @Override
    public void print() {
        for (int i = 0; i < LEVELS; i++) {
            head.print(i);
        }

        System.out.println();
    }

    private void insert(SkipNode<T> SkipNode, int level) {
        head.insert(SkipNode, level);
    }

    private SkipNode<T> search(T data, boolean print) {
        SkipNode<T> result = null;
        for (int i = LEVELS-1; i >= 0; i--) {
            if ((result = head.search(data, i, print)) != null) {
                if (print) {
                    System.out.println("Found " + data.toString() + " at level " + i + ", so stoppped" );
                    System.out.println();
                }

                break;
            }
        }

        return result;
    }

}

class SkipNode<N extends Comparable<? super N>> {

    N data;
    @SuppressWarnings("unchecked")
    SkipNode<N>[] next = (SkipNode<N>[]) new SkipNode[SkippableList.LEVELS];

    SkipNode(N data) {
        this.data = data;
    }

    void refreshAfterDelete(int level) {
        SkipNode<N> current = this.getNext(level);
        while (current != null && current.getNext(level) != null) {
            if (current.getNext(level).data == null) {
                SkipNode<N> successor = current.getNext(level).getNext(level);
                current.setNext(successor, level);
                return;
            }

            current = current.getNext(level);
        }
    }

    void setNext(SkipNode<N> next, int level) {
        this.next[level] = next;
    }

    SkipNode<N> getNext(int level) {
        return this.next[level];
    }

    SkipNode<N> search(N data, int level, boolean print) {
        if (print) {
            System.out.print("Searching for: " + data + " at ");
            print(level);
        }

        SkipNode<N> result = null;
        SkipNode<N> current = this.getNext(level);
        while (current != null && current.data.compareTo(data) < 1) {
            if (current.data.equals(data)) {
                result = current;
                break;
            }

            current = current.getNext(level);
        }

        return result;
    }

    void insert(SkipNode<N> SkipNode, int level) {
        SkipNode<N> current = this.getNext(level);
        if (current == null) {
            this.setNext(SkipNode, level);
            return;
        }

        if (SkipNode.data.compareTo(current.data) < 1) {
            this.setNext(SkipNode, level);
            SkipNode.setNext(current, level);
            return;
        }

        while (current.getNext(level) != null && current.data.compareTo(SkipNode.data) < 1 && 
                current.getNext(level).data.compareTo(SkipNode.data) < 1) {

            current = current.getNext(level);
        }

        SkipNode<N> successor = current.getNext(level);
        current.setNext(SkipNode, level);
        SkipNode.setNext(successor, level);
    }

    void print(int level) {
        System.out.print("level " + level + ": [");
        int length = 0;
        SkipNode<N> current = this.getNext(level);
        while (current != null) {
            length++;
            System.out.print(current.data.toString() + " ");
            current = current.getNext(level);
        }

        System.out.println("], length: " + length);
    }

}