如何在C#中将一个LinkedList<T>添加到另一个LinkedList<T>中？

Question

人们可能会认为这段简单的代码：

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

这样做是可行的，但是显然在C#的LinkedList中，First、Last以及它们的属性都是只读的。

我能想到的另一种方法是

llist1.AddLast(llist2.First);

然而，这也不起作用——因为llist2的第一个节点已经在一个链表中了，所以它失败了。

这是否意味着我必须使用循环手动将llist2的每个节点AddLast到llist1中？这难道不会破坏链表的效率吗？？？

- Nick

---

追加链表似乎也不是一个非常常见的任务；如果我还记得我从前的数据结构课程。列表和链表不是同一回事。它们有不同的目的；因此，这种行为（或缺乏行为）是有意义的。 - John Kraft

llist1.AddLast(llist2.First)无法正常工作，因为llist1/llist2是双向链表。如果允许这样做，那么AddLast所给出的节点会引用哪个“previous”节点呢？正是因为这个原因，一个节点不能同时是两个列表的成员。 - Steve Guidi

@John Kraft：链表是列表概念的一种实现方式（与 C# 中的“List”是基于数组的列表实现方式不同）。它们只是在所需使用类型上有不同的成本。我可以看到需要将两个链表合并在一起的需求。 - Erich Mirabal

@Erich - 我同意你的观点。合并链接列表是一个合法的需求。我之前尝试指出的，可能表达得不太清楚的是，与 C# 的具体实现细节无关，链表的性能收益主要体现在节点的插入、删除和按特定顺序浏览节点列表上。重点是列表中包含的节点，而不是列表本身。因此，对于连接多个链接列表，没有内置的操作是有道理的。 - John Kraft

Answer 1

是的，不幸的是你必须循环。这是一个O(n)操作 - 每添加一个条目的时间复杂度为O(1)。没有需要调整大小和复制缓冲区等的风险 - 尽管当然垃圾回收可能会做类似的工作 :) 你甚至可以编写方便的扩展方法：

public static class LinkedListExtensions   
{
    public static void AppendRange<T>(this LinkedList<T> source,
                                      IEnumerable<T> items)
    {
        foreach (T item in items)
        {
            source.AddLast(item);
        }
    }

    public static void PrependRange<T>(this LinkedList<T> source,
                                       IEnumerable<T> items)
    {
        LinkedListNode<T> first = source.First;
        // If the list is empty, we can just append everything.
        if (first is null)
        {
            AppendRange(source, items);
            return;
        }

        // Otherwise, add each item in turn just before the original first item
        foreach (T item in items)
        {
            source.AddBefore(first, item);
        }
    }
}

编辑：Erich的评论说明了为什么您可能认为这是低效的 - 为什么不通过更新第一个列表的尾部的“next”指针和第二个列表的头部的“prev”指针来将两个列表连接在一起呢？好吧，想想第二个列表会发生什么...它也会改变。

不仅如此，那些节点的所有权会发生什么？每个节点现在本质上是两个列表的一部分...但是LinkedListNode<T>.List属性只能涉及其中一个。

虽然我可以理解您在某些情况下为什么要这样做，但.NET LinkedList<T>类型的构建方式基本上禁止了它。我认为这篇文档评论最好地解释了这一点：

LinkedList<T>类不支持链接、拆分、循环或其他可能导致列表处于不一致状态的功能。

- Jon Skeet

---

我认为他指的是执行一次操作（通过操作“指针”将一个列表附加到另一个列表）与遍历其中任何一个列表的所有条目之间的效率比较。对于附加操作，O(1)与O(n)相比。 - Erich Mirabal

直接操作指针会破坏第二个列表。 - Jon Skeet

当你说迭代和附加是O(1)时，你能否澄清一下你的意思？这听起来不太对。我认为附加一个项目是O(1)，但遍历n个项目是O(n)。 - Don Kirkby

这里的“每个条目”是O(1)。整体上是O(n)，没错。我会进行编辑以使其更清晰明了。 - Jon Skeet

请注意，如果source列表为空（因为source.First为空，导致source.AddBefore()抛出ArgumentNullException），则PrependRange()方法将失败。 - Erlend Graff

Answer 2

llist1 = new LinkedList<T>(llist1.Concat(llist2));

这个操作将两个列表连接起来（需要 .NET 3.5）。缺点是它会创建一个新的 LinkedList 实例，这可能不是你想要的...相反，你可以尝试以下操作：

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

- Thomas Levesque

---

这段代码对于链表是否执行正确的操作？还是使用默认的遍历所有元素的方法？ - Jimmy

它执行的是遍历每个元素的方法。 - Reed Copsey

请查看我的更新答案，避免对llist1进行迭代（尽管您仍然需要对llist2进行迭代...） - Thomas Levesque

Concat以惰性方式将两个IEnumerables连接在一起。因此，如果从未遍历结果列表，则此操作需要O（1）。 如果它们被遍历，那么在遍历第一个列表，然后是第二个列表时，没有渐近开销。因此，Concat是读取组合列表的非常有吸引力的解决方案。如果需要对组合列表进行结构修改，则它会出现问题，因为仍然存在两个不同的支持列表，并且无法通过IEnumerables进行结构修改。 - Michael Donohue

Answer 3

这里是一个具有O(1)连接和分离时间的链表实现。

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

简短总结

与.NET LinkedList相比的优势：

• 内存消耗更少，因此每个节点SimpleLinkedListNode只有三个指针（prev，next，value），而不像原始的.NET实现那样有四个（prev，next，list，value）。

• 支持O(1)的Concat和Split操作

• 支持O(1)的IEnumarable Reverse()枚举器 - 顺便说一句，我不知道为什么.NET LinkedList没有提供它原生支持。适当的扩展方法需要O(n)。

缺点：

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

其他：

• 我选择了一种替代策略来实现枚举和查找操作，而不是更冗长且纯可读的原始实现。我希望负面性能影响保持微不足道。

- George Mamaladze

---

至少要使实现方式变成“在O(1)时间内不支持计数（Count）”，而不是“不支持计数”。 - nawfal