Давайте подумаем, как работает связанный список по сравнению с тем, как работает бинарное дерево
Для двусвязного списка у нас есть такие элементы, как
Head < - > 5 < - > 10 < - > 4 < - > tail
Если мы хотим добавить элемент, мы можем легко добавить егов начало или конец списка, указав наш новый элемент в конечную точку и значение, на которое указывает конечная точка, а затем обновив оба из них, чтобы они указывали на новый элемент (убедившись в правильном назначении предыдущего и следующего).здесь, но есть много хороших ресурсов, если вы ищете вставку в связанный список.Эта операция имеет O (1) сложность по времени.Проведите какое-нибудь исследование по вставке в (сбалансированные) двоичные деревья, это займет гораздо больше времени
А теперь как насчет поиска?В приведенном выше списке, если я хочу найти элемент, мне нужно пройти по всему списку с одной стороны, пока я не достигну нужного значения.Это приводит к O (n) временной сложности, однако, если у нас есть сбалансированное двоичное дерево, мы можем проверить, является ли то, что мы ищем, выше или ниже значения, которое находится ~ в середине.Если оно выше, мы можем убрать нижнюю половину чисел.Затем мы можем сделать тот же шаг с остальными числами.Это сокращает количество оставшихся чисел наполовину на каждом шаге и приводит к значительному сокращению времени.
Существует много способов оценить это, и они зависят от разных реализаций.Я советую вам выбрать, какую реализацию каждой из них вы хотите сосредоточить, сравнить временную сложность операций, а затем рассмотреть альтернативные реализации и то, что они делают, со временной сложностью операций.
Для двоичного кода следует учитывать сбалансированность и несбалансированность..
Для связанного списка посмотрите на двусвязные, односвязные, с указателями на хвост и без них (по существу, стек против очереди)
Если у вас есть вопросы о конкретных реализациях и их сравнении, сообщите нам, и мы будемсделать все возможное, чтобы прояснить это.