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

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

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

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

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

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

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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

Ваш "пустой" список начинается с одного часового

Head -> [Sentinel]

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

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

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

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

Ответ 6

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