什么时候双向链表比单链表更有效？

Question

在今天的一次面试中，我被问到这个问题。

除了回答、颠倒列表和向前和向后遍历之外，面试官还不断强调其中有一些“基本”的东西。我放弃了，当然在面试后做了一些研究。在双向链表中插入和删除似乎比单链表更有效。我不太确定如何才能更有效地使用双向链表，因为很明显需要更改更多的引用。有人能解释一下背后的秘密吗？老实说，我做了相当多的研究，但未能理解我的主要问题是，双向链表仍然需要O(n)搜索。

Answer 1

在单链表中插入显然是较少的工作，只要您满足于总是在某个已知元素的开头或后面插入即可。(也就是说，您不能在已知元素之前插入，但请参见下文。)

另一方面，删除更为棘手，因为您需要在删除元素之前知道该元素。

执行此操作的一种方法是使delete API与要删除的元素的前置元素一起工作。这反映了插入API，该API接受将作为新元素的前置元素的元素，但它不是很方便，并且很难记录。不过，这通常是可能的。一般而言，您通过遍历列表到达列表中的元素。

当然，您可以从头开始搜索列表以找到要删除的元素，这样您就可以知道它的前身是什么。这假设删除API包括列表的头部，这也很不方便。此外，搜索的速度也慢得离谱。

几乎没有人使用的方法是定义一个单链接列表迭代器，作为指向迭代器当前目标之前的元素的指针，但这种方法实际上非常有效。这很简单，只比直接使用指向元素的指针慢一个间接的速度，并且使得插入和删除都很快。缺点是删除一个元素可能会使列表元素的其他迭代器失效，这很烦人。(它不会使要删除的元素的迭代器失效，这对于删除一些元素的遍历来说很好，但这不是很好的补偿。)

如果删除并不重要，也许是因为数据结构是不可变的，那么单链表提供了另一个真正有用的属性:它们允许结构共享。单链表可以很高兴地成为多个头部的尾部，这对于双向链表来说是不可能的。出于这个原因，单链表一直是函数式语言选择的简单数据结构。

Answer 2

下面是一些代码，它们让我更清楚……拥有：

class Node{
      Node next;
      Node prev;
}

删除单个链表中的节点 -O(n)-

您不知道前一个节点是哪个，所以您必须遍历列表，直到找到它：

deleteNode(Node node){
    prevNode = tmpNode;
    tmpNode = prevNode.next;

    while (tmpNode != null) {
        if (tmpNode == node) {
            prevNode.next = tmpNode.next;
        }
        prevNode = tmpNode;
        tmpNode = prevNode.next;
    }
}

删除双向链表中的节点 -O(1)-

您可以像这样简单地更新链接：

deleteNode(Node node){
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

Answer 3

以下是我对双向链表的看法：

• 您可以随时访问\插入两端。
• 它可以同时作为队列和堆栈工作。
• 节点删除不需要额外的指针。
• 您可以应用爬山遍历，因为您已经在两端都具有访问权限。
• 如果您正在存储数值，并且列表已排序，您可以保留一个指针/变量作为中位数，然后使用统计方法实现高度优化的搜索操作。

F211