Создать связанный список с головным и хвостовым узлами

Question

Я новичок в структуре данных. Когда вы создаете связанный список с головным и хвостовым узлами, зачем мне связывать новый узел с хвостовым? Разве не достаточно, чтобы tail.next был связан с newNode?

как это:

public void add( Object data ) {
ListNode newNode = new ListNode( data );
    if ( isEmpty() ) {
        head = newNode;
    } else {
        tail.setNext( newNode );
    }
    tail = newNode;
    length = length + 1;
}

или вот так:

if(head == null) {
    head = tail = newNode;
} else {
    tail.next = newNode;
    tail = newNode;
}

Я посмотрел основы LinkedList, но до сих пор не могу понять это так хорошо. Я не уверен, как это позволяет заголовку ссылки вести на tail и как tail может сохранить предыдущее значение, если вы замените tail на newNode. Не могли бы вы объяснить это мне? Спасибо вам большое!

Answer 1

Голова не привязана к хвосту. Вы должны думать о них как об отдельных предметах. Голова указывает на начало списка и хвост до конца. Давайте предположим, что вы только добавляете, а не удаляете, просто для простоты.

Голова и хвост начинаются пустыми (указывая на NULL). С добавлением первого newNode (назовем его A) и head, и tail устанавливаются в A..., поскольку это единственная запись, по определению как начало, так и конец.

Когда вы добавляете второй узел (B), то заголовок остается тем же, текущий tail.next устанавливается в B (который также устанавливает head.next). И после этого хвост устанавливается на B.

Какой третий узел (С) добавляется, голова не меняется вообще. Но tail.next установлен в C, а хвост перемещен в C. Итак, теперь у нас есть A.next = B, B.next =C, а C.next равен NULL. Голова указывает на А, а хвост на С.

Answer 2

Когда список имеет только один узел, head а также tail указывают на один и тот же узел, поэтому изменения на то, что либо указывает на изменения, на что указывают оба (пока вы не измените head или же tail). Так что в этом случае, имея tail.next указать на новый узел также делает head.next указать на это. Когда список длиннее, меняется на tail не повлияет head (и вы не хотели бы их!)

Answer 3

Давайте посмотрим на иллюстрацию:

У тебя есть A в вашем списке. Вы хотите добавить B, Когда ты это сделаешь, A указывает на B как его преемник и B превращается в последний узел (хвост).

Это именно то, что происходит в вашем коде каждый раз, когда вы добавляете новый узел. Предыдущий хвост передает свое место новому хвосту, но должен сохранять ссылку на новый, чтобы список мог оставаться взаимосвязанным.

Я надеюсь, что это помогает,

С уважением,