Связанный список - Добавляющий узел: цикл или указатель?

Question

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

Мне просто интересно, какие плюсы/минусы или лучшие практики предназначены для отслеживания последнего узла. У меня мог бы быть указатель «хвоста», который всегда указывает на последний узел, упрощающий добавление, или я мог бы перебирать список, начиная с указателя головы, чтобы найти последний узел, когда хочу добавить. Какой метод лучше?

Answer 1

Обычно рекомендуется хранить хвост. Если мы подумаем о сложности добавления элемента в конце (если это операция, которую вы обычно делаете), то время O (n) будет искать хвост или O (1), если вы его сохраните.

Другой вариант, который вы можете рассмотреть, состоит в том, чтобы сделать ваш список дважды связанным. Таким образом, когда вы хотите удалить конец списка, путем хранения хвоста вы можете удалить узлы в O (1) раз. Но это повлечет за собой дополнительный указатель, который будет храниться для каждого элемента вашего списка (не дорого, но он добавляется и должен учитываться для систем с ограниченной памятью).

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

Answer 2

Зависит от того, как часто вам нужно найти последний узел, но в целом лучше всего иметь указатель tail.

Существует очень небольшая стоимость, просто сохраняя и обновляя указатель tail, но вы должны помнить о его обновлении! Если вы можете сохранить его в обновленном состоянии, то он сделает операции добавления намного быстрее (O(1) вместо O(n)). Итак, если вы обычно добавляете элементы в конец списка, тогда вы должны абсолютно создавать и поддерживать указатель tail.

Если у вас есть дважды связанный список, в котором каждый элемент содержит указатель как к nextиprev элементов, то tail указатель почти повсеместно используется.

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