51

今天在接受采访时被问到这个问题。

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

4

8 回答 8

48

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

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

一种方法是使删除 API 与要删除的元素的前身一起工作。这反映了插入 API，它采用将成为新元素前身的元素，但它不是很方便，而且很难记录。不过，这通常是可能的。一般来说，您通过遍历列表到达列表中的一个元素。

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

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

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

于 2013-03-22T05:57:19.130 回答
26

这是一些让我更清楚的代码......拥有：

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;
}
于 2015-04-21T14:53:06.943 回答
11

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

  • 您可以在两端准备好访问\插入。

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

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

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

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

于 2013-03-22T05:57:39.330 回答
6

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

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

于 2013-03-22T05:04:24.283 回答
2

'除了回答反转列表以及向前和向后遍历之外，还有一些“基本”的东西'。

似乎没有人提到：在双向链表中，只需拥有一个指向已删除元素的指针，就可以重新插入已删除的元素。参见 Knuth 的 Dancing Links 论文。我认为这是非常基本的。

于 2015-04-21T15:40:59.070 回答
1

  • 因为双向链表可以立即访问列表的开头和结尾，所以它们可以在 O(1) 的任一侧插入数据，也可以在 O(1) 的任一侧删除数据。因为双向链表可以在 O(1) 时间内在末尾插入数据并在 O(1) 时间内从前面删除数据，所以它们为队列提供了完美的底层数据结构。Queeus 是项目列表，其中数据只能在末尾插入并从开头删除。队列是抽象数据类型的一个例子，我们可以在底层使用数组来实现它们。现在，由于队列在末尾插入并从开头删除，因此数组仅与底层数据结构一样好。虽然数组在末尾插入是 O(1)，但从头开始删除是 O(N)。另一方面，双向链表，在末尾插入和从开头删除都是 O(1)。这就是使它非常适合用作队列的底层数据结构的原因。

  • LRU缓存设计中使用了双向链表，因为我们需要经常删除最近最少的项目。删除操作更快。

  • DLL 用于需要前后导航的导航系统。浏览器也使用它来实现被访问网页的后退和前进导航，即后退和前进按钮。

于 2021-11-01T02:48:18.400 回答
0 
Doubly Linked list is more effective than the Singly linked list when the location of the element to be deleted is given.Because it is required to operate on "4" pointers only & "2" when the element to be deleted is at the first node or at the last node.


struct  Node {

       int  Value;
       struct Node  *Fwd;
       struct Node  *Bwd;
);


Only the below line of code will be enough to delete the element ,If the element to be deleted is not in the first or last node.

X->Bwd->Fwd = X->Fwd; X->Fwd->Bwd = X->Bwd ;
于 2019-08-06T05:35:39.360 回答
0

单链表vs双链表vs动态数组：

在比较三种主要数据结构时，在查看时间复杂度时，双向链表在所有主要任务和操作中都是最有效的。对于双向链表，它在所有操作中以恒定时间运行，除了仅按索引访问，它在线性时间 (n) 运行，因为它需要遍历每个节点以获取所需的索引。当涉及到插入、删除、第一个、最后一个、连接和计数时，双向链表以恒定时间运行，而动态数组以线性时间 (n) 运行。

在空间复杂度方面，动态数组只存储元素，因此时间复杂度恒定，单链表存储每个元素的后继，因此线性空间复杂度（n），最糟糕的是双向链表存储每个元素的前驱和后继，因此也是线性空间复杂度，但 (2*n)。

除非您的资源/空间非常有限，否则动态数组或单链表可能会更好，但是，如今，空间和资源越来越丰富，因此双链表以更多空间为代价要好得多。

于 2021-04-22T04:06:57.453 回答