问题描述
在今天的一次采访中，我被问到了这个问题.
In an interview today I got asked the question.
除了回答反转列表和向前和向后遍历之外，面试官一直强调其中的一些基本".我放弃了，当然面试后做了一些研究.似乎双链表中的插入和删除比单链表更有效.我不太确定如何使双向链表更有效，因为很明显需要更改更多引用.谁能解释一下背后的秘密?老实说，我做了很多研究，但未能理解我的主要问题是双链表仍然需要 O(n) 搜索.
Apart from answering reversing the list and both forward and backward traversal there was something "fundamental" in it that the interviewer kept stressing. I gave up and of course after interview did a bit of research. It seems that insertion and deletion are more efficient in doubly linked list than singly linked list. I am not quite sure how it can be more efficient for a doubly linked list since it is obvious that more references are required to change.Can anybody explain the secret behind? I honestly did a quite a bit of research and failed to understand with my main trouble being the fact that a O(n) searching is still needed for the double linked list.
推荐答案
在单向链表中插入显然工作量较小，只要您满足于始终插入在头部或某些已知元素之后即可.(也就是说，您不能在已知元素之前插入，但请参见下文.)
Insertion is clearly less work in a singly-linked list, as long as you are content to always insert at the head or after some known element. (That is, you cannot insert before a known element, but see below.)
另一方面，删除比较棘手，因为您需要在要删除的元素之前知道元素.
Deletion, on the other hand, is trickier because you need to know the element before the element to be deleted.
这样做的一种方法是使删除 API 与要删除的元素的前身一起工作.这反映了插入 API，它采用将成为新元素的前身的元素，但它不是很方便并且难以记录.不过，这通常是可能的.一般来说，你通过遍历列表来到达列表中的元素.
One way of doing this is to make the delete API work with the predecessor of the element to be deleted. This mirrors the insert API, which takes the element which will be the predecessor of the new element, but it's not very convenient and it's hard to document. It's usually possible, though. Generally speaking, you arrive at an element in a list by traversing the list.
当然，你可以从头开始搜索列表，找到要删除的元素，这样你就知道它的前身是什么了.那假设删除 API 包括列表的头部，这也很不方便.此外，搜索速度非常慢.
Of course, you could just search the list from the beginning to find the element to be deleted, so that you know what its predecessor was. That assumes that the delete API includes the head of the list, which is also inconvenient. Also, the search is stupidly slow.
几乎没有人使用但实际上非常有效的方法是定义一个单链表迭代器作为指向迭代器当前目标之前元素的指针.这很简单，只有一个间接比使用直接指向元素的指针慢，并且使得插入和删除都很快.缺点是删除一个元素可能会使其他迭代器无效以列出元素，这很烦人.(它不会使被删除元素的迭代器失效，这对于删除一些元素的遍历来说很好，但这并没有多少补偿.)
The way that hardly anyone uses, but which is actually pretty effective, is to define a singly-linked list iterator to be the pointer to the element preceding the current target of the iterator. This is simple, only one indirection slower than using a pointer directly to the element, and makes both insertion and deletion fast. The downside is that deleting an element may invalidate other iterators to list elements, which is annoying. (It doesn't invalidate the iterator to the element being deleted, which is nice for traversals which delete some elements, but that's not much compensation.)
如果删除不重要，也许是因为数据结构是不可变的，单链表提供了另一个非常有用的特性:它们允许结构共享.单向链表可以愉快地成为多个头的尾部，这对于双向链表是不可能的.出于这个原因，单链表传统上一直是函数式语言选择的简单数据结构.
If deletion is not important, perhaps because the datastructures are immutable, singly-linked lists offer another really useful property: they allow structure-sharing. A singly-linked list can happily be the tail of multiple heads, something which is impossible for a doubly-linked list. For this reason, singly-linked lists have traditionally been the simple datastructure of choice for functional languages.
这篇关于什么时候双链表比单链表更有效?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！