logo标签列表

为什么在单向链表中删除操作的时间复杂度为O(1)？

data-structureslinked-listsingly-linked-list
23

我不太明白为什么单向链表在末尾删除时可以在O(1)时间内完成，正如维基百科文章所说。

一个单向链表由节点组成。每个节点包含某种数据和对下一个节点的引用。连接列表中最后一个节点的引用为null。

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

我可以在O(1)的时间内删除最后一个节点。但是这种情况下，由于先前的节点仍然包含对已删除的最后一个节点的引用，因此您不会将新的最后一个节点的引用设置为null。所以我想知道，在运行时间分析中他们是否忽略了这一点？或者说您不必更改它，因为该引用指向了空，这被视为null？

因为如果不忽略这一点，我认为删除的时间复杂度是O(n)。因为您必须遍历整个列表才能到达新的最后一个节点并将其引用设置为null。只有在双向链表中，删除才真正是O(1)的。

-编辑-

也许这个观点可以更清楚地说明问题。但是我认为“删除一个节点”应该成功删除节点本身并将前一个引用设置为null。

2
我在那篇维基百科文章中看到了两个关于O(1)的引用，但它们都没有说明从单向链表中删除最后一个节点是一个O(1)操作。假设在尝试删除时，您已经持有指向前一个节点的指针，这对于删除除第一个节点以外的任何节点都是必需的。 - Robert Harvey
8个回答
46

我不确定在维基百科的文章中是否提到过单链表中可以在O(1)时间内删除最后一个元素，但是这个信息大多数情况下都是不正确的。对于链表中的任何节点，通过重新连接指向该新节点的列表，总是可以在O(1)时间内删除其后面的节点。因此，如果您拥有一个指向单链表中倒数第二个节点的指针，那么您可以在O(1)时间内删除链表的最后一个元素。

然而，如果除了头指针之外没有额外的指向列表的指针，则无法在不扫描整个列表的情况下删除列表的最后一个元素，这将需要 Θ(n) 时间，正如您所指出的一样。您绝对正确，如果只是删除最后一个节点而不先更改指向它的指针，那么这将是一个非常糟糕的想法，因为这样做会导致现有的列表包含指向已释放对象的指针。

更普遍地说，假设您有一个指向要插入或删除的节点之前的节点的指针，在单链表中执行插入或删除的成本为O(1)。然而，您可能需要做额外的工作（最多需要 Θ(n)）来找到该节点。

希望这可以帮助您！

9
在任何位置添加/删除任何节点的时间复杂度为O(1)。代码只需要进行固定的开销（一些指针计算和malloc/frees）来添加/删除节点。这种算术成本对于任何特定情况都是固定的。
然而，到达（索引）所需节点的成本为O(n)。
本文仅列举了多个子类别中的添加/删除（在中间、开头、结尾添加）以显示在中间添加的成本与在开头/结尾添加的成本不同（但各自的成本仍然是固定的）。
我仍然不太确定我是否正确理解了它。您认为删除只是删除节点O(1)，而不是将前一个节点的引用设置为null，O(n)，“到达所需节点的成本”？我认为删除是删除节点本身并将前一个节点的引用设置为null。 - WG-
我不明白你为什么批准了这个答案，它几乎没有解释多少。如果我将要删除的节点和它的下一个节点的指针都设置为空，那么我就会得到一个损坏的列表。我可能已经把我的列表分成了两部分。这样算是合适的删除吗？除非假定删除是删除下一个节点。我需要一个进入具体细节的解释。索引是O(n)，但如果删除需要索引，它应该是用例的一部分。也就是说，如果我在单链表上调用Delete方法，我必须期望O(n)的时间复杂度。 - Didier A.
0
如果您在单链表中给出要删除的节点的指针，则可以通过将下一个节点复制到要删除的节点上来在常数时间内删除此节点。
M pointer to node to delete
M.data=M.next.data
M.next=M.next.next

否则，如果您需要搜索节点，则无法做得比O(n)更好。
0

是的，即使您没有维护“前一个元素”的指针，也可以在O(1)时间内完成此操作。

假设您有这个列表，其中“head”和“tail”是静态指针，“End”是标记为结束的节点。您可以像平常一样使用“next == NULL”，但在这种情况下，您必须忽略该值：

head -> 1 -> 2 -> 3 -> 4 -> 5 -> End <- tail

现在，您有一个指向节点3的指针，但没有它的前一个节点。您也有头和尾指针。以下是一些类似Python的代码，假设有一个SingleLinkedList类。

class SingleLinkedList:

    # ... other methods

    def del_node(self, node):  # We "trust" that we're only ever given nodes that are in this list.
        if node is self.head:
            # Simple case of deleting the start
            self.head = node.next
            # Free up 'node', which is automatic in python
        elif node.next is self.tail
            # Simple case of deleting the end. This node becomes the sentinel
            node.value = None
            node.next = None
            # Free up 'self.tail'
            self.tail = node
        else:
            # Other cases, we move the head's value here, and then act
            # as if we're deleting the head.
            node.value = self.head.value
            self.head = self.head.next
            new_head = self.head.next
            # Free up 'self.head'
            self.head = new_head

哎呀，这会重新排序列表，并移动值，这可能对您的应用程序有利也可能不利。

0
如果您要包括修复悬挂节点的成本，您仍然可以使用末尾的哨兵节点（也在该页面上描述）以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]
我喜欢这个。它可以使时间复杂度为O（1），同时引入空间交换，但它会保持空间复杂度为O（n）。显然，就像你所说的那样，你偶尔需要进行O（n）操作来清理列表，否则你可能会遇到内存问题。 - Didier A.
当您有一个更长的列表时，您可能会发现算法不起作用。如果您有“头 - > 1 - > 2 - > 3 - > 4 - > 5 - > 哨兵”，然后删除节点3，您可以正确地执行此操作吗？ - Chris Cogdon
0

O(1)简单地意味着“恒定成本”。这并不意味着一次操作。它意味着执行“最多C”个操作，其中C是固定的，无论其他参数如列表大小发生如何变化。事实上，在有时令人困惑的大O世界中：O(1)==O(22)。

相比之下，删除整个列表的成本是O(n)，因为成本随列表的大小(n)而变化。

2
删除整个列表的时间复杂度为O(1)。清空整个列表的时间复杂度为O(n)。 - Didier A.
0

为了以后参考，我必须说经过一些研究，我发现对于这个问题提供的所有参数都不相关。答案是我们只需决定将堆栈顶部设置为链表的头部（而不是尾部）。这将在推送例程中引入轻微更改，但是弹出和推送都将保持o（1）。

-1
例如，您可以拥有指向倒数第二个元素（“倒数第二个”）的指针，并在删除时执行以下操作： 1. 删除此“倒数第二个”元素的*next。 2. 将此“倒数第二个”*next设置为NULL。
除此之外，如果您正在保留“倒数第二个”指针，则现在必须更新该指针。 - James
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接