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

Question

人们会想到简单的代码

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<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;
        foreach (T item in items)
        {
            source.AddBefore(first, item);
        }
    }
}

编辑:埃里希的意见建议,为什么你会认为这是无效的-为什么不通过更新第一列表和第二头的"上一个"指针尾部的"下一个"指针两个列表连接在一起？好吧,想想第二个列表会发生什么...... 它也会发生变化.

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

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

本LinkedList<T>)类不支持链接,分裂,周期,或其他功能,可以留在不一致的状态列表.

Answer 2

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

这连接了两个列表(需要.NET 3.5).缺点是它创建了一个新的LinkedList实例,这可能不是你想要的......你可以这样做:

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

Answer 3

在这里你可以找到我的链表实现，它的连接和拆分时间为 O(1)。

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

简短的摘要

与 .NET LinkedList 相比的优势：

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

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

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

缺点：

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

其他：

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