Java——双向链表逻辑

Question

我试图理解一个Java实现的双向链表。我有以下代码：

public class DLLNode{
    //define variables
    public int info;
    public DLLNode next;
    public DLLNode prev;


    //Passing constructors
    public DLLNode(int i){
        info = i;
        next = prev = null;
    }

    public DLLNode(int i, DLLNode n, DLLNode p){
        info = i;
        next = n;
        prev = p;
    }
}

还有以下内容：

public class DLL {
    DLLNode head;
    DLLNode tail;

    public DLL(){
        head = tail = null;
    }

    //Check whether list is empty or not
    public boolean isEmpty(){
        return head == null;
    }

//Insert element to head
    public void insertHead(int n){
        if(isEmpty()){
            head = tail = new DLLNode(n);
        }
        else{
            head = new DLLNode(n, null, head);
            head.next.prev = head;
        }
    }

为了清晰起见，这里只展示了insertHead()方法。

现在我明白了，如果有人在主方法中运行insertHead(10)，如果列表为空，则会形成一个新对象，并且head和tail引用变量都指向该对象。

但是，如果列表不为空，这段代码非常令人困惑，我不明白其中的含义。

head = new DLLNode(n, null, head);
head.next.prev = head; //really confusing, what does this mean??

1) 我的理解是 n=10, null 和 head 被传递到构造函数: public DLLNode(int i, DLLNode n, DLLNode p)。然后进行了赋值 info=10, next=null 和 prev=head。一个问题是，如果列表上至少有一个项目，并且我将另一个项目添加到 HEAD 位置，"next" 应该指向前一个 head，而 "prev" 应该指向 null 吗？可能是错误的代码吗？

2) 代码段

head.next.prev = head;

mean是什么？为什么需要它？我真的不理解这个逻辑...:(

任何帮助都将不胜感激。

- user3889963

---

看起来你是对的，应该是 new DLLNode(n, head, null) 而不是其他。你试过运行它了吗？ - RealSkeptic

它肯定会编译通过，但方法名使用的逻辑很令人困惑。这就是我担心的，我害怕自己错过了一些微不足道的东西。 - user3889963

编译没问题，但是对于多个元素运行就不行了。这种情况非常适合进行实验。在调试器中尝试一下，你会更有信心判断代码是否正确。 - RealSkeptic

我会做的。谢谢你的快速回复。 - user3889963

@maraca - 因为您在第二个参数中传递了 null，并且在第三个参数中传递了头部。第二个参数进入了 next - 所以 next 变成了 null，第三个参数进入了 prev，它将成为旧的头部。由于 next 是 null，head.next.prev 将抛出 NPE。 - RealSkeptic

@RealSkeptic 是的，我看到了错误，实现仍然是正确的，只是构造函数的顺序有误。好的，这基本上与你说的一样。 - maraca

Answer 1

这个实现有问题。如果调用多次，insertHead会抛出NullPointerException：

 head = new DLLNode(n, null, head);
 head.next.prev = head;  // head.next is null because of the above call

相反，插入的实现应该是：

public void insertHead(int n) {
    if (isEmpty()) {
        head = tail = new DLLNode(n);
    } else {
        head = new DLLNode(n, head, null);
        head.next.prev = head;
    }
}

在头部插入节点是一个两步操作:

1. 创建节点，将其next指针设置为指向当前头部，并将其分配为列表的新头部。
2. 将旧头部的previous指针设置为新头部。这就是语句head.next.prev = head的作用。

- M A

Answer 2

是的，你说得对，但代码确实在做你所说的事情（只有一个错误），也许如果我们使用括号，则会更清晰：

(head.next).prev = head;

我们将刚创建的节点分配给下一个节点。换句话说，我们将旧头部的prev引用更新为新头部，这是必要的，因为...

head = new DLLNode(n, null, head);

创建一个新的头节点，其中previous指向null，next指向旧的头节点，但旧头节点的previous引用仍为null。

在构造函数中，您将元素放置的顺序错误（或在创建新头节点的调用中）。

public DLLNode(int i, DLLNode p, DLLNode n) {

它能够正常工作。

- maraca