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

106

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

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

ИЗМЕНИТЬ :

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

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

Массивы:

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

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

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

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

Роб Соберс
источник

Ответы:

113

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

CookieOfFortune
источник
3
Что делает большую разницу при вставке более чем 1 объект в том же положении ...
прекращал - Anony-Мусс
@ Anony-Mousse, ты можешь объяснить это поподробнее? т.е. нам нужно найти позицию вставки только один раз при вставке нескольких объектов?
MyTitle
2
Это O (n) в размере существующего списка, а не в количестве вставок, которые вы планируете в него сделать.
ВЫЙТИ - Anony-Mousse
28

Сама вставка - O (1). Нахождение узла - O (n).

Evansbee
источник
26

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

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

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

Билл К
источник
1
Ха, да, это отстой ... Я добавил +1 к твоему, потому что стоит отметить, что сложность вставки связанных списков рассматривается в контексте уже нахождения на желаемом указателе.
Даниэль Масиас
6

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

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

Джоэл Кохорн
источник
5

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

егоматт
источник
3

Потому что в нем нет цикла.

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

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

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

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

Томалак
источник
3

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

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

InsertItem(item * newItem, item * afterItem)
е. Джеймс
источник
2

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

Лэнс Ричардсон
источник
2

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

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

ТЕД
источник
0

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


источник
1
Разве точка вставки массива не будет O (1)? Поскольку массивы хранятся в непрерывной памяти, все, что ему нужно сделать, это добавить смещение.
Роб Соберс,
@ vg1890 - Сначала вам нужно найти смещение.
0

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

Гленн
источник
0

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

workmad3
источник
0

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

Сани Сингх Хуттунен
источник
0

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

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

ChrisW
источник
Можно сделать вставку элементов в конец массива равной O (1), если вы сохраните буфер пустых элементов в конце, хотя иногда вставки по-прежнему будут O (1). Большинство коллекций делают это. Также можно сделать инерцию элементов в начало массива равной O (1), изменив оператор индекса так, чтобы он возвращал номер элемента (n + x)% len, где x - количество раз, когда вы вставляли элементы в начало. списка. Deques иногда реализуются таким образом (но также иногда реализуются с двусвязными списками.
Брайан,