双链表逻辑

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被传递给构造函数：public DLLNode（int I,DLLNode n,DLLNode p）。然后赋值info=10，next=null和prev=head。一个问题是，如果列表中至少有一个项目可用，并且我在head位置添加了另一个项目，那么“next”不应该指向前面的head，而“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;
    }
}

在head插入节点需要两个步骤：

1. 创建节点，将其下一个指针设置为指向当前头，并将其指定为列表的新头。
2. 将旧磁头的前一个指针设置为新磁头。这就是语句head.next.prev=head所做的。