Не могу визуализировать вставку узла в конец связанного списка

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

Может быть, это поможет, если вы просто измените код на нечто похожее, которое все еще делает то же самое, но дает вам другую точку зрения. Иногда наименование переменной - это все, что вас смущает.

Для лучшего понимания переименуйте last в current, потому что вы начинаете с головы, а затем последовательно смотрите на каждый узел, пока не найдете узел, на который указывает nextна null, что указывает на конец списка.

Помните, что .next сам по себе является узлом, а current используется в качестве итератора. Вы также можете написать это как for -loop:

Node current = head;
for(current; current.next != null; current.next)
//now current refers to the last node since current.next now points to null
current.next = new_node;
//The new end is now new_node - new_node.next points to null

Answer 2

Основной связанный список просто начинается с узла Head, и каждый узел в списке указывает на следующий узел в списке. Последнему узлу будет присвоено значение 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;

Он начинается с головы и смотрит на его next. Если это не null, это означает, что это все еще не фактический последний узел списка, поэтому он устанавливает переменную last на следующий. Пока, наконец, он не найдет тот, для которого next установлен в null. Переменная last действительно является последней действительной, когда цикл while завершается.

Затем она просто устанавливает next узла last на новый узел. Новый узел уже имеет next, установленный на null, поэтому в следующий раз, когда будет выполнен обход, это будет узел last.