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

Question

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

单链表允许您单向访问。而双向链表具有next和previous双向。

这是一张很好的图片，画出了单色和双色的LinkedLists。

​

​

然而，如何以更有序的方式解释这些项目的优缺点？

Answer 1

我被问到这样的问题，我有自己的说法，但我真的不确定该怎么说利弊？

这一切都归结于使用。这是一种权衡。

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

双向链表的迭代效率更高，特别是当你需要反向迭代的时候(这对于单个链表来说效率非常低)，并且可以更有效地删除特定的节点。

也就是说，由于您有这个标记的.NET，所以双向链表还具有以LinkedList类的形式直接存在于框架中的优点。这提供了一个巨大的优势，因为您不必实现、测试和维护自己的集合类。

Answer 2

虽然这个问题已经得到了回答，但不知何故我对这个答案并不满意(无意冒犯)，所以我将如何回答它：

使用什么-单链表还是双向链表取决于您要实现的目标和系统限制(如果有的话)。

单链表：

优点:实现简单，需要相对较少的内存来存储，假设您需要删除/插入(在)下一个节点-删除/插入速度更快。

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

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

双向链表：

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

缺点:实现起来相对复杂，需要更多的内存来存储(每个节点1个‘.previous’指针)。插入和删除相对比较耗时(为邻居节点分配/重新分配‘.previous’指针)

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

如果有更多的优点和缺点，请随时添加，在评论中回复。谢谢!

Answer 3

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

双链表可以用于单链表不起作用的地方(双端队列)，但它们需要稍微多一点的“内务”，因此在插入时效率略低。