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

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

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

ИЗМЕНИТЬ :

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

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

Массивы:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

InsertItem(item * newItem, item * afterItem)

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

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

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

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

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

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

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

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

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