#java #linked-list
#java #связанный список
Вопрос:
Я видел много реализаций добавления связанного списка в начале, затем обновления ссылки на заголовок или не изменения ссылки на заголовок и добавления в конце, обновляя его каждый раз. Есть ли очевидное преимущество одного по сравнению с другим? Какой из них является предпочтительным способом реализации?
Комментарии:
1. Один помещает новый узел в начало, а другой — в конец. Является ли это преимуществом, зависит от того, где вы хотите разместить свой новый узел.
Ответ №1:
Никакой пользы вообще. На самом деле, единственное, что делает начало заголовком, а хвост — хвостом, это то, что мы называем одно начало, а другое — хвост. Вы могли бы заменить head на tail, а tail на head, и у вас был бы точно такой же список, за исключением того, что он был бы «наоборот». (Это предполагает наличие двусвязного списка …)
Это что-то вроде вещества и антивещества…
Ответ №2:
Абсолютно простая реализация связанного списка может (эффективно) добавлять только в начале. Для добавления в конец вам нужен второй указатель, который указывает на текущий последний элемент.
Пользователи, вероятно, хотят иметь возможность добавлять в любой конец, а также иметь возможность запрашивать длину списка за постоянное время и перемещаться по списку от конца к началу (это означает, что вам нужен список с двойной связью), поэтому разумная реализация по умолчанию должна поддерживать это (точно так же, как в java.util).
Вы бы использовали односвязные списки, только если можете оправдать ограниченную функциональность и получить взамен какую-то реальную выгоду (например, совместное использование содержимого для снижения требований к хранилищу). Concurrentlink queue, похоже, односвязный, чтобы обеспечить параллелизм без блокировок. Компромисс, связанный с невозможностью узнать текущую длину, упоминается в Javadocs.
Комментарии:
1. Честно говоря, я не знаю ни о каких реализациях односвязных списков в производственных библиотеках.
2. @glowcoder: Я думаю, java.util.concurrent. Concurrentlink queue является односвязным.
3. вы могли бы поспорить, является ли это списком (обратите внимание на явное отсутствие реализации интерфейса списка), хотя, похоже, что он реализован с односвязным списком внизу. Это правда, что очередь FIFO не выиграет от двойной ссылки.
Ответ №3:
java.util.LinkedList реализует обе функции. Это делает его универсальным — его можно использовать как очередь (FIFO) и как стек (LIFO)