Почему вставка в середину связанного списка O(1)?

Question

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

Разве этот анализ не учитывает нахождение операции узла (хотя это и требуется) и только саму вставку?

Редактировать:

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

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

Массивы:

• Нахождение точки вставки/удаления O(1)
• Выполнение вставки/удаления O(n)

Связанные списки:

• Нахождение точки вставки/удаления O(n)
• Выполнение операции вставки/ удаления O(1)

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

Answer 1

Вы правы, в статье рассматривается "Индексирование" как отдельная операция.Таким образом, вставка сама по себе является O (1), но переход к этому среднему узлу - O (n).

Answer 2

Сама вставка равна O(1).Поиск узла - это O(n).

Answer 3

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

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

Редактировать:Чувак, ты набираешь второй абзац, и внезапно вместо того, чтобы быть первым ответчиком, ты 5-й, говорящий то же самое, что и первые 4!

Answer 4

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

Так что да, они предполагают, что у вас уже есть указатель на этот узел, или что получение указателя тривиально.Другими словами, проблема сформулирована:"заданный узел в точке X, какой код вставить после этого узла?" Вы можете начать с точки вставки.

Answer 5

Вставка в связанный список отличается от итерации по нему.Вы не размещаете элемент, вы сбрасываете указатели, чтобы поместить элемент туда.Не имеет значения, будет ли он вставлен ближе к интерфейсу или ближе к концу, вставка по-прежнему включает переназначение указателей.Конечно, это будет зависеть от того, как это было реализовано, но в этом и заключается сила списков - вы можете легко вставлять.Доступ через индекс - это то место, где отображается массив.Однако для списка обычно требуется O (n), чтобы найти n-й элемент.По крайней мере, это то, что я помню со школы.

Answer 6

Потому что это не предполагает никакого зацикливания.

Вставка - это как:

• вставить элемент
• ссылка на предыдущую
• ссылка на следующий
• Выполнено

в любом случае, это постоянное время.

Следовательно, вставка n элементов один за другим равна O(n).

Answer 7

Разве этот анализ не учитывает нахождение операции узла (хотя это и требуется) и только саму вставку?

Ты понял это.Вставка в заданной точке предполагает, что у вас уже есть указатель на элемент, который вы хотите вставить после:

InsertItem(item * newItem, item * afterItem)

Answer 8

Вставка - это O (1), как только вы знаете, куда собираетесь ее поместить.

Answer 9

Нет, это не учитывает поиск.Но если у вас уже есть указатель на элемент в середине списка, вставка в этой точке равна O(1).

Если вам нужно его найти, вам придется добавить время на поиск, которое должно быть O (n).

Answer 10

Статья посвящена сравнению массивов со списками.Поиск позиции вставки как для массивов, так и для списков равен O (N), поэтому в статье это игнорируется.

Answer 11

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

Answer 12

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

Answer 13

Если у вас есть ссылка на узел для вставки после операции, это O(1) для связанного списка.
Для массива это все равно O (n), так как вам нужно переместить все последующие узлы.

Answer 14

Наиболее распространенными случаями, вероятно, являются вставки в начале или в конце списка (а поиск концов списка может не занять много времени).

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