为什么要删除单个链表O(1)？

Question

我不清楚理解为什么在单个链表的末尾删除在O(1)时间内,正如维基百科的文章所说.

单个链表由节点组成.节点包含某种数据,以及对下一个节点的引用.链表中最后一个节点的引用为null.

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

我确实可以删除O(1)中的最后一个节点.但是在这种情况下,您不会将新最后一个节点(前一个节点)的引用设置为null,因为它仍包含对已删除的最后一个节点的引用.所以我想知道他们在运行时分析中是否忽略了这一点？或者它是否被认为你不必改变它,因为引用,好吧,只是指向什么,并且这被视为null？

因为如果它不会被忽略,我会认为删除是O(n).因为您必须遍历整个列表才能到达新的最后一个节点并将其引用也设置为null.只有在双链表中,它才真正是O(1).

-edit-也许这种观点会让人更加清晰.但我看到"删除节点"成功删除节点本身并将先前的引用设置为null.

Answer 1

我不确定我在维基百科的文章中看到它可以在O(1)时间内删除单链表的最后一个条目,但在大多数情况下该信息是不正确的.给定链表中的任何单个节点,通过在该新节点周围重新布线列表,总是可以在O(1)时间之后删除其后的节点.因此,如果给了一个指向链表中倒数第二个节点的指针,那么你可以在O(1)时间内删除列表的最后一个元素.

但是,如果你没有任何额外的指针进入列表而不是头指针,那么你不能删除列表的最后一个元素而不扫描到列表的末尾,这将需要Θ(n)时间,如你注意到了.你是绝对正确的,只是删除最后一个节点而不先将指针更改为它是一个非常糟糕的主意,因为如果你这样做,现有的列表将包含一个指向解除分配对象的指针.

更一般地说 - 在单个链接列表中进行插入或删除的成本是O(1),假设您在要插入或删除的节点之前有一个指向节点的指针.但是,您可能需要做额外的工作(最多Θ(n))才能找到该节点.

希望这可以帮助!

Answer 2

在任何位置添加/删除ANY节点是O(1).代码只是以固定成本(少量指针计算和malloc/frees)来添加/删除节点.对于任何特定情况,这种算术成本是固定的.

但是,达到(索引)所需节点的成本是O(n).

本文仅列出多个子类别中的添加/删除(在中间,开头,结尾添加),以显示在中间添加的成本与在开头/结尾添加的成本不同(但相应的成本仍然是固定的).