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

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. Да. Список - это упорядоченная коллекция. Если я добавлю Алису, Бобу и Чаку к списку в этом порядке и спрошу список, что он содержит, я хочу, чтобы Алиса, Боб и Чак были показаны в этом порядке.