用Java实现自定义SkipList

Question

我最近学习了SkipList，并认为我会自己创建一个。该实现使用一个2层的` `SkipList，其中支持列表的大小大致是原始列表大小的平方根。

package skiplists.skiplist;

public class SkipList<T extends Comparable<T>> {
private SkipNode<T> start;
private SkipNode<T> end;
private SkipNode<T> supportStart;
private SkipNode<T> supportEnd;
private int size;
private int sizeSupport;

public T getStart() {
    return start.getData();
}

public T getEnd() {
    return end.getData();
}

public int getSize() {
    return size;
}

public void add(T data){
    if(start == null){
        insertAsFirstElement(data);
    }
    else{
        insert(data);
    }
}

private void insertAsFirstElement(T data){
    SkipNode<T> node = new SkipNode<>(data);
    start = node;
    end = node;
    size++;

    SkipNode<T> supportNode = new SkipNode<>(data); 
    supportStart = supportNode;
    supportEnd = supportNode;
    supportNode.setDown(node);
    sizeSupport++;
}

//Adding element in the end assuming user enters data in ascending order
private void insert(T data){
    SkipNode<T> node = new SkipNode<>(data);
    end.setNext(node);
    node.setPrevious(end);
    end = node;
    size++;

    int expectedSupportSize = (int) Math.sqrt(size);
    if(sizeSupport < expectedSupportSize){
        SkipNode<T> supportNode = new SkipNode<>(data);
        supportEnd.setNext(supportNode);
        supportNode.setPrevious(supportEnd);
        supportEnd = supportNode;
        supportNode.setDown(node);
        sizeSupport++;

        if(sizeSupport > 2)
        reAjustSupportList();

    }
}

/*readjusting the support list so that they point to the correct nodes when new 
*support nodes are added
*/
private void reAjustSupportList(){
    SkipNode<T> navigationNode = supportStart.getNext();
    int i = 1; 

    while(navigationNode != supportEnd){
        SkipNode<T> tempNode = navigationNode.getDown();
        for(int j = 1 ; j <= i ; j++){
            tempNode = tempNode.getNext();
        }
        navigationNode.setDown(tempNode);
        navigationNode.setData(tempNode.getData());
        navigationNode = navigationNode.getNext();

        i++;
    }
}

public boolean search(T data){
    SkipNode<T> navigationNode = supportStart;

    if(data.compareTo(navigationNode.getData()) < 1){
        return false;
    }

    while(navigationNode != null && navigationNode.getNext() != null && (data.compareTo(navigationNode.getNext().getData()) > 0 || data.compareTo(navigationNode.getData()) == 0)){
                    navigationNode = navigationNode.getNext();
    }

    SkipNode<T> searchNodeStart = navigationNode.getDown();
    SkipNode<T> searchNodeEnd  = navigationNode.getNext().getDown();

    while(searchNodeStart != searchNodeEnd){
        if(searchNodeStart.getData().compareTo(data) == 0){
            return true;
        }
        searchNodeStart = searchNodeStart.getNext();
    }
    return false;
}

private static class SkipNode<T>{

    public SkipNode(T data){
        this.data = data;
    }

    private SkipNode<T> next = null;
    private SkipNode<T> previous = null;
    private SkipNode<T> down = null;
    private T  data;

    public SkipNode<T> getNext() {
        return next;
    }
    public void setNext(SkipNode<T> next) {
        this.next = next;
    }
    public SkipNode<T> getPrevious() {
        return previous;
    }
    public void setPrevious(SkipNode<T> previous) {
        this.previous = previous;
    }
    public SkipNode<T> getDown() {
        return down;
    }
    public void setDown(SkipNode<T> down) {
        this.down = down;
    }
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
}
}

我希望收到关于这段代码的评论(在SkipList和调整机制中搜索的更好方法)。我假设用户按升序输入数字。稍后我将应用一些排序机制，并发布代码。

Answer 1

单元测试

这是一个相当复杂的问题。让单元测试来验证实现是正确的是很好的。下面是一些示例：

public class SkipListTest {
    @Test
    public void test_with_30_50() {
        SkipList<Integer> list = new SkipList<>();
        list.add(30);
        list.add(50);
        assertEquals(2, list.getSize());
        assertEquals(new Integer(30), list.getStart());
        assertEquals(new Integer(50), list.getEnd());
        assertTrue(list.search(30));  // -> false
        assertTrue(list.search(50));  // -> npe
        assertFalse(list.search(51));  // -> npe
        assertFalse(list.search(33));  // -> npe
    }

    @Test
    public void test_with_30_40_50_60_70_80_90() {
        SkipList<Integer> list = new SkipList<>();
        list.add(30);
        list.add(40);
        list.add(50);
        list.add(60);
        list.add(70);
        list.add(80);
        list.add(90);
        assertEquals(7, list.getSize());
        assertEquals(new Integer(30), list.getStart());
        assertEquals(new Integer(90), list.getEnd());
        assertTrue(list.search(30));  // -> false
        assertTrue(list.search(40));
        assertTrue(list.search(50));
        assertTrue(list.search(60));  // -> false
        assertTrue(list.search(70));  // -> npe
        assertTrue(list.search(80));  // -> npe
        assertTrue(list.search(90));  // -> npe
        assertFalse(list.search(33));
        assertFalse(list.search(51));
        assertFalse(list.search(63));  // -> npe
        assertFalse(list.search(133));  // -> npe
    }
}

请注意我在行尾添加注释的测试用例：

• // -> false --这些断言失败，调用不会产生期望值
• // -> npe --这些断言会抛出一个NullPointerException

换句话说，search方法是错误的。

替代实现.search

此实现通过了上述测试：

public boolean search(T data) {
    SkipNode<T> navigationNode = supportStart;
    int compare;

    while ((compare = data.compareTo(navigationNode.getData())) > 0
            && navigationNode.getNext() != null) {
        navigationNode = navigationNode.getNext();
    }

    if (compare == 0) {
        return true;
    }

    if (compare < 0) {
        navigationNode = navigationNode.getPrevious();
    }
    navigationNode = navigationNode.getDown().getNext();

    while ((compare = data.compareTo(navigationNode.getData())) > 0
            && navigationNode.getNext() != null) {
        navigationNode = navigationNode.getNext();
    }
    return compare == 0;
}

这个实现依赖于这样一个事实:类只支持两个层。该算法相对简单：

• 只要节点值小于目标，就在上层迭代。
• 如果找到完全匹配的，请返回
• 如果节点值大于目标值，请退到前一个节点。
• 下台:我们知道这里不应该有NPE，因为我们现在在顶层
• 在较低层中迭代，只要节点值小于目标。
• 如果上次比较相等，则返回true，否则返回false。

注意上下层迭代中的相似之处。只要付出更多的努力，这可能会被推广到支持更多的层。

其他实现说明

此实现仅涵盖跳过列表操作的一小部分：

• 没有实际插入，必须按升序追加项。
• 不删除
• 没有多层次
• 与维基百科解释的概念相去甚远，最值得注意的是没有p因素

命名

有些方法和变量名不是很好。我建议重新命名其中的一些：

• add是很好的，因为它的行为像List.add一样，附在最后
• 而不是insertAsFirstElement，简单的insertFirst怎么样？
• insert确实是不合适的，因为上面的评论说，它在末尾添加了一个元素。所以append会更好。
• sizeSupport不是一个很好的名字，通常最好把size、count、index和num这样的东西作为后缀而不是前缀。还请注意，supportSize将很好地与现有变量supportStart和supportEnd保持一致。

Answer 2

对于数据结构来说，也有一些测试代码是非常好的，只需使用它，显然您可以确保它的工作。而且，SkipList没有实现任何接口，但我确信至少实现List、Iterable会很容易，哦是的，toString也会很好。

无论如何，我将从我注意到的几点开始；总的来说，我认为这看起来不错。

• 格式设置有点错误，但这是复制和粘贴问题；SkipNode在方法之间没有使用相同的空间，两个注释的格式可以更好地格式化。
• 使用<>是很棒的。
• 避免使用Math.sqrt，您可以简单地用平方的sizeSupport进行比较。
• reAjustSupportList缺少一个"d“。
• search中的单条极长的行不太好。或者将每个条件放在一行中，或者在不喜欢的情况下将其移动到一个方法中。

至于算法部分，我想既然你只在结尾加了一点，这就可以了，但据我所知，总的来说，从维基百科还有更多的东西给跳过的人，特别是没有必要重新调整(如果我错了，请纠正我)。

Answer 3

一些小贴士：

1. 您的跳过列表由两个列表组成。因此，使用相同的逻辑搜索两个列表：
   • 从supportStart遍历到supportEnd以获得navigationNode。
   • 从navigationNode.down遍历到navigationNode->next.down以获得搜索的节点(就像您所做的那样)。

2. 空检查://数据可能为空。如果(data.compareTo(navigationNode.getData())< 1){返回false；} // navigationNode.getNext()可能为空。SkipNode searchNodeEnd = navigationNode.getNext().getDown()；

除了这个，search()看起来还不错。