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

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

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

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

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

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

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

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

потому что это не включает в себя какой-либо цикл.

вставка выглядит так:

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

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

следовательно, вставка 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), так как вы должны переместить все последовательные узлы.

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

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