Практичность головы и хвоста в связанном списке

Question

Из того, что я понимаю, голова всегда указывает на первый узел в списке. Хвост всегда указывает на последний узел в списке.

Вопросы:

1) Но с точки зрения практичности, почему хвост полезен?

Я понимаю, что иметь голову полезно, потому что вам нужен сторожевой узел, который содержит нулевую ссылку, которая является работой головы.

2) Действительно ли имеет значение, отображать ли список, начиная с головы или начиная с хвоста?

Я видел несколько реализаций связанного списка с хвостом и другие реализации без хвоста.

public void insert(Link link)
    {
            // this executes once
            // when linked list is initially empty
            if(head == null)
            {
                // next point to the head
                link.next = head;
                // head point to the inserted link
                head = link;
                // tail point to the inserted link as well
                tail = link;
            }
            else
            {

                // next point to tail
                link.next = tail;
                // tail point to the inserted link 
                tail = link;
            }

    }

    public void display()
    {
        // display the linked list starting from the tail back to head 
        while(tail != null)
        {
            System.out.println(tail.data);
            tail = tail.next;

        }
    }

Answer 1

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

Заголовок указывает на начальный узел связанного списка, а Tail указывает на последний узел связанного списка.

1. Хвост позволяет обратные ссылки гораздо быстрее. Мол, добавление элемента в последний узел, переход от обратного порядка связанного списка. Следовательно, хвост также играет главную роль. Выполнение тех же операций с использованием head указатель будет громоздким.

Голова не меняет своего положения, когда-то назначенный узлу, в то время как хвост перемещается до последнего узла, связанного последним.

2. Хорошо, отображение узлов связанного списка отображает порядок на основе того, как они были добавлены в список. Так что, да, это всегда имеет значение, и отображение из head или же tail всегда будет отличаться и наоборот друг от друга.

Я надеюсь, что это очищает ваше замешательство.

Answer 2

1. Это позволяет добавить элемент в конец списка намного быстрее, поскольку вам не нужно перебирать все узлы, чтобы найти последний. Поскольку это, вероятно, самая распространенная операция в списке, она ОЧЕНЬ полезна.

2. Да. Список - это упорядоченная коллекция. Если я добавлю Алису, Боба и Чака в список в этом порядке и спросить, что в нем содержится, я хочу, чтобы Алиса, Боб и Чак отображались в этом порядке.