Java中的SkipList实现

Question

代码运行良好，但可能会更好。我该如何改进呢？

维基百科：

跳过列表是一种数据结构，允许在有序的元素序列中快速搜索。通过维护链接的子序列层次结构，快速搜索成为可能，每一个连续的子序列跳过的元素比前一个少。搜索从最稀疏的子序列开始，直到找到两个连续的元素，一个较小，一个大于或等于所搜索的元素。通过链接的层次结构，这两个元素链接到下一个最稀疏子序列的元素，其中搜索将继续，直到最后我们以完整的顺序进行搜索。

public class SkipList<T extends Comparable<T>>{

int maxLevels;
Random rand = new Random();
Node first;
int size;

public SkipList(int listLevels){
    this.maxLevels = listLevels;

    first = new Node(null);
    Node d = new Node(null);
    first.down = d;

    for(int j = listLevels - 2; j >= 0; j--){

        d.down = new Node(null);
        d = d.down;
    }
}

/*
 *Makes a new Node containing data and links the node to the node 
 *previous and after on all levels from the nodes height and below.
 */

public void insert(T data){

    int levels = setHeight();
    Node newNode = new Node(data);
    Node node = first;

    for(int i = maxLevels; i > levels; i--){
        node = node.down;
    }

    for(int i = levels; i >= 1; i--){

        Node previous = findPreviousNodeOnLevel(data, node);
        newNode.next = previous.next;
        previous.next = newNode;

        if(i > 1){
            newNode.down = new Node(data);
            newNode = newNode.down;
            node = previous.down;
            }
    }
    size++;
}

/*
 * Gives a random number between 1 and maxLevels 
 */
private int setHeight(){
    int n = 0;
    int level = 0;
    while( n != 1 && level < maxLevels){
        n = rand.nextInt(2) + 1;
        level ++;
    }
    return level;
}

/*
 * Finds @param data in the list
 */
public T get(T data){
    Node node = getPreviousNode(data);
    if(node == null || node.next == null || node.next.data == null){
        return null;
    }
    return getPreviousNode(data).next.data;
}

/*
 * Removes @param data from the list
 */

public boolean remove(T data){
    Node previous = getPreviousNode(data);
    if(previous.next != null){
        Node toRemove = previous.next;
        previous.next = toRemove.next;

        while(toRemove.down != null){
            toRemove = toRemove.down;
            previous = findPreviousNodeOnLevel(data, previous.down);
            previous.next = toRemove.next;
        }

        return true;
    }

    return false;
}

/*
 * Returns the node that is before @param data in the list.
 */
private Node getPreviousNode(T data){
    Node previous = findPreviousNodeOnLevel(data, first);

    while(true){
        if(previous.next != null && previous.next.data.equals(data)){
            return previous;
        }

        if(previous.down != null){
        previous = previous.down;
        previous = findPreviousNodeOnLevel(data, previous);
        }
        else{
            return null;
        }
    }
}

/*
 * Returns the node before @param data at the same height/level as @param current
 */
private Node findPreviousNodeOnLevel(T data, Node current){

    while(current.next != null && current.next.data.compareTo(data) < 0){  
        current = current.next;
    }
    return current;
}


public int getSize(){
    return size;
}

private class Node {

    T data;
    Node next;
    Node down;

    Node(T data){
        this.data = data;
    }
}

}

Answer 1

跳过列表的目标是通过执行如下循环来完成查找：

Node find(T value){
    Node start = root;

    while(start!=null && comp(start.value, value) != 0){

        if(comp(start.next.value, value) < 0){
            start = start.next;
        }else{
            start = start.down;
        }

    }
    return start;
}

注意comp助手函数。我补充说，这样您就可以轻松地使用在构建过程中传入的自定义Comparable<T>。

如果您想插入/删除一个值，可以很容易地展开它以保留要更新的节点列表：

List<Node> findAllPrevs(T value){
    List<Node> prevs = new ArrayList<>();
    Node start = root;

    while(start!=null){

        if(comp(start.next.value, value) < 0){
            start = start.next;
        }else{
            prevs.add(start);
            start = start.down;
        }

    }
    while(prevs.get(prevs.size()-1).down!=null){
        prevs.add(prevs.get(prevs.size()-1).down);
    }
    return prevs;
}

然后，您只需要在添加或删除值时更新prevs中的最后一个depth节点。