.net 微软问：单列还是双列？使用每种方法的优缺点是什么？

Microsoft Asks: Singly List or Doubly List? What are the pros and cons of using each?

提问by Tarik

I am asked such question and I have my own sayings but I am not really sure what to say about cons and pros? Microsoft asked this question to one of its candidates.

我被问到这样的问题，我有自己的说法，但我真的不确定要说些什么关于利弊？微软向其中一位候选人提出了这个问题。

Singly linked list allows you to go one way direction. Whereas doubly linked list has two way direction next and previous.

单向链表可以让你往一个方向走。而双向链表有下一个和上一个两个方向。

Here is a good picture which draws the Singly and Doubly LinkedLists.

这是一张很好的图片，它绘制了单链表和双链表。

However, how do you explain the pros and cons of these items in more orderly fashion?

但是，您如何以更有序​​的方式解释这些项目的优缺点？

回答by coder0h1t

Although this question has already been answered, I am somehow not satisfied with the answer (no offense meant), so here's how I would reply to it:

虽然已经回答了这个问题，但我对答案并不满意（没有冒犯的意思），所以我将如何回答：

What to use - Singly or Doubly linked list depends on what you intend to achieve and system limitations, if any.

使用什么 - 单链表或双链表取决于您打算实现的目标和系统限制（如果有）。

Singly-linked list:

单链表：

Pros: Simple in implementation, requires relatively lesser memory for storage, assuming you need to delete/insert (at) next node – deletion/insertion is faster.

优点：实现简单，需要相对较少的存储内存，假设您需要删除/插入（在）下一个节点 - 删除/插入更快。

Cons: Cannot be iterated in reverse, need to maintain a handle to the head node of the list else, the list will be lost in memory. If you're deleting previous node or inserting at previous node, you will need to traverse list from head to previous node to be able to carry out those operations – O(N) time.

缺点：不能反向迭代，需要维护链表头节点的句柄，否则链表会在内存中丢失。如果您要删除前一个节点或在前一个节点插入，则需要从头到前一个节点遍历列表才能执行这些操作 - O(N) 时间。

--So, this should be used when you have lesser memory and your main goal is insertion/deletion and not searching elements.

--因此，当您的内存较少并且您的主要目标是插入/删除而不是搜索元素时，应该使用它。

Doubly-linked list:

双向链表：

Pros: Can be iterated in forward as well as reverse direction. In case of needing to delete previous node, there is no need to traverse from head node, as the node to be deleted can be found from ‘.previous' pointer.

优点：可以正向和反向迭代。在需要删除前一个节点的情况下，不需要从头节点开始遍历，因为可以从'.previous'指针中找到要删除的节点。

Cons: Relatively complex to implement, requires more memory for storage (1 ‘.previous' pointer per node). Insertions and deletions are relatively more time consuming (assigning/reassigning ‘.previous' pointer for neighbor nodes)

缺点：实现相对复杂，需要更多内存来存储（每个节点 1 个“.previous”指针）。插入和删除相对更耗时（为邻居节点分配/重新分配'.previous'指针）

--This should be used when you have no or minimal limitations on memory, and your main goal is to search for elements.

--当您对内存没有限制或限制很少时，应该使用它，并且您的主要目标是搜索元素。

If there are some more pros and cons to any, please feel free to add, reply in comments. Thanks!

如果有更多的优缺点，请随时补充，在评论中回复。谢谢！

回答by Reed Copsey

I am asked such question and I have my own sayings but I am not really sure what to say about cons and pros?

我被问到这样的问题，我有自己的说法，但我真的不确定要说些什么关于利弊？

It all comes down to usage. There's a trade off here.

这一切都归结为使用。这里有一个权衡。

Singly linked list is simpler in terms of implementation, and typically has a smaller memory requirement as it only needs to keep the forward member referencing in place.

单链表在实现方面更简单，并且通常具有较小的内存需求，因为它只需要保持前向成员引用就位。

Doubly linked list has more efficient iteration, especially if you need to ever iterate in reverse (which is horribly inefficient with a single linked list), and more efficient deletion of specific nodes.

双向链表具有更高效的迭代，尤其是当您需要反向迭代时（单链表效率极低），并且更有效地删除特定节点。

That being said - since you have this tagged .NET, double linked lists also have the advantage of being directly in the framework in the form of the LinkedList<T>class. This provides a huge advantage in that you don't have to implement, test, and maintain your own collection class.

话虽如此 - 因为你有这个标记的 .NET，所以双链表也有直接以LinkedList<T>类的形式存在于框架中的优势。这提供了一个巨大的优势，因为您不必实现、测试和维护自己的集合类。

回答by dasblinkenlight

While singly linked list uses less memory per node (one pointer vs. two pointers), its deletion operation is O(N)if all you have is a pointer to the node you want deleted, while doubly-linked deletion is O(1). There is a little-known trick that lets you delete from a singly-linked list in O(1), but the list must be circular for it to work (move the content of nextinto the current, and delete next).

虽然单向链表每个节点使用较少的内存（一个指针 vs. 两个指针），但它的删除操作是，O(N)如果您拥有的只是指向要删除的节点的指针，而双链表删除则是O(1). 有一个鲜为人知的技巧可以让您从 中的单向链表中删除O(1)，但该列表必须是循环的才能使其工作（将 的内容next移入当前，然后删除next）。

Doubly-linked lists can be used in places where singly-linked lists would not work (a doubly-ended queue), but they require slightly more "housekeeping", and are slightly less efficient on insertions as the result.

双链表可用于单链表不起作用的地方（双端队列），但它们需要更多的“内务处理”，因此插入效率略低。

回答by Porco

Advantage of double linked list: Can traverse in both directions

双链表的优点：可以双向遍历

Advantage of single linked list: Less housework to be done on update/insert/delete, less memory usage.

单链表的优点：更新/插入/删除操作少，内存占用少。

回答by Peladao

Well, it depends on the situation. If you need to be able to quickly get both the previous as well as the next element from a given element then a doubly linked list is best.

嗯，这取决于情况。如果您需要能够从给定元素快速获取前一个和下一个元素，那么双向链表是最好的选择。

If you only need to get the next element from a given element, then a singly linked list is good enough.

如果您只需要从给定元素中获取下一个元素，那么单向链表就足够了。

回答by thealchemist

Singly-linked list over doubly-linked list:

单链表优于双链表：

Pros: 1. Less memory requirement.

优点： 1. 更少的内存需求。

1. It only needs to keep forward pointer/referencing in place.
2. Singly-linked list are persistent data structure. http://en.wikipedia.org/wiki/Persistent_data_structure#Linked_lists

2. 它只需要保持前向指针/引用就位。
3. 单向链表是持久化的数据结构。http://en.wikipedia.org/wiki/Persistent_data_structure#Linked_lists

Cons: 1. In general, to remove a node from the list, you have to change the next pointer of the node that appears before the node to remove so that it no longer points to the node to remove. In the case when you have a pointer to the node to be deleted. You have to start at the beginning of the list, iterate it all over till you find the node that comes just before the node to be deleted. This takes time O(n), so the runtime for the removing step is O(n) in the worst case.

缺点： 1、一般来说，要从链表中删除一个节点，你必须改变出现在要删除节点之前的节点的下一个指针，使其不再指向要删除的节点。如果您有指向要删除的节点的指针。您必须从列表的开头开始，遍历它，直到找到要删除的节点之前的节点。这需要时间 O(n)，所以在最坏的情况下，移除步骤的运行时间是 O(n)。

1. Provides Sequential access in one direction. What if you want to access in both directions, making it a DLL.

2. 提供一个方向的顺序访问。如果您想双向访问，将其设为 DLL，该怎么办？

Doubly linked list over the Singly linked list:

单链表之上的双链表：

Pros: 1. To remove a node when a pointer is given to that node, double linked list requires O(1) in the worst case.

优点： 1. 要在一个指向该节点的指针时删除该节点，双链表在最坏的情况下需要 O(1)。

1. Provides sequential access in both directions.

2. 提供双向顺序访问。

Cons: 1. More memory requirement ( if it is not a xored one A Memory-Efficient Doubly Linked List, XOR linked list ). Requires two pointers previous, and next as it is a two way.

缺点： 1. 更多的内存需求（如果不是异或一个内存高效的双向链表，异或链表）。需要两个指针前一个，下一个，因为它是一个双向的。

1. It needs to keep both forward and backward pointers in place.

2. Double linked list does not adapt well with a persistent setting.

2. 它需要同时保持向前和向后指针。

3. 双链表不能很好地适应持久设置。