我被问到这样的问题，我有自己的说法，但我真的不知道该说些什么利弊？微软向其中一位候选人提出了这个问题。
单链表可以让你走一个方向。而双向链表具有下一个和上一个方向。
这是一张绘制单链表和双链表的好图。
但是，您如何更有序地解释这些物品的优缺点？
问问题
35557 次
6 回答
27
虽然这个问题已经回答了，但我对答案不满意（没有冒犯的意思），所以我将如何回答：
使用什么 - 单链表或双链表取决于您打算实现的目标和系统限制（如果有）。
单链表：
优点：实现简单，需要相对较少的存储内存，假设您需要删除/插入（在）下一个节点 - 删除/插入更快。
缺点：不能反向迭代，需要维护链表头节点的句柄，否则链表会丢失在内存中。如果要删除前一个节点或在前一个节点插入，则需要从头到前一个节点遍历列表才能执行这些操作 - O(N) 时间。
--因此，当您的内存较少并且您的主要目标是插入/删除而不是搜索元素时，应该使用它。
双向链表：
优点：可以正向和反向迭代。如果需要删除前一个节点，则不需要从头节点遍历，因为可以从'.previous'指针中找到要删除的节点。
缺点：实现起来相对复杂，需要更多内存来存储（每个节点 1 个“.previous”指针）。插入和删除相对更耗时（为相邻节点分配/重新分配“.previous”指针）
--这应该在您对内存没有限制或限制最小的情况下使用，并且您的主要目标是搜索元素。
如果有更多的优点和缺点，请随时添加，在评论中回复。谢谢！
于 2012-09-12T12:02:24.617 回答
25
我被问到这样的问题，我有自己的说法，但我真的不知道该说些什么利弊？
这一切都归结为使用。这里有一个权衡。
单链表在实现方面更简单，并且通常具有较小的内存需求，因为它只需要保持前向成员引用到位。
双链表的迭代效率更高，特别是如果您需要反向迭代（单链表效率极低），以及更有效地删除特定节点时。
话虽这么说 - 由于您有这个标记的 .NET，双链表还具有直接以LinkedList<T>类的形式存在于框架中的优点。这提供了一个巨大的优势，因为您不必实现、测试和维护自己的集合类。
于 2012-05-22T19:31:38.760 回答
12
虽然单链表每个节点使用较少的内存（一个指针与两个指针），但它的删除操作是，O(N)如果您只有一个指向要删除的节点的指针，而双链接删除是O(1). 有一个鲜为人知的技巧，可以让您从 中的单链表中删除O(1)，但列表必须是循环的才能工作（将 的内容移动next到当前，然后删除next）。
双链表可用于单链表不起作用的地方（双向队列），但它们需要稍微多一点的“内务处理”，因此插入效率略低。
于 2012-05-22T19:33:04.597 回答
3
双链表的优点：可以双向遍历
单链表的优点：更新/插入/删除要做的家务少，内存占用少。
于 2012-05-22T19:32:16.800 回答
2
好吧，这取决于情况。如果您需要能够从给定元素中快速获取上一个和下一个元素，那么双向链表是最好的。
如果只需要从给定元素中获取下一个元素，那么单链表就足够了。
于 2012-05-22T19:32:28.883 回答
1
单链表优于双链表：
优点： 1. 更少的内存需求。
- 它只需要保持前向指针/引用到位。
- 单链表是持久化的数据结构。http://en.wikipedia.org/wiki/Persistent_data_structure#Linked_lists
缺点： 1. 一般来说，要从列表中删除一个节点，您必须更改出现在要删除节点之前的节点的下一个指针，使其不再指向要删除的节点。如果您有一个指向要删除的节点的指针。您必须从列表的开头开始，遍历它，直到找到要删除的节点之前的节点。这需要时间 O(n)，因此在最坏的情况下，删除步骤的运行时间是 O(n)。
- 提供一个方向的顺序访问。如果您想双向访问，使其成为 DLL，该怎么办。
单链表上的双链表：
优点： 1. 要在将指针指向该节点时删除该节点，双链表在最坏的情况下需要 O(1)。
- 提供双向顺序访问。
缺点： 1. 更多内存要求（如果不是异或 A Memory-Efficient 双链表，异或链表）。需要两个指针previous和next，因为它是双向的。
它需要保持前向和后向指针都在适当的位置。
双链表不能很好地适应持久化设置。
于 2020-05-01T12:41:25.807 回答