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

Question

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

Answer 1

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

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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

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

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

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