Имеет ли связанный список какую-либо ценность в языке с динамическими массивами?

Имеет ли связанный список какую-либо ценность в языке, который имеет динамические массивы, например Python (который, конечно же, имеет структуру данных списка)?

В настоящее время я понимаю, что список в python действительно просто статический массив, который по мере вставки большего количества данных переопределяет себя как новый массив (большего размера), копируя данные из старого в новый (таким образом делая его динамическим). это правильно?

Я также понимаю, как список и связанный список хранят данные в памяти по-разному (списки в непрерывном порядке и связанные списки в несмежном порядке), но дает ли это какие-либо серьезные преимущества?


python arrays dynamic-arrays linked-list
person sw123456    schedule 24.06.2015    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Да, это так. Удаление ссылки из связанного списка занимает O(1), в то время как для динамического массива оно является линейным.

Предположим, вы хотите построить структуру данных для LRU. Как правило, у вас будет хеш-таблица для операций «касания», а также массив последовательностей, чтобы увидеть, что устарело. При доступе к элементу хэш-таблица находит его в последовательности и перемещает в конец. Если элемент необходимо вытеснить, то первый элемент в последовательности используется для поиска элемента в хэш-таблице, который затем удаляется.

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

person Ami Tavory    schedule 24.06.2015
comment
В качестве альтернативы вы можете просто использовать упорядоченный словарь . - person Veedrac; 24.06.2015
comment
@Veedrac Действительно ли вставка/удаление в упорядоченном словаре O (1)? Я предполагаю, что вместо этого вы получите O (lg (n)) - разница может быть важной. Также обратите внимание, что упомянутый упорядоченный словарь упорядочен по порядку вставки, что означает, что вы можете вставлять только в один конец последовательности. - person skyking; 24.06.2015
comment
@skyking Это упорядочено по времени вставки, а не по значению. Он амортизируется за O(1), как и большинство операций со словарями. Тот факт, что это непрерывная память, должен с лихвой окупить периодическое повторное уплотнение. - person Veedrac; 24.06.2015
comment
@Veedrac Есть и другие сценарии, в которых предпочтительнее связанный список. Упорядоченный словарь не работает во всех этих случаях. - person skyking; 24.06.2015
comment
@skyking Конечно, но для очереди LRU я бы придерживался словаря. - person Veedrac; 24.06.2015
comment
@Veedrac Однако, как выясняется, объект OrderedDict представляет собой один dict (который оказывается хеш-таблицей) в сочетании с одним связанным списком. Да, если библиотека содержит решение, которое вы все равно использовали бы, вы должны его использовать;) - person skyking; 24.06.2015
comment
@skyking Вы должны прочитать ссылку, которую я дал. Это старая реализация. CPython все еще использует это, но планирует обновить (я думаю). PyPy уже обновлен. - person Veedrac; 24.06.2015