.net Microsoft要求:单列表还是双列表?使用每种方法的优缺点是什么?

a7qyws3x  于 2023-03-31  发布在  .NET
关注(0)|答案(6)|浏览(142)

我被问到这样的问题,我有我自己的说法,但我真的不知道该说什么利弊?微软问这个问题,它的候选人之一。
单链表允许你去一个方向。而双向链表有两个方向下一个和上一个。
这里有一个很好的图片,它绘制了Singly和Doubly LinkedList。

但是,你如何更有序地解释这些项目的利弊呢?

u4vypkhs

u4vypkhs1#

虽然这个问题已经得到了回答,但我对答案并不满意(无意冒犯),所以我会这样回答:
使用什么-单或双链表取决于你打算实现什么和系统限制,如果有的话。

单链表:

优点:实现简单,需要相对较少的内存用于存储,假设您需要删除/插入(在)下一个节点-删除/插入更快。
缺点:不能反向迭代,需要维护链表头节点的句柄,否则链表会在内存中丢失。如果删除前一个节点或者在前一个节点插入,需要从头遍历链表到前一个节点才能执行这些操作- O(N)时间。

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

双向链表:

优点:可以正向迭代,也可以反向迭代,如果需要删除前一个节点,不需要从头节点开始遍历,可以从.previous指针中找到要删除的节点。
缺点:实现比较复杂,需要更多内存存储(每个节点1个.previous指针),插入和删除比较耗时(为邻居节点分配/重新分配.previous指针)

--当你没有内存限制或内存限制很小,并且你的主要目标是搜索元素时,应该使用它。
如果有更多的优点和缺点,请随时补充,在评论中回复。谢谢!

to94eoyn

to94eoyn2#

我被问到这样的问题,我有我自己的说法,但我真的不知道该说什么利弊?
这都取决于使用情况。这里有一个权衡。
单链表在实现方面更简单,并且通常具有更小的内存需求,因为它只需要保持正向成员引用。
双向链表有更高效的迭代,特别是当你需要反向迭代的时候(这对于一个单链表来说是非常低效的),以及更高效的删除特定节点。
也就是说-因为你有这个标记.NET,双向链表也有直接在框架中以LinkedList<T>类的形式存在的优势。这提供了一个巨大的优势,因为你不必实现,测试和维护自己的集合类。

mwyxok5s

mwyxok5s3#

而单链表每个节点占用的内存更少(一个指针vs.两个指针),它的删除操作是O(N),如果你只有一个指向你想要删除的节点的指针,而双向链接删除是O(1)。在O(1)中有一个鲜为人知的技巧,可以让你从单链表中删除,但是列表必须是循环的,这样它才能工作(将next的内容移动到当前,并删除next)。
双链表可以用在单链表不能工作的地方(双端队列),但它们需要稍微多一点的“内务管理”,结果在插入时效率稍低。

inkz8wg9

inkz8wg94#

双向链表的优点:可以双向移动
单链表的优点:更新/插入/删除时需要做的家务更少,内存使用更少。

koaltpgm

koaltpgm5#

当然,这取决于具体情况。如果你需要快速地从一个给定的元素中获取前一个元素和下一个元素,那么双向链表是最好的。
如果你只需要从一个给定的元素中获取下一个元素,那么一个单链表就足够了。

ccrfmcuu

ccrfmcuu6#

单链表优于双链表:
优点:1.内存需求少。
1.它只需要在适当的位置保持前向指针/引用。
1.单链表是持久化的数据结构http://en.wikipedia.org/wiki/Persistent_data_structure#Linked_lists
缺点:1.一般来说,要从列表中删除一个节点,你必须改变出现在要删除的节点之前的节点的下一个指针,使它不再指向要删除的节点。在你有一个指针指向要删除的节点的情况下。你必须从列表的开头开始,时间复杂度为O(n),所以在最坏的情况下,时间复杂度为O(n)。
1.提供一个方向的顺序访问。如果你想在两个方向访问,使它成为一个DLL。
双向链表优先于单向链表:
如果一个链表的指针指向一个节点,那么这个链表的时间复杂度为O(1)。
1.提供双向顺序访问。
缺点:1.更多的内存需求(如果它不是一个xored一个内存高效的双链表,异或链表)。需要两个指针前,和下一个,因为它是一个双向的。
1.它需要保持向前和向后指针。
1.双向链表不能很好地适应持久设置。

相关问题