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() 方法。

现在我明白了，如果有人在main方法中运行insertHead(10)，如果列表是空的；一个新对象形成，头和尾引用变量都指向该对象。

我不明白的是如果列表不为空；代码片段非常混乱。

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

1)我理解的是n=10,null和head传给构造函数：publicDLLNode(int i, DLLNode n, DLLNode p).然后赋值info=10,next=null并且 prev=head 出现。一个问题是，如果列表中至少有一个项目可用，并且我将另一个项目添加到 HEAD 位置，不应该 "next" 指向前一个头部，而 "prev" 指向 null 吗？可能是错误的代码？？

2)代码是什么

head.next.prev = head;

是什么意思？？为什么有必要？我真的不明白这个逻辑...:(

任何帮助将不胜感激..

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;
    }
}

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

创建节点，设置它的next指针指向当前头，并将其指定为链表的新头。
将旧磁头的previous指针设置为新磁头。这就是语句 head.next.prev = head 的作用。

Answer 2

是的，你是对的，但代码完全按照你说的去做（只是一个错误），也许如果我们使用括号它会变得更清楚：

(head.next).prev = head;

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

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

创建一个新的head，previous指向null，next是旧head，但是旧head的previous引用仍然是null。

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

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

而且有效。

java-双向链表逻辑

java-Doubly Linked List logic

java

object

doubly-linked-list