c# - 如何在 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 的每个节点添加到 llist1？这不是打败了链表的效率吗？？？？

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属性(property)只能谈其中之一。

虽然我明白为什么在某些情况下您可能想要这样做，但 .NET LinkedList<T> 的方式类型已经建立基本上禁止它。我认为这个文档评论解释得最好:

The LinkedList<T>) class does not support chaining, splitting, cycles, or other features that can leave the list in an inconsistent state.