何时双链表比单链表更有效？

Question

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

除了回答清单以及向前和向后遍历之外,还有一些"基本面",面试官一直在强调.我放弃了,当然在采访后做了一些研究.似乎插入和删除在双链表中比单链表更有效.我不太确定如何对双链表更有效,因为很明显需要更多的引用才能改变.任何人都可以解释背后的秘密吗？我老老实实地进行了相当多的研究,并且无法理解我的主要麻烦是双链表仍然需要进行O(n)搜索.

Answer 1

只要您满足于总是插入头部或在某个已知元素之后插入,那么插入在单链表中显然不那么重要.(也就是说,您不能在已知元素之前插入,但请参见下文.)

另一方面,删除比较棘手,因为您需要在要删除的元素之前知道元素.

执行此操作的一种方法是使删除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

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

• 您可以在两端准备好访问\ insert.

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

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

• 您可以应用Hill-Climb遍历,因为您已经可以访问两端.

• 如果要存储数值,并且列表已排序,则可以保留中位数的指针/变量,然后使用统计方法可以非常优化搜索操作.

Answer 4

如果要删除链接列表中的元素,则需要将前一个元素链接到下一个元素.使用双向链表,您可以随时访问这两个元素,因为您可以链接到这两个元素.

这假设您已经有一个指向需要删除的元素的指针,并且不涉及搜索.