java - 无法可视化在链表末尾插入节点

Question

我目前正在尝试理解和可视化 Java 中的链表。

我了解链表的基本概念以及如何将节点添加到链表的头部。但是，我不明白新节点是如何添加到链表末尾的。

例如，在以下代码中:

public class LinkedList
{
    Node head; // head of list

    /* Linked list Node*/
    class Node
    {
        int data;
        Node next;
        Node(int d) {data = d; next = null; }
    }

    public void append(int new_data)
    {
        /* 1. Allocate the Node &
        2. Put in the data
        3. Set next as null */
        Node new_node = new Node(new_data);

        /* 4. If the Linked List is empty, then make the
            new node as head */
        if (head == null)
        {
            head = new Node(new_data);
            return;
        }

        /* 5. This new node is going to be the last node, so
            make next of it as null */
        new_node.next = null;

        /* 6. Else traverse till the last node */
        Node last = head;
        while (last.next != null)
            last = last.next;

        /* 7. Change the next of last node */
        last.next = new_node;
        return;
    }

    public static void main(String[] args)
    {
        /* Start with the empty list */
        LinkedList llist = new LinkedList();

        // Insert 6. So linked list becomes 6->NUllist
        llist.append(6);

        // Insert 4 at the end. So linked list becomes
        // 6->4->NUllist
        llist.append(4);
        llist.printList();
    }

    public void printList()
    {
        Node tnode = head;
        while (tnode != null)
        {
            System.out.print(tnode.data+" ");
            tnode = tnode.next;
        }
    }
}

虽然我可以可视化遍历(last 到达 llist 的末尾)，但我不明白为什么 last = last.next; (在 public void append(int new_data) 中)将该节点链接到前一个节点(为什么前一个 .next 指向它)。

感谢您的支持!

Answer 1

基本的链表只是从头节点开始，链表中的每个节点都指向链表中的下一个节点。最后一个节点的 next 将设置为 null，直到添加新节点，此时新节点将成为最后一个节点。

所以逻辑在这里完成:

/* 6. Else traverse till the last node */
        Node last = head;
        while (last.next != null)
            last = last.next;

        /* 7. Change the next of last node */
        last.next = new_node;

它从头部开始，然后查看其下一个。如果它不是 null ，则意味着它仍然不是列表的实际最后一个节点，因此它将 last 变量设置为下一个节点。直到最后它找到 next 设置为 null 的那个。当 while 循环结束时，last 变量才是真正实际的最后一个变量。

然后它只是将 last 节点的 next 设置为新节点。新节点已将其 next 设置为 null，因此下次遍历完成时，它将是 last 节点。