一尘不染

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

algorithm

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

除了回答反转列表以及前后遍历之外,访调员还不断强调其中的一些“基本原理”。我放弃了,当然在面试之后做了一些研究。似乎在双链表中插入和删除比单链表更有效。我不太确定双向链接列表的效率如何,因为很明显,需要更改更多引用。谁能解释其背后的秘密?老实说,我做了很多研究,但我的主要麻烦是,对于双链表仍然需要O(n)搜索这一事实,使我无法理解。


阅读 534

收藏
2020-07-28

共1个答案

一尘不染

只要您愿意始终插入到开头或某个已知元素之后,插入显然不会在单链列表中工作。(也就是说,您不能在已知元素之前插入,但请参见下文。)

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

一种方法是使Delete
API与要删除的元素的前任一起使用。这反映了插入API,该API接受将成为新元素的前身的元素,但是它不是很方便,并且很难记录。通常,这是可能的。一般来说,您可以通过遍历列表来到达列表中的元素。

当然,您可以从头开始搜索列表,以找到要删除的元素,从而知道其前身是什么。假定delete API包含列表的开头,这也是不方便的。而且,搜索速度非常慢。

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

如果删除不重要,也许是因为数据结构是不可变的,则单链接列表提供了另一个真正有用的属性:它们允许结构共享。单链列表可以很高兴地成为多个头的尾部,而双链列表则不可能。因此,单链列表传统上一直是功能语言选择的简单数据结构。

2020-07-28