Java链接列表无法将项目添加到末尾

Question

似乎无法正确添加最后一个元素。我将最后一个项目保存在临时节点中，然后创建一个新节点。然后我链接每个节点的前一个和下一个，然后将最后一个节点指向一个新的空节点。但是当我转到 print() 方法时，该空节点似乎并不属于列表的一部分。

看起来它应该像我的推送方法一样简单，但我似乎无法让它像它一样工作。

public class LinkedListDeque {

public DoubleNode first = new DoubleNode(null);
public DoubleNode last = new DoubleNode(null);
public DoubleNode temp;
public int N;

LinkedListDeque() {
    first.next = last;
    last.prev = first;

}

public static void main(String[] args) {

    LinkedListDeque link = new LinkedListDeque();

    link.push("banana");
    link.printList();

    link.enqueue("gorilla");
    link.printList();


    link.enqueue("spam");

}


//nested class

private class DoubleNode {

    String item;
    int counter = 0;
    DoubleNode next;
    DoubleNode prev;

    DoubleNode(String i) {
        this.item = i;
    }

}

public void push(String item) {

    System.out.println("\npush()\n******");
    if (first.item == null) {
        first.item = item;
        first.counter++;
    } else {

        System.out.println("last.item = " + last.item);
        DoubleNode node = new DoubleNode(item);
        first.prev = node;
        node.next = first;
        first = node;

    }

}



 public void enqueue(String item) {
    System.out.println("\nenqueue()\n***********");
    System.out.println("adding \"" + item + "\" to the end");

    if (last.item == null) {
        DoubleNode node = new DoubleNode(null);                     //holds null node to end list
        last.item = item;
        last.next = node;
    } else {
        DoubleNode node = new DoubleNode(null);
        System.out.println("node = " + node.item);                  //= correct item

        temp = last;
        last = new DoubleNode(item);                                //creating a new last node

        System.out.println("temp = " + temp.item);                  //corect
        //reconnect the links
        temp.next.item = last.item;

        System.out.println("temp.prev = " + temp.prev.item);        //correct
        System.out.println("temp.next = " + temp.next.item);        //correct
        System.out.println("last = " + last.item);                  //correct
        System.out.println("last.prev = " + last.prev);             //correct

        last.prev = temp;

        System.out.println("last.prev = " + last.prev.item);        //correct

        last.next = node;
        System.out.println("last.next = " + last.next.item);        //= null to end list

        System.out.println("\n\nfirst = " + first.item);                                //correct
        System.out.println("first.next = " + first.next.item);                          //correct
        System.out.println("first.next.next = " + first.next.next.item);                //correct
        System.out.println("first.next.next.next = " + first.next.next.next.item);      //"null pointer exception"
}

public void printList() {
    System.out.println("\nprintList():\n********");
    temp = first;

    int i = 0;
    if (first.item == null) {
        temp = first.next;
    }
    System.out.println("temp = " + temp.item);
    while (temp.item != null) {
        i++;
        System.out.println(i + " " + temp.item);
        temp = temp.next;
    }
    System.out.println();
}

Answer 1

让我们看看实际发生了什么:初始状态:

• 第一个包含 null，first.next 是最后一个，最后一个包含 null
• push:first不再包含null，仍然指向last，且为null
• enque:last.item为null，因此触发第一个cae，现在列表如下:banana -> gorilla -> null，last指向gorilla
• 再次排队:现在 else 被触发。如果你看一下代码，你就会会注意到 temp.next 在任何地方都没有被触及。这意味着作为 enque 之前的最后一个节点并被复制到 temp 的节点仍然指向空节点。
• 这最终会导致空指针异常。

缺少什么:在创建最后一个节点之后，类似于 temp.next=last 的内容。

实际发生的情况如下所示:

---> last ---> closing-null

---> temp ---> closing-null

---> last

看来您可以更干净地实现这一点，而无需空节点关闭列表。

然后你可以这样做:

node=new Node(item);
last.next=node;
node.prev=last;
last=node;