#data-structures #linked-list #big-o
#структуры данных #связанный список #big-o
Вопрос:
Учитывая, что как для связанного списка, так и для массива вставка / удаление данных из середины имеет сложность O (n), почему предпочтительнее использовать связанный список? Является ли O (n) массива (выполнение операции) более дорогостоящим, чем индексация связанного списка?
Комментарии:
1. Каков ваш источник, говорящий о том, что «предпочтительнее использовать связанный список» и «быстрее вставлять и удалять в связанном списке»? Это зависит от используемого вами языка программирования. Кроме того, что вы подразумеваете под «(индексированием)» в контексте связанного списка?
Ответ №1:
Для массива размером «M»: если я хочу удалить элемент в N-й позиции, я могу сразу перейти к N-й позиции, используя индекс за один раз (мне не нужно проходить до N-го индекса), а затем я могу удалить элемент, до этого момента сложность равна O (1) тогда мне придется переместить остальные элементы (M-N сдвигов), чтобы моя сложность была линейной, т.Е. O (M-N 1). и, следовательно, удаление или вставка в конце дадут мне наилучшую производительность (как N ~ M), а удаление или вставка в начале будут худшими (как N ~ 1).
Теперь LinkedList размером «M»: если у вас уже есть ссылка на узел, который вы хотите вставить после или удалить по истечении времени, сложность равна O (1) . Если это не предусмотрено, мы не можем напрямую добраться до N-го элемента в LinkedList, для доступа к N-му элементу нам нужно пройти N элементов, поэтому поиск в LinkedList обходится дороже, чем в ArrayList.