Преимущества связанных списков перед двоичными деревьями?

Question

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

Answer 1

Если хвост связанного списка сохранен, то вставка в связанный список решительно быстрее, чем вставка в двоичное дерево. Вставка в двоичное дерево - это O (N) в худшем случае (O (log N) в лучшем случае), если оно не сбалансировано. Если он сбалансирован, то вставки - это O (log N), но в поддержании его сбалансированности требуется ведение домашнего хозяйства. Вставка в связанный список - это O (1), если хвост сохранен.

Кроме того, как BillyONeal упомянул , двоичное дерево обычно является ассоциативной структурой, тогда как связанные списки не являются.

Answer 2

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

Answer 3

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

Answer 4

Связанный список обычно не используется в качестве ассоциативного контейнера (READ: не должен использоваться в качестве словаря) - только как буквальный список элементов, например, массив. Производительность бинарных деревьев, когда такая простая структура данных желательна, низкая.

Answer 5

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

Связанный список часто не сортируется, поэтому добавление новых узлов - это просто операция O (1), обычно добавляемая в конец списка.

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

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

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

Примечание. Вставка в связанный список - это другая (более медленная) операция, чем простое добавление / добавление. Для вставки часто требуется обход по списку, пока не будет найдена правильная позиция, O (n), где n - длина списка. Добавление - это просто добавление к концу списка (отсюда O (1))

Answer 6

Это в основном зависит от сценария. Если хвост связного списка сохраняется, то вставка в связанный список выполняется быстро. Удаление довольно быстро в связанном списке, но в случае поиска лучше в деревьях (o (log (n) для дерева баланса высот) и o (n) в связанном списке.

Answer 7

Честный вопрос.Мне нравится использовать контейнер, который наиболее "плотно" соответствует моим потребностям.Например, вы можете использовать список, когда все, что вам нужно, - это очередь без каких-либо реальных последствий ... но ... очереди высоко оптимизированы для этой конкретной задачи: отодвинуться вперед и вставить сзади, бездополнительные указатели, или что-нибудь.Используя наиболее подходящий класс, вы можете быть уверены, что не получите никакого дополнительного пуха, даже если у него тот же Big-O.Иногда эти скрытые константы имеют значение .