Java：当我用头伪节点插入到我的循环双链表中时，我的伪节点会被打乱。为什么？

Question

我写了一个循环双链接列表，前面有一个虚拟节点。在初始化DLL类的过程中，我创建了虚拟节点。当我在jGrasp中使用调试器并使用可视化工具时，在插入几个数字后，我的虚拟节点会四处移动，不会停留在最前面。我不明白我是如何修改我的链表的。作为前言，我的节点类有一个整数val和两个名为prev和next的指针。我注意到的一件事是，在赋值语句curr=dummy之后，dummy节点被洗牌到上一次插入的curr。

public class DLL {

    Node curr;
    Node help;
    Node dummy = new Node(null, null, -1);

    public DLL() {
        this.curr = curr;
        this.help = help;
        dummy.next = dummy;
        dummy.prev = dummy;
    }

    public boolean isEmpty() {
        if (dummy.next == dummy && dummy.prev == dummy) {
            return true;
        }
        return false;
    }

    public void push(int elem) {
        if (isEmpty()) {
            Node sec = new Node(dummy, dummy, elem);
            dummy.next = sec;
            dummy.prev = sec;
        } else {
            curr = dummy;
            while (curr.next != dummy) {
                curr = curr.next;
            }
            Node n = new Node(curr, dummy, elem);
            curr.next = n;
            dummy.prev = n;
        }
    }

    public void reverse() {
        curr = dummy;
        help = dummy;
        while (curr.next != help || curr != help) {
            curr = curr.next; // increment curr
            help = help.prev; // decrement help    
            swap(curr, help); // swap
        }
    }
    public void swap(Node curr, Node help) {
        int temp = curr.val;
        curr.val = help.val;
        help.val = temp;
    }
    public boolean contains(int elem) {
        curr = dummy.next;
        while (curr != dummy && elem != curr.val) {
            curr = curr.next;
            if (curr == dummy) {
                return false;
            }
        }

        return true;
    }
}

以下是我使用的小测试类：

public class testDLL {
    public static void main(String[] args) {
        DLL dlink = new DLL();
        dlink.push(4);
        dlink.push(6);
        dlink.push(3);
        dlink.push(2);
        assert dlink.contains(4) == true;
        assert dlink.contains(6) == true;
        assert dlink.contains(3) == true;
        assert dlink.contains(2) == true;
        dlink.reverse();

    }
}

Answer 1

我相信我已经解决了这个问题。我没有设置curr=dummy，而是设置curr=head。在DLL顶部初始化dummy之后，我立即设置head=dummy。这样我就不会在前进中改变头部。

Answer 2

欢迎来到SO。我将建议你如何自己解决问题，而不是为你找出问题所在。

您的测试试图一次测试太多。为了让您的测试工作，所有的方法都需要工作。更好的是（尽可能地）孤立地测试每个方法，然后构建以测试更复杂的场景。

所以先试着让这个测试起作用：

DLL list = new DLL();
assertTrue(list.isEmpty());

然后呢

DLL list = new DLL();
list.push(5);
assertTrue(list.contains(5));

很快，你就会发现你需要一种方法来获取不同格式的列表，以便进行测试。这很典型。

DLL list = new DLL();
list.push(5);
list.push(7);
list.push(5);
assertEquals(list.asList(), List.of(5, 7, 5));

DLL list = new DLL();
list.push(5);
list.push(7);
list.reverse();
assertEquals(list.asList(), List.of(7, 5));

等等

这样，在继续之前，您可以检查每个方法是否适用于基本值。

现在有几个设计要点：使用虚拟节点存储头部和尾部是不寻常的。很容易搞乱价值观（就像你所做的那样）。更好的方法是将头部和尾部存储为单独的变量，如果列表为空并指向单个项目的同一个节点，则这些变量为null（或者更好的方法是可选。empty）。