Беспорядок времени выполнения вставки Связанного списка

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

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

И нет, не во всех реализациях связанного списка есть указатель на конец списка.

Пример

Предположим, у Вас есть пустой список, в который Вы добавляете одиночный узел, x. Затем к списку добавляются n узлов до и после x. Одиночный узел можно добавить после x, просто обновив его следующим указателем (и новые узлы), независимо от того, сколько узлов было в списке.

Внесение изменений в связанный список включает в себя две операции:

1. определение местоположения узла для добавления нового узла к
2. фактическому добавлению узла, путем изменения указателей узла

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

Что касается середины, Ваш анализ корректен в том, что локализация узла также займет O(n). Однако, некоторые библиотеки выставляют метод, который приведет указатель на то, куда должен быть вставлен новый узел, а не на индекс (например, C++ list). Это устраняет линейную стоимость, в результате чего получается более O(1).

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

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

Что касается вставки посередине. Некоторые библиотеки, такие как C++, имеют предлагаемое место для вставки. Они берут указатель на узел списка, к которому добавляется новый. Такие вставки будут стоить O(1). Я не думаю, что можно достичь O(1) по номеру индекса.

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

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

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

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

Очевидно, что вы, вероятно, просмотрели запись в википедии http://en.wikipedia.org/wiki/Linked_list. Я вижу таблицу, в которой они указывают, что и вставка/удаление из конца и в середине списка имеют исполнение O(1), но не уточняют, как они это определили.

Здесь есть несколько интересных ответов на похожий вопрос по стековому переполнению на Почему вставка в середине связанного списка O(1)?. Оригинальный плакат этого вопроса отредактировал свой пост и указал, что он верит, когда говорится, что вставка/удаление - это O(1), они говорят о фактической операции вставки, а не о нахождении того, куда вставлять. Это имеет смысл, но я не видел ни в одной из статей, которые я нашел на данный момент.

Я думаю, что одна из причин вашей путаницы заключается в том, что вы думаете, как будто существует идеальный/канонический связанный список, который либо имеет, либо не имеет определенных указателей на голову/хвост. Реальность такова, что любая линейная (т.е. не ветвящаяся) структура данных, которая обращается к элементам через указатели из предыдущих элементов, в основном является связным списком. Сохраняете ли вы указатели на первый, последний, k-ый и т.д. элементы, полностью зависит от вас. Итак, если вам нужен список, в который вам часто приходится вставлять/удалять элементы, находящиеся на 10 позиции, вы можете просто реализовать список, который имеет дополнительный указатель на 9-й элемент и сделать это за O(1) время.

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

Как указывает @Kaleb Brasee, вставка в хвосте на Java - O(1), потому что Java использует двойной список в качестве реализации LinkedList. Я думаю, что это довольно распространенный выбор для многих реализаций SDK. Например, реализация STL list является двусвязной (source).