algorithm - 什么时候双向链表比单向链表更高效？

Question

在今天的采访中，有人问我这个问题。

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

Answer 1

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

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

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

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

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

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