How does one add a LinkedList to a LinkedList in C#?

Question

One would think the simple code

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

would work, however apparently in C#'s LinkedList, First, Last, and their properties are Get only.

The other method I could think of was

llist1.AddLast(llist2.First);

However, this does not work either - it fails because the first node of llist2 is already in a linked list.

Does this mean that I have to have a loop that manually AddLast's each node of llist2 to llist1? Doesn't this defeat the efficiency of linked lists????

Answer 1

Yes, you have to loop, unfortunately. This is an O(n) operation - O(1) for each entry added. There's no risk of requiring a buffer to be resized and copied, etc - although of course garbage collection might do roughly that :) You could even write handy extension methods:

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);
        }
    }
}

EDIT: Erich's comment suggests why you might think this is inefficient - why not just join the two lists together by updating the "next" pointer of the tail of the first list and the "prev" pointer of the head of the second? Well, think about what would happen to the second list... it would have changed as well.

Not only that, but what would happen to the ownership of those nodes? Each is essentially part of two lists now... but the LinkedListNode<T>.List property can only talk about one of them.

While I can see why you might want to do this in some cases, the way that the .NET LinkedList<T> type has been built basically prohibits it. I think this doc comment explains it best:

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

Answer 2

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

this concatenates the two lists (requires .NET 3.5). The drawback is that it creates a new instance of LinkedList, which may not be what you want... You could do something like that instead :

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

Answer 3

Here you can find my linked list implementation with O(1) concat and split times.

Why .NET LinkedList does not support Concat and Split operations?

Short summary

Advantages vs .NET LinkedList:

• Less memory consumption, thus every node SimpleLinkedListNode has three pointers (prev, next, value) instead of four (prev, next, list, value) unlike original .NET implementation.

• Supports Concat and Split operations in O(1)

• Supports IEnumarable Reverse() enumerator in O(1) – by the way I do not see any reason why it’s not provided natively on the .NET LinkedList. Appropriate extension method requires O(n).

Disadvantages:

• Does not support Count.
• Concat operation leaves second list in an inconsistent state.
• Split operation leaves original list in an inconsistent state.
• You are able to share nodes between lists.

Other:

• I have chosen an alternative strategy for implementing enumeration and find operations, rather than more verbose and purely readable original implementation. I hope the negative performance impact remains insignificant.