java-Doubly Linked List逻辑

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位置,则不应该"下一个"指向前一个头,而"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;
    }
}

在头部插入节点分为两步:

1. 创建节点,将其下一个指针设置为指向当前头并将其指定为列表的新头.
2. 将旧头的先前指针设置为新头.这就是声明的head.next.prev = head作用.