在今天接受采访时我被问的问题。

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.

这样做的一种方法是使与元件的predecessor删除的API工作被删除。这反映了插入的API，这需要这将是新元素的predecessor的元素，但它不是很方便，很难记录。它通常是可能的，但。一般来说，你在元素列表中的到达通过遍历列表

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.

当然，你可以只搜索列表中从一开始就找到要删除的元素，让你知道它的predecessor了。该假定的删除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.

这几乎没有人使用，但它实际上是pretty的有效的方法是定义一个单链表的迭代器是指针元素preceding迭代器的当前目标。这是简单的，仅一个间接比直接使用一个指向元件慢，使得无论插入和删除快。不足之处是删除一个元素可能违反其他迭代器列表元素，这是烦人。 （它不会被删除的迭代器的元素，这是很好的遍历它删除某些内容无效，但这不是赔偿多少。）

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.