Путаница во время вставки связанного списка

Question

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

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

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

Может кто-нибудь уточнить, пожалуйста? Спасибо.

Answer 1

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

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

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

Пример

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

Answer 2

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

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).

Answer 3

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

Answer 4

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

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

Answer 5

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

Answer 6

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

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

Answer 7

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

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