微软问:单一列表还是双重列表？使用每个的利弊是什么？

Question

我被问到这样的问题而且我有自己的说法,但我不确定该如何评价利弊和专业人士？微软向其中一位候选人提出这个问题.

单链表可以让你走向单向.而双向链表在下一个和前一个方向有两个方向.

这是一张描绘单一和双重链接列表的好照片.

但是,您如何以更有秩序的方式解释这些项目的利弊？

Answer 1

虽然这个问题已经得到了解答,但我对答案感到不满意(没有冒犯意味着),所以这里我将如何回复它:

使用方法 - 单个或双重链表取决于您打算实现的目标和系统限制(如果有的话).

单链表:

优点:实现简单,需要相对较少的存储空间,假设您需要删除/插入(at)下一个节点 - 删除/插入更快.

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

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

双链表:

优点:可以在前进和反向迭代.在需要删除前一个节点的情况下,不需要从头节点遍历,因为可以从'.previous'指针找到要删除的节点.

缺点:实现相对复杂,需要更多内存用于存储(每个节点1'.previous'指针).插入和删除相对更耗时(为邻居节点分配/重新分配'.previous'指针)

- 如果您对内存没有限制或限制很少,则应使用此选项,主要目标是搜索元素.

如果有任何优点和缺点,请随意添加,回复评论.谢谢!

Answer 2

我被问到这样的问题而且我有自己的说法,但我不确定该如何评价利弊和专业人士？

这一切都归结为使用.这里有一个折衷.

单个链接列表在实现方面更简单,并且通常具有更小的内存要求,因为它只需要保持前向成员引用到位.

双向链表具有更高效的迭代,特别是如果您需要反向迭代(对于单个链表而言效率非常低),以及更有效地删除特定节点.

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

Answer 3

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

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