什么时候双链表比单链表更有效？
今天在一次采访中，我被问到了这个问题。
除了回答反转列表以及前后遍历之外，访调员还不断强调其中的一些“基本原理”。我放弃了，当然在面试之后做了一些研究。似乎在双链表中插入和删除比单链表更有效。我不太确定双向链接列表的效率如何，因为很明显，需要更改更多引用。谁能解释其背后的秘密？老实说，我做了很多研究，但我的主要麻烦是，对于双链表仍然需要O（n）搜索这一事实，使我无法理解。
回答：
只要您愿意始终插入到开头或某个已知元素之后，插入显然不会在单链列表中工作。（也就是说，您不能在已知元素之前插入，但请参见下文。）
另一方面，删除则比较棘手，因为您需要在要删除的元素之前先知道该元素。
一种方法是使Delete
API与要删除的元素的前任一起使用。这反映了插入API，该API接受将成为新元素的前身的元素，但是它不是很方便，并且很难记录。通常，这是可能的。一般来说，您可以通过遍历列表来到达列表中的元素。
当然，您可以从头开始搜索列表，以找到要删除的元素，从而知道其前身是什么。假定delete API包含列表的开头，这也是不方便的。而且，搜索速度非常慢。
几乎没有人使用，但实际上非常有效的方法是，将单链接列表迭代器定义为指向迭代器当前目标之前的元素的指针。这很简单，只有一个间接操作要比直接使用指向元素的指针慢，并且可以快速插入和删除。缺点是删除元素可能会使其他迭代器无效以列出元素，这很烦人。（它不会使迭代器对要删除的元素无效，这对于删除某些元素的遍历很有用，但是补偿并不多。）
如果删除不重要，也许是因为数据结构是不可变的，则单链接列表提供了另一个真正有用的属性：它们允许结构共享。单链列表可以很高兴地成为多个头的尾部，而双链列表则不可能。因此，单链列表传统上一直是功能语言选择的简单数据结构。
以上是 什么时候双链表比单链表更有效？ 的全部内容， 来源链接： utcz.com/qa/418678.html
