Почему не удаляется O (1) в односвязных списках и двусвязных списках, если дан узел для удаления?

Question

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

Обычно упоминается, что одним из преимуществ использования двусвязного списка над односвязным списком является то, что удаление - это O (1), когда у нас есть ссылка на узел, который мы хотим удалить. Т.е., если вы хотите удалить узел i, просто сделайте следующее: i.prev.next = i.next и i.next.prev = i.prev

Говорят, что удаление - это O (1) в ТОЛЬКО связанном списке, только если у вас есть ссылка на узел перед тем, который вы хотите удалить. Тем не менее, я не думаю, что это обязательно так. Если вы хотите удалить узел i (и у вас есть ссылка на узел i), почему вы не можете просто скопировать данные из i.next и установить i.next = i.next.next? Это также будет O (1), как в случае двусвязного списка, что означает, что удаление не является более эффективным в двусвязном списке в ЛЮБОМ случае, если речь идет о Big-O. Конечно, эта идея не будет работать, если узел, который вы пытаетесь удалить, является последним узлом в связанном списке.

Меня действительно беспокоит то, что никто не помнит этого, сравнивая одиночные и двусвязные списки. Чего мне не хватает?

Чтобы уточнить : в случае односвязного случая я предлагаю перезаписать данные на узле, который вы хотите удалить , данными из следующего узла, а затем удаляя следующий узел. Это имеет тот же желаемый эффект, что и удаление узла i, хотя это не то, что вы делаете как таковое.

EDIT

Что я выучил:

Так что, похоже, я в некоторой степени прав. Прежде всего, многие люди отметили, что мое решение не является полным, так как удаление последнего элемента является проблемой, поэтому мой алгоритм O (n) (по определению Big-O). В ответ я наивно предложил обойти это, отслеживая «второй-последний узел» в вашем списке - конечно, это вызывает проблемы, как только последний узел в вашем списке был удален в первый раз. Решение, которое было предложено и, похоже, работает, состоит в том, чтобы разграничить конец вашего списка чем-то вроде NullNode, и мне нравится этот подход.

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

Answer 1

Удаление для одного списка ссылок

Предположим, что всего 6 узлов. и первый узел указывает Head.

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

Если вы хотите удалить 4-й узел, то сложность будет O (n)

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

Answer 2

Хороший вопрос.

Простой ответ: Альтернативное решение, которое вы предлагаете для односвязных списков, не является полным и завершается неудачно, когда вам предоставляется последний узел для удаления. Невозможно заставить предыдущий узел указывать на ноль.

Следовательно, для правильного решения сложность в случае удаления в односвязном списке составляет O (n).

Answer 3

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

Пока у вас нет ссылок на список, этот подход будет работать. В противном случае он подвержен сбоям.

Answer 4

Говорят, что удаление - это O (1) в односвязном списке ТОЛЬКО если вы иметь ссылку на узел перед тем, который вы хотите удалить. Тем не менее, я не думаю, что это обязательно так. Если хотите удалить Node i (и у вас есть ссылка на Node i), почему вы не можете просто скопируйте данные из i.next и установите i.next = i.next.next?

Поскольку это «следующий» элемент предыдущего узла, который вы хотите установить равным тому, на что указывает i.next перед удалением i. Поиск предыдущего узла - это операция O (N) для односвязного списка, если у вас нет ссылки на него. Для двойного связанного списка поиск предыдущего узла - это операция O (1), как и должно быть i.prev

Answer 5

Это правда, что копирование данных из i.next в i с последующим удалением i будет O(1) при условии, что копирование данных также O(1).

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

По поводу вашего комментария:

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

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

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

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

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

Кроме того, если вам нужно сохранить целостность ссылок, вы не захотите перемещать значения с одного узла на другой, т. Е. Если вы добавите ссылку на узел i+1 и удалите узел i, вы не ожидаете ваша ссылка недействительна, поэтому при удалении элементов более надежным вариантом является удаление самого узла.

Answer 6

Для узла в середине списка вам нужно изменить предыдущий узел (поэтому его «следующий» указатель указывает на удаленные узлы «следующий»).

Сдвойной список очень прост, поскольку удаляемый узел содержит указатель на предыдущий узел.Это невозможно с односвязным списком, где вам нужно перебирать список, пока вы не найдете узел, чей «следующий» указатель является узлом для удаления.

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