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

Question

Я не понимаю, почему удаление в конце одного связанного списка идет в O (1) раз, как говорит wikipedia article.

Один связанный список состоит из узлов. Узел содержит какие-то данные и ссылку на следующий узел. Ссылка на последний узел в связанном списке равна NULL.

-------------- --------------   -------------- 
| data | ref | -> | data | ref | -> ... -> | data | ref | 
-------------- --------------   -------------- 

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

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

-edit- Возможно, эта точка зрения дает еще несколько разъяснений. Но я вижу «удаление узла» как успешное удаление самого узла и установление предыдущей ссылки на нуль.

Answer 1

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

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

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

Надеюсь, это поможет!

Answer 2

Добавление/удаление ЛЮБОЙ узла на ЛЮБОЙ месте представляет собой О (1). Код просто играет с фиксированной стоимостью (несколько указателей указателей и malloc/frees) для добавления/удаления узла. Эта арифметическая стоимость фиксируется для любого конкретного случая.

Однако стоимость достижения (индексации) нужного узла равна O (n).

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

Answer 3

Например, вы можете иметь указатель на элемент перед последним («второй от конца») и при удалении: 1. Удалить * следующий элемент «второй от конца». 2. Установите этот «второй с конца» * рядом с NULL

Answer 4

O (1) просто означает «постоянная стоимость». Это не означает 1 операцию. Это означает, что операции «не более C» с C фиксируются независимо от изменения других параметров (например, размера списка). На самом деле, в иногда запутанном мире больших-Oh: O (1) == O (22).

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

Answer 5

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

Ваш «пустой» список начинается с одного дозорного

Head -> [Sentinel] 

Добавить некоторые вещи

Head -> 1 -> 2 -> 3 -> [Sentinel] 

Теперь удалите хвост (3), пометив узел, который был 3 недействительными, а затем удаление ссылки на старый дозорный сигнал и освобождение памяти для него:

Head -> 1 -> 2 -> 3 -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel] -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel] 

Answer 6

Для дальнейшего использования, я должен сказать: после некоторых исследований я обнаружил, что ни один из аргументов, представленных в ответ на этот вопрос, не имеет отношения к делу. Ответ заключается в том, что мы просто решаем, чтобы верхняя часть стека была главой связанного списка (а не хвоста). Это введет небольшое изменение в рутину push, но тогда поп и толчок оба останутся o (1).