Почему вставка в середине связанного списка 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) время, чтобы отсоединить два соседних узла и вставить свой новый.

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

Answer 4

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

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

Answer 5

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

Answer 6

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

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

InsertItem(item * newItem, item * afterItem)

Answer 7

Потому что это не связано с зацикливанием.

Вставка похожа на:

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

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

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

Answer 8

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

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

Answer 9

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

Answer 10

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

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