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

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;

Answer 2

我不会给你完整的代码，但我会把它可视化。之后您可以轻松地编写代码。

Next 是--->，Previous 是<---，last 指向最后一个节点，first 指向第一个节点

假设你有这个清单。

Banana ---> Orange ---> Gorilla ---> null

       <---        <---         

  ^                       ^

  |                       |

first                    last

// First's previous and last's next is null.

你想在最后添加芒果。您创建一个新节点

DoubleNode node = new DoubleNode("Mango");

<--- Mango --->

// Note: When you create a new node by default both next and previous are null. 

// You don't need to point them to null later

步骤1：

last.next(newNode);

Banana ---> Orange ---> Gorilla ---> Mango 

       <---        <---    

  ^                       ^

  |                       |

first                    last  

第2步：

newNode.previous(last);

Banana ---> Orange ---> Gorilla ---> Mango 

       <---        <---         <---

  ^                       ^

  |                       |

first                    last

现在我们有新的最后一个，所以我们将更新最后一个

last = newNode

Banana ---> Orange ---> Gorilla ---> Mango 

       <---        <---         <---

  ^                                    ^

  |                                    |

first                                last

从构造函数中我们知道 Mango 的 next 已经为 null，因此newNode.next(null);没有必要。

您可能会遇到 nullpointerException 的原因

添加第一个元素后，您的列表如下所示

null <--- Banana ---> null      null

             ^                   ^

             |                   |

           first                last

从技术上讲，你应该将第一个和最后一个点都指向香蕉，因为你没有这样做。当你将某些东西放入队列时，比如说大猩猩。这将是

null.item = "Gorilla"

null.next = null