为什么在单个链表中删除 O(1)? [英] Why is deleting in a single linked list O(1)?
问题描述
我不太明白为什么在单个链表末尾删除会在 O(1) 时间内进行，因为 维基百科文章说.
I do not quite understand why deleting at the end of a single linked list goes in O(1) time, as the wikipedia article says.
一个链表由多个节点组成.一个节点包含某种数据，以及对下一个节点的引用.链表最后一个节点的引用为空.
A single linked list consists out of nodes. A node contains some kind of data, and a reference to the next node. The reference of the last node in the linked list is null.
-------------- -------------- --------------
| data | ref | -> | data | ref | -> ... -> | data | ref |
-------------- -------------- --------------
我可以删除 O(1) 中的最后一个节点.但是在这种情况下，您不要将新的最后一个节点(前一个节点)的引用设置为 null，因为它仍然包含对已删除的最后一个节点的引用.所以我想知道，他们在运行时间分析中是否忽略了这一点?或者是否认为您不必更改它，因为引用只是指向任何内容，而这被视为空值?
I can remove the the last node in O(1). But in that case you don't set the reference of the newly last node, the previous one, to null since it still contains the reference to the deleted last node. So I was wondering, do they neglect that in the running time analysis? Or is it consired that you don't have to change that since the reference, well, just points to nothing, and such is seen as null?
因为如果它不被忽视，我会争辩说删除是 O(n).由于您必须遍历整个列表才能到达新的最后一个节点并将其引用也设置为 null.只有在双链表中，它才是真正的 O(1).
Because if it would not be neglected I would argue that deleting is O(n). Since you have to iterate over the whole list to get to the newly last node and set its reference also to null. Only in a double linked list it would be really O(1).
-编辑-也许这个观点更能说明问题.但是我看到删除节点"成功删除节点本身并将先前的引用设置为空.
-edit- Maybe this point of view gives some more clearence. But I see "deletion of a node" as succesfully deleting the node itself and setting the previous reference to null.
推荐答案
我不确定我在维基百科文章中看到它说可以在 O(1) 时间内删除单向链表的最后一个条目，但该信息在大多数情况下是不正确的.给定链表中的任何单个节点，总是可以通过在新节点周围重新连接链表，在 O(1) 时间内删除它后面的节点.因此，如果你得到一个指向链表中倒数第二个节点的指针，那么你可以在 O(1) 时间内删除链表的最后一个元素.
I am not sure I see in the Wikipedia article where it says that it's possible to remove the last entry of a singly-linked list in O(1) time, but that information is incorrect in most cases. Given any individual node in a linked list, it is always possible to remove the node after it in O(1) time by rewiring the list around that new node. Consequently, if you were given a pointer to the penultimate node in a linked list, then you could delete the last element of the list in O(1) time.
然而，如果除了头指针之外没有任何额外的指向列表的指针，那么你不能在不扫描到列表末尾的情况下删除列表的最后一个元素，这将需要 Θ(n) 时间，正如您所指出的.您完全正确，只是删除最后一个节点而不先将指针更改为它是一个非常糟糕的主意，因为如果您要这样做，现有列表将包含一个指向已释放对象的指针.
However, if you didn't have any extra pointers into the list other than a head pointer, then you could not delete the last element of the list without scanning to the end of the list, which would require Θ(n) time, as you have noted. You are absolutely correct that just deleting the last node without first changing the pointers into it would be a Very Bad Idea, since if you were to do this the existing list would contain a pointer to a deallocated object.
更一般地 - 在单链表中进行插入或删除的成本是 O(1)，假设您有一个指向要插入或删除的节点之前的节点的指针.但是，您可能需要做额外的工作(最多 Θ(n))才能找到该节点.
More generally - the cost to do an insertion or deletion in a singly-linked list is O(1), assuming you have a pointer to the node right before the one you want to insert or delete. However, you might have to do extra work (up to Θ(n)) to find that node.
希望这有帮助！
这篇关于为什么在单个链表中删除 O(1)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
