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

Мое понимание...

Преимущества:

• Вставка в конце O (1) вместо O (N).
• Если список является двусвязным списком, то удаление с конца также означает O (1) вместо O (N).

Недостаток:

• Занимает тривиальное количество дополнительной памяти: 4-8 байт .
• Исполнитель должен следить за хвостом.

Глядя на эти преимущества и недостатки, я не могу понять, почему Связанный список никогда не использовал бы хвостовой указатель. Я что-то пропустил?

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

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

Связанные списки очень часто являются постоянными и неизменными. На самом деле, в функциональных языках программирования такое использование повсеместно. Хвост указатели нарушают оба этих свойства. Однако, если вы не заботитесь об неизменности или постоянстве, есть очень мало недостатков в том, чтобы включить указатель хвоста.

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

Часто в моем обычном случае использования односвязного списка могут храниться сотни тысяч связанных списков, каждый из которых содержит только несколько узлов списка. Я также обычно не использую указатели для связанных списков. Вместо этого я использую индексы в массиве, поскольку индексы могут быть 32-битными, например, занимая половину пространства 64-битного указателя. Я также обычно не выделяю узлы списка по одному, и вместо этого, опять же, просто использую большой массив для хранения всех узлов, а затем использую 32-битные индексы, чтобы связать узлы вместе.

В качестве примера представьте себе видеоигру, использующую сетку 400x400 для разделения миллиона частиц, которые движутся и отскакивают друг от друга, чтобы ускорить обнаружение столкновений. В этом случае довольно эффективный способ хранения, который заключается в хранении 160 000 односвязных списков, что в моем случае означает 160 000 32-разрядных целых чисел (~ 640 килобайт) и одну 32-разрядную целочисленную служебную нагрузку на частицу. Теперь, когда частицы перемещаются по экрану, все, что нам нужно сделать, это обновить несколько 32-разрядных целых чисел, чтобы переместить частицу из одной ячейки в другую, например, так:

... с nextиндексом ("указателем") узла частицы, служащим либо индексом для следующей частицы в ячейке, либо следующей свободной частицы для восстановления, если частица умерла (в основном реализация распределителя свободного списка с использованием индексов):

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

Хвостовой указатель удвоил бы использование памяти сетки, а также увеличил бы количество пропусков кэша. Также требуется вставка, чтобы ветвь проверяла, является ли список пустым, а не ветвящимся. Создание этого двусвязного списка увеличит вдвое издержки списка каждой частицы. 90% времени я использую связанные списки, это для подобных случаев, и поэтому хвостовой указатель на самом деле довольно дорогой для хранения.

Так что 4-8 байтов на самом деле не тривиальны в большинстве случаев, в которых я в первую очередь использую связанные списки. Я просто хотел добавить сюда, так как если вы используете структуру данных для хранения множества элементов, то 4-8 байтов не всегда могут быть настолько незначительными. Я на самом деле использую связанные списки, чтобы уменьшить количество выделяемой памяти и объем требуемой памяти, в отличие от, скажем, хранения 160 000 динамических массивов, которые растут для сетки, которая будет использовать взрывное использование памяти (обычно один указатель плюс два целых по крайней мере на одну ячейку сетки). наряду с распределением кучи на ячейку сетки, в отличие от одного целого и нулевого распределения кучи на ячейку).

Я часто нахожу многих людей, ищущих связанные списки из-за их сложности в постоянном времени, связанной с удалением спереди / серединой и вставкой спереди / средним, когда LL часто являются плохим выбором в этих случаях из-за их общего отсутствия смежности. Где LL прекрасны для меня с точки зрения производительности, так это возможность просто перемещать один элемент из одного списка в другой, просто манипулируя несколькими указателями, и имея возможность получить структуру данных переменного размера без распределителя памяти переменного размера (так как каждый узел имеет одинаковый размер, мы можем использовать свободные списки, например). Если каждый узел списка распределяется индивидуально по отношению к распределителю общего назначения, обычно это происходит, когда связанные списки работают намного хуже по сравнению с альтернативами, и это '

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

Стоит также помнить, что в наши дни у нас есть много DRAM, но это второй самый медленный тип памяти. Мы все еще находимся на уровне около 64 КБ на ядро, когда дело доходит до кэша L1 с 64-байтовыми строками кэша. В результате, эта небольшая экономия байтов может действительно иметь значение в критически важной для производительности области, как приведенная выше сима частицы, при умножении в миллионы раз, если это означает разницу между хранением вдвое большего количества узлов в строке кэша или нет, например