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

Question

在今天的一次采访中，我被问到了这个问题。

除了回答倒序和前后遍历外，面试官还不断强调其中的一些“基本点”。我放弃了，当然在面试后做了一些调查。在双链表中插入和删除似乎比单链表更有效。我不太清楚如何才能更有效地使用双链接列表，因为显然需要更改更多的引用。有人能解释背后的秘密吗？老实说，我做了相当多的研究，但未能理解我的主要问题是，仍然需要对双链接列表进行O（n）搜索。

Answer 1

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

>

您已准备好访问\insert的两端。

它可以同时作为队列和堆栈工作。

节点删除不需要额外的指针。

您可以应用爬山遍历，因为您已经可以访问两端。

如果您正在存储数值，并且列表已排序，则可以为中值保留一个指针/变量，然后使用统计方法可以实现高度优化的搜索操作。

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

在单链表中，插入显然是较少的工作，只要您满足于总是在头部或某些已知元素之后插入。也就是说，您不能在已知元素之前插入，但请参阅下文。）

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

实现这一点的一种方法是使deleteapi与要删除的元素的前一个一起工作。这反映了insertapi，它采用的元素将是新元素的前身，但它不是很方便，而且很难记录。不过，这通常是可能的。一般来说，您通过遍历列表来获得列表中的元素。

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

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

如果删除并不重要，可能是因为数据结构是不可变的，那么单链表提供了另一个真正有用的特性：它们允许结构共享。一个单链表很可能是多个头的尾巴，这对于一个双链表来说是不可能的。因此，单链表传统上是函数式语言选择的简单数据结构。