Связанный список вставки пробега путаницы

Question

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

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

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

Не могли бы вы прояснить ситуацию? Благодарю.

Answer 1

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

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

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

Пример

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

Answer 2

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

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

В Linked List, вторая операция - операция 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

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

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

Answer 4

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

Есть несколько интересных ответов на аналогичный вопрос здесь, на stackoverflow на Why is inserting in the middle of a linked list O(1)?. Оригинальный плакат этого вопроса отредактировал его сообщение и сделал вывод, что он верит, когда говорится, что вставка/удаление - O (1), они говорят о фактической операции вставки, а не о том, куда вставить. Это имеет смысл, но я не видел того, что официально заявлено в любой из статей, которые я нашел на этом этапе.

Answer 5

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

Answer 6

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

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

Answer 7

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