Я пишу тип данных связанного списка, и поэтому у меня в настоящее время есть стандартный указатель заголовка, который ссылается на первый элемент, а затем следующий указатель для каждого элемента, который указывает на следующий, так что последний элемент имеет next = NULL.
Мне просто любопытно, каковы плюсы / минусы или лучшие практики для отслеживания последнего узла. У меня может быть указатель «хвост», который всегда указывает на последний узел, что упрощает добавление, или я мог бы перебирать список, начиная с указателя заголовка, чтобы найти последний узел, когда я хочу добавить. Какой способ лучше?
Обычно рекомендуется хранить хвост. Если мы подумаем о сложности добавления элемента в конце (если это обычная операция), у вас будет время O (n) для поиска хвоста или O (1), если вы его сохраните.
Другой вариант, который вы можете рассмотреть, — сделать свой список двусвязным. Таким образом, если вы хотите удалить конец списка, сохраняя хвост, вы можете удалить узлы за O (1) раз. Но это повлечет за собой сохранение дополнительного указателя для каждого элемента вашего списка (не дорого, но складывается и следует учитывать для систем с ограничением памяти).
В конце концов, все дело в необходимых вам операциях. Если вы никогда не добавляете, не удаляете или не работаете с конца вашего списка, нет причин для этого. Я рекомендую проанализировать сложность ваших наиболее распространенных операций и основывать свое решение на этом.
Также учитывайте добавленную стоимость хранения избыточных указателей. Если ваш список очень длинный, вы можете получить очень большой объем памяти. — person arcologies; 17.09.2013
Зависит от того, как часто вам нужно искать последний узел, но в целом лучше иметь указатель
tail.Простое сохранение и обновление указателя
tailтребует очень небольших затрат, но вы должны не забывать его обновлять! Если вы можете постоянно обновлять его, тогда операции добавления будут намного быстрее (O(1)вместоO(n)). Итак, если вы обычно добавляете элементы в конец списка, вам обязательно нужно создать и поддерживать указательtail.Если у вас есть двусвязный список, где каждый элемент содержит указатель на элементы
nextиprev, то указательtailиспользуется почти повсеместно.С другой стороны, если это отсортированный список, вы не будете добавлять его в конец, поэтому указатель
tailникогда не будет использоваться. Тем не менее, держать указатель на месте — это хорошая идея, на всякий случай, если вы решите, что он вам понадобится в будущем.