我很好奇为什么从双链表中删除节点比单链表快。根据我的讲座，双链表需要 O(1)，而单链表需要 O(n)。根据我的思考过程，我认为它们都应该是 O(n)，因为你必须遍历可能的所有元素，所以这取决于大小。
我知道这将与每个节点都有一个前一个指针和一个指向下一个节点的下一个指针这一事实相关联，我只是无法理解它在 O(1) 的意义上如何是一个常量操作
问问题
4923 次
2 回答
27
这部分取决于您如何解释设置。这里有两个不同的版本。
版本 1：假设您想从单链表或双链表中删除包含特定值 x 的链表节点，但您不知道它在链表中的位置。在这种情况下，您必须从头开始遍历列表，直到找到要删除的节点。在单链表和双链表中，您都可以在 O(1) 时间内将其删除，因此总体运行时间为 O(n)。也就是说，在单链表中执行删除步骤更加困难，因为您需要更新前一个单元格中的指针（要删除的单元格没有指向该指针），因此您需要将两个指针存储为你来做这件事。
版本 2：现在假设您获得了一个指向要删除的单元格的指针，并且需要将其删除。在双向链表中，您可以通过使用 next 和 previous 指针来识别要删除的单元格周围的两个单元格，然后重新连接它们以将单元格拼接出列表。这需要时间 O(1)。但是单链表呢？要从列表中删除此单元格，您必须更改出现在要删除的单元格之前的单元格的下一个指针，使其不再指向要删除的单元格。不幸的是，您没有指向该单元格的指针，因为该列表只是单链接的。因此，您必须从列表的开头开始，向下遍历节点，然后找到要删除的节点之前的节点。这需要时间 O(n)，所以删除步骤的运行时间在最坏的情况下是 O(n)，而不是 O(1)。（也就是说，如果你知道两个指针 - 您要删除的单元格和它之前的单元格，然后您可以在 O(1) 时间内删除该单元格，因为您不必扫描列表来查找前面的单元格。）
简而言之：如果您事先知道要删除的单元格，则双向链表可以让您在 O(1) 时间内将其删除，而单链表则需要 O(n) 时间。如果您事先不知道单元格，那么在这两种情况下都是 O(n)。
希望这可以帮助！
于 2013-10-08T02:10:03.120 回答
1
为了将前一个节点连接到双链表中的下一个节点，不必遍历该列表。你只需指出
curr.Prev.Next = curr.Next和
curr.Next.Prev = curr.Prev。
在单链表中，必须遍历链表才能找到上一个节点。在未排序的列表中遍历可以是 O(n)。
于 2013-10-08T02:10:56.857 回答