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

Question

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

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

РЕДАКТИРОВАТЬ :

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

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

Массивы:

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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