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

问题描述

我很好奇为什么从双链表中删除节点比单链表更快.根据我的讲座，与单链表的 O(n) 相比，双链表需要 O(1).根据我的思考过程，我认为它们都应该是 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.

我知道这将与每个节点都有一个指向下一个节点的前一个指针和一个下一个指针的事实相关联，我只是无法理解从 O(1) 的意义上来说，这将是一个常量操作

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.

版本1:假设您想从单链表或双链表中删除包含特定值x 的链表节点，但您不知道它在链表中的哪个位置.在这种情况下，您必须从头开始遍历列表，直到找到要删除的节点.在单链表和双链表中，您都可以在 O(1) 时间内将其删除，因此总体运行时间为 O(n).也就是说，在单向链表中执行删除步骤更难，因为您需要更新前一个单元格中的指针(要删除的单元格未指向该指针)，因此您需要将两个指针存储为你这样做.

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.

版本 2:现在让我们假设您获得了一个指向要删除的单元格的指针，并且需要将其删除.在双向链表中，您可以通过使用 next 和 previous 指针来标识要删除的单元格周围的两个单元格，然后重新连接它们以将单元格从列表中拼接出来.这需要时间 O(1).但是单链表呢?要从列表中删除此单元格，您必须更改出现在要删除的单元格之前的单元格的下一个指针，使其不再指向要删除的单元格.不幸的是，您没有指向该单元格的指针，因为该列表只是单链接的.因此，您必须从列表的开头开始，向下遍历节点，然后找到要删除的节点之前的节点.这需要时间 O(n)，所以在最坏的情况下，移除步骤的运行时间是 O(n)，而不是 O(1).(也就是说，如果您知道两个指针 - 要删除的单元格和它之前的单元格，那么您可以在 O(1) 时间内删除该单元格，因为您不必扫描查找前一个单元格的列表.)

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.)

简而言之:如果您事先知道要删除的单元格，则双向链表可让您在 O(1) 时间内将其删除，而单链表则需要时间 O(n).如果你事先不知道这个单元格，那么这两种情况都是 O(n).

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.

希望这有帮助！

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