реализация связанного списка, добавление в начале или добавление в конце?

Question

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

Answer 1

Абсолютно простую реализацию связанного списка можно только (эффективно) добавить в начало. Чтобы добавить к хвосту, вам нужен второй указатель, который указывает на текущий последний элемент.

Пользователи, вероятно, хотят иметь возможность добавлять к любому концу, а также иметь возможность запрашивать длину списка в постоянное время и перемещаться по списку от хвоста к голове (что означает, что вам нужен двойной связанный список), поэтому разумная реализация по умолчанию должна поддерживать это (как в java.util).

Вы будете использовать односвязные списки только в том случае, если сможете оправдать ограниченную функциональность и получить реальную выгоду взамен (например, совместное использование хвостов для сокращения требований к хранилищу). ConcurrentLinkedQueue представляется односвязным, чтобы обеспечить параллельный доступ без блокировки. Компромисс невозможности узнать текущую длину упоминается в Javadocs.

Answer 2

Там нет никакой пользы вообще. Фактически, единственное, что делает голову головой, а хвост - это то, что мы называем одну голову, а другую - хвост. Вы могли бы заменить голову хвостом, а хвост - головой, и у вас был бы такой же точный список, за исключением того, что он был бы «задом наперед». (Это предполагает двусвязный список ...)

Это как материя и антивещество ...

Answer 3

java.util.LinkedList реализует обе функции. Это делает его универсальным - его можно использовать как очередь (FIFO) и как стек (LIFO)