Java 将节点添加到链表的末尾

Add node to end of Linked List

提问by user3413540

Having a bit of trouble adding a node to the end of my linked list. It only seems to display the very last one I added before I call my addFirst method. To me it looks like on the addLast method I'm trying to first create the node to assign it 5, then for the following numbers use a while loop to assign them to the last node on the linked list. Little stuck on why I can't get my output to display 5 and 6.

在我的链表末尾添加节点时遇到了一些麻烦。它似乎只显示我在调用 addFirst 方法之前添加的最后一个。对我来说，在 addLast 方法中，我试图首先创建节点以将其分配为 5，然后对于以下数字，使用 while 循环将它们分配给链表上的最后一个节点。为什么我不能让我的输出显示 5 和 6 几乎没有问题。

class LinkedList
{
    private class Node          
    {
    private Node link;
    private int x;
    }
    //----------------------------------
    private Node first = null;    
    //----------------------------------
    public void addFirst(int d)
    {
        Node newNode = new Node();
        newNode.x = d;            
        newNode.link = first;    
        first = newNode;           
    }
    //----------------------------------
    public void addLast(int d)
    {
        first = new Node();
        if (first == null)
        {
            first = first.link;
        }
        Node newLast = new Node();
        while (first.link != null)
        {
            first = first.link;
        }
        newLast.x = d;
        first.link = newLast;
        first = newLast;
    }
    //----------------------------------
    public void traverse()
    {
        Node p = first;
        while (p != null)           
        {
            System.out.println(p.x);  
            p = p.link;               
        }
    }
}
//==============================================
class test123
{
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.addLast(5);
        list.addLast(6);
        list.addLast(7);
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(3);
        System.out.println("Numbers on list");
        list.traverse();
    }
}

I've also tried creating a last Node and in the traverse method using a separate loop to traverse the last node. I end up with the same output!

我还尝试创建最后一个节点，并在 traverse 方法中使用单独的循环来遍历最后一个节点。我最终得到相同的输出！

   public void addLast(int d)
   {
       Node newLast = new Node();
       while (last.link != null)
       {
          last = newLast.link;
       }    
       newLast.x = d; 
       newLast.link = last;
       last = newLast;       
   }

回答by Shreya Srinivas

Your addLast() method displays the value of the last node because every time you append a node to the end of your list, you are overwriting the reference to "first". You are also doing this when you assign a new reference to first in the following line:

您的 addLast() 方法显示最后一个节点的值，因为每次将节点附加到列表末尾时，您都会覆盖对“第一个”的引用。当您在以下行中为 first 分配新引用时，您也在这样做：

first = new Node();

Try the following:

请尝试以下操作：

public void addLast(int d)
{
    Node newLast = new Node();
    if (first == null)
    {
        newLast.x = d;
        first = newLast;
        return;
    }
    Node curr = first;
    while (curr.link != null)
    {
        curr = curr.link;
    }
    newLast.x = d;
    curr.link = newLast;
}

The method creates a new node and it is added to the end of the list after checking two conditions: 1.) If first is null: in this case the list is empty and the first node should be initialized to the new node you are creating, then it will return (or you could do an if-else). 2.) If first is not null: If the list is not empty you'll loop through your list until you end up with a reference to the last node, after which you will set its next node to the one you just created.

该方法创建一个新节点，并在检查两个条件后将其添加到列表的末尾： 1.) 如果 first 为 null：在这种情况下，列表为空，第一个节点应初始化为您正在创建的新节点，然后它会返回（或者你可以做一个 if-else）。2.) 如果第一个不为空：如果列表不为空，您将遍历您的列表，直到最终引用最后一个节点，然后将其下一个节点设置为您刚刚创建的节点。

If you wanted to keep track of the tail of your list called "last", like you mentioned above, then add:

如果您想像上面提到的那样跟踪名为“last”的列表尾部，请添加：

last = newLast

at the end of your method. Hope this helps!

在你的方法结束时。希望这可以帮助！

回答by Jeff Ward

The logic of your addLast method was wrong. Your method was reassigning firstwith every call the logic falls apart from that point forward. This method will create the Node for lastand if the list is empty simply assign firstto the new node last. If firstis not null it will traverse the list until it finds a Node with a null link and make the assignment for that Nodes link.

您的 addLast 方法的逻辑是错误的。您的方法在first每次调用时都会重新分配逻辑从该点开始分崩离析。此方法将创建节点last，如果列表为空，只需将其分配first给新节点last。如果first不为空，它将遍历列表，直到找到具有空链接的节点并为该节点链接进行分配。

public void addLast(int d) {
    Node last = new Node();
    last.x = d;

    Node node = first;
    if (first == null) {
        first = last;
    } else {
        while (node.link != null) {
            node = node.link;
        }
        node.link = last;
    }
}