为什么要从双链表中删除节点比从单链表中删除节点更快？ [英] Why is removing a node from a doubly-linked list faster than removing a node from a singly-linked list?

问题描述

我很好奇为什么从双链表中删除一个节点比单个链接更快。根据我的演讲，对于单个链接，O（1）与O（n）相比，需要O（1）。根据我的思维过程，我认为他们都应该是O（n），因为你必须遍历可能的所有元素，这取决于大小。

我明白它将与每个节点具有先前的指针和下一个指向下一个节点的事实相关联，我只是无法理解在O（1）的意义上它将是一个常量运算

解决方案

这部分取决于你如何解释设置。这里有两个不同的版本。

版本1：假设要从单个或双向链接列表中删除包含特定值x的链接列表节点，但是你不知道列表中的哪里。在这种情况下，您必须从头开始遍历列表，直到找到要删除的节点。在单列和双向列表中，您可以在O（1）时间内删除它，因此整个运行时是O（n）。也就是说，单击链接列表中的删除步骤很困难，因为您需要更新上一个单元格中的指针（该单元格不指向要删除的指针），因此需要将两个指针存储为你这样做。

版本2：现在让我们假设你给了一个指针去除单元格，需要删除它。在双向链表中，您可以通过使用下一个和上一个指针来识别单元格周围的两个单元格，从而删除它们，然后重新布线它们将单元格从列表中拼出。这需要时间O（1）。但是单链表呢？要从列表中删除此单元格，您必须更改显示在要删除的单元格之前的单元格的下一个指针，以使其不再指向要删除的单元格。不幸的是，您没有指向该单元格的指针，因为列表仅单独链接。因此，您必须从列表的开始处开始，跨越节点向下移动，并找到要删除的节点。这需要时间O（n），所以删除步骤的运行时间在最坏的情况下是O（n），而不是O（1）。 （也就是说，如果你知道两个指针 - 要删除的单元格和单元格正好在之前，那么您可以在O（1）时间内删除单元格，因为您不必扫描简单来说：如果您提前知道要移除的单元格，双向链表可以及时将其删除O（ 1），而单链表将需要时间O（n）。如果你不知道这个细胞，那么在这两种情况下都是O（n）。

希望这有帮助！

I was curious why deleting a node from a double linked list is faster than a single linked. According to my lecture, it takes O(1) for a double linked list compared to O(n) for a single linked. According to my thought process, I thought they both should be O(n) since you have to traverse across possibly all the elements so it depends on the size.

I understand it's going be associated with the fact that each node has a previous pointer and a next pointer to the next node, I just can't understand how it would be a constant operation in the sense of O(1)

解决方案

This partially depends on how you're interpreting the setup. Here are two different versions.

Version 1: Let's suppose that you want to delete a linked list node containing a specific value x from a singly or doubly-linked list, but you don't know where in the list it is. In that case, you would have to traverse the list, starting at the beginning, until you found the node to remove. In both a singly- and doubly-linked list, you can then remove it in O(1) time, so the overall runtime is O(n). That said, it's harder to do the remove step in the singly-linked list, since you need to update a pointer in the preceding cell (which isn't pointed at by the cell to remove), so you need to store two pointers as you do this.

Version 2: Now let's suppose you're given a pointer to the cell to remove and need to remove it. In a doubly-linked list, you can do this by using the next and previous pointers to identify the two cells around the cell to remove and then rewiring them to splice the cell out of the list. This takes time O(1). But what about a singly-linked list? To remove this cell from the list, you have to change the next pointer of the cell that appears before the cell to remove so that it no longer points to the cell to remove. Unfortunately, you don't have a pointer to that cell, since the list is only singly-linked. Therefore, you have to start at the beginning of the list, walk downwards across the nodes, and find the node that comes right before the one to remove. This takes time O(n), so the runtime for the remove step is O(n) in the worst case, rather than O(1). (That said, if you know two pointers - the cell you want to delete and the cell right before it, then you can remove the cell in O(1) time since you don't have to scan the list to find the preceding cell.)

In short: if you know the cell to remove in advance, the doubly-linked list lets you remove it in time O(1) while a singly-linked list would require time O(n). If you don't know the cell in advance, then it's O(n) in both cases.

Hope this helps!

这篇关于为什么要从双链表中删除节点比从单链表中删除节点更快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！