为什么在单个链表中删除O（1）？ [英] Why is deleting in a single linked list O(1)?

问题描述

我不安静理解为什么在单个链接列表的末尾删除在O（1）时间，因为说。

单个链表由节点组成。节点包含某种数据，并引用下一个节点。链表中最后一个节点的引用为空。

  ------------- -  -------------- -------------- 
 |数据|参考| - > |数据|参考| - > ...  - > |数据|参考| 
 -------------- -------------- -------------- 
我确实可以删除O（1）中的最后一个节点。但是在这种情况下，您不要将上一个节点（前一个节点）的引用设置为null，因为它仍然包含对已删除的最后一个节点的引用。所以我想知道他们在运行时分析中是否忽略了？或者它是有意义的，你不必改变，因为参考，嗯，只是指向什么，这样被视为null？ 
 
 
 
因为如果不被忽视，我会认为删除是O（n）。因为你必须遍历整个列表才能到达最后一个节点，并将其引用设置为null。只有在一个双重链接的列表中才会真的是O（1）。
 
 
 
 -edit- 
也许这个观点给出了更多的清晰度。但是我看到删除一个节点成功地删除节点本身并将之前的引用设置为null。
解决方案
我是不知道我在维基百科的文章中看到它可以在O（1）时间内删除单链列表的最后一个条目，但在大多数情况下，该信息是不正确的。给定链接列表中的任何单个节点，总是可以在O（1）时间内通过重新布线围绕该新节点的列表来删除节点。因此，如果您在链表中给出倒数第二个节点的指针，那么可以在O（1）时间内删除列表的最后一个元素。
 
 
 
 ，如果您没有任何额外的指针，除了头指针以外的列表，那么你不能删除列表的最后一个元素，而不扫描到列表的末尾，这将需要&（;）的时间，因为你注意到你绝对是正确的，只要删除最后一个节点，而不用先改变指针就可以了，这将是一个非常糟糕的想法，因为如果你这样做，现有的列表将包含指向一个释放对象的指针。
 
 
 
更一般地说，在单链表中进行插入或删除的代价是O（1），假设在要插入或删除的节点之前有一个指向节点的指针。但是，您可能需要额外的工作（直到Θ（n））才能找到该节点。
 
 
 
希望这有帮助！
 
I do not quiet 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 |
--------------    --------------           --------------
I indeed 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? 

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.
解决方案
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.

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.

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.

Hope this helps!

                        
这篇关于为什么在单个链表中删除O（1）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！