如何在C＃中将LinkedList 添加到LinkedList ？

人们会想到简单的代码

llist1.Last.Next = llist2.First; llist2.First.Previous = llist1.Last; 

可行，但显然在C＃的LinkedList，First，Last中，它们的属性仅为Get。

我能想到的另一种方法是

 llist1.AddLast(llist2.First); 

但是，这也不起作用 – 它失败了，因为llist2的第一个节点已经在链表中。

这是否意味着我必须有一个循环，手动AddLast的llist2的每个节点到llist1？ 这不是打败链表的效率????

Answer 1

是的，不幸的是，你必须循环。 这是一个O（n）操作 – 添加的每个条目的O（1）。 不存在需要调整缓冲区和复制等的风险 – 尽管当然垃圾收集可能大致如此:)您甚至可以编写方便的扩展方法：

 public static class LinkedListExtensions { public static void AppendRange(this LinkedList source, IEnumerable items) { foreach (T item in items) { source.AddLast(item); } } public static void PrependRange(this LinkedList source, IEnumerable items) { LinkedListNode first = source.First; foreach (T item in items) { source.AddBefore(first, item); } } } 

编辑：Erich的评论建议你为什么认为这是低效的 – 为什么不通过更新第一个列表尾部的“下一个”指针和第二个列表头部的“prev”指针将两个列表连接在一起？ 好吧，想想第二个列表会发生什么…… 它也会发生变化。

不仅如此，但这些节点的所有权会发生什么？ 现在每个都基本上是两个列表的一部分……但LinkedListNode.List属性只能谈论其中一个。

虽然我可以在某些情况下看到为什么你可能想要这样做，但是.NET LinkedList类型的构建方式基本上禁止它。 我认为这篇文档评论最能说明这一点：

LinkedList)类不支持链接，拆分，循环或其他可能使列表处于不一致状态的function。

Answer 2

 llist1 = new LinkedList(llist1.Concat(llist2)); 

这连接了两个列表（需要.NET 3.5）。 缺点是它创建了一个新的LinkedList实例，这可能不是你想要的……你可以这样做：

 foreach(var item in llist2) { llist1.AddLast(item); } 

Answer 3

在这里，您可以找到我的链表实现与O（1）concat和拆分时间。

为什么.NET LinkedList不支持Concat和Split操作？

简短的摘要

与.NET LinkedList的优点：

• 减少内存消耗，因此每个节点SimpleLinkedListNode有三个指针（prev，next，value）而不是四个（prev，next，list，value），这与原始的.NET实现不同。

• 支持O（1）中的Concat和Split操作

• 支持O（1）中的IEnumarable Reverse（）枚举器 – 顺便说一下，我没有看到为什么它没有在.NET LinkedList上本地提供的原因。 适当的扩展方法需要O（n）。

缺点：

• 不支持Count。
• Concat操作使第二个列表处于不一致状态。
• 拆分操作使原始列表处于不一致状态。
• 您可以在列表之间共享节点。

其他：

• 我选择了一种替代策略来实现枚举和查找操作，而不是更详细和纯粹可读的原始实现。 我希望负面的业绩影响仍然微不足道。