22

正如维基百科文章所说，我不太明白为什么在单个链表末尾删除会在 O(1) 时间内进行。

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

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

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

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

-edit- 也许这种观点给出了一些更清晰的信息。但我将“删除节点”视为成功删除节点本身并将先前的引用设置为空。

4

8 回答 8

42

我不确定我是否在 Wikipedia 文章中看到它说可以在 O(1) 时间内删除单链表的最后一个条目，但在大多数情况下该信息是不正确的。给定链表中的任何单个节点，始终可以通过围绕该新节点重新连接链表，在 O(1) 时间内删除该节点之后的节点。因此，如果给你一个指向链表中倒数第二个节点的指针，那么你可以在 O(1) 时间内删除链表的最后一个元素。

但是，如果除了头指针之外没有任何额外的指向列表的指针，那么您不能在不扫描到列表末尾的情况下删除列表的最后一个元素，这将需要 Θ(n) 时间，因为你已经注意到了。您绝对正确，仅删除最后一个节点而不首先更改指向它的指针将是一个非常糟糕的主意，因为如果您要这样做，现有列表将包含指向已释放对象的指针。

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

希望这可以帮助！

于 2012-12-27T01:11:22.933 回答
8

在任何位置添加/删除任何节点都是 O(1)。代码只是使用固定成本（很少的指针计算和 malloc/frees）来添加/删除节点。对于任何特定情况，此算术成本都是固定的。

但是，到达（索引）所需节点的成本是 O(n)。

文章只是列出了多个子类（中间、开头、结尾的添加）的添加/删除，以表明中间添加的成本与开头/结尾的添加成本不同（但各自的成本仍然是固定的）。

于 2012-12-27T01:08:38.587 回答
0

O(1) 仅表示“恒定成本”。这并不意味着 1 次操作。这意味着“至多 C”操作，无论其他参数如何变化（例如列表大小），C 都是固定的。事实上，在有时令人困惑的 big-Oh 世界中：O(1) == O(22)。

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

于 2012-12-27T01:11:35.603 回答
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]
于 2012-12-31T09:21:54.613 回答
0

为了将来参考，我必须说，经过一些研究，我发现为回答这个问题而提供的所有论点都不相关。答案是我们简单地决定堆栈的顶部是链表的头部（而不是尾部）。这将在 push 例程中引入轻微的变化，但 pop 和 push 都将保持 o(1)。

于 2016-06-01T04:49:01.693 回答
0

如果您在单个链表中给出要删除的节点的指针，那么您可以通过简单地将下一个节点复制到要删除的节点上来在恒定时间内删除该节点。

M pointer to node to delete
M.data=M.next.data
M.next=M.next.next

否则，如果您需要搜索节点，那么您不能做得比 O(n) 更好

于 2018-03-29T20:05:36.043 回答
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

唉，这会重新排序列表，并移动值，这对您的应用程序可能合适，也可能不合适。

于 2018-06-30T02:03:41.813 回答
-1

例如，您可以有一个指向 last 之前的元素（“倒数第二个”）的指针，并且在删除时： 1. 删除此“倒数第二个”元素的 *next。2. 将此“倒数第二个”*next 设置为 NULL

于 2012-12-27T01:10:30.330 回答