How does one add a LinkedList<T> to a LinkedList<T> 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????

Solution 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.

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

Solution 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.

Comments

[Steve Guidi]

llist1.AddLast(llist2.First) doesn't work because llist1/llist2 are doubly-linked lists. If this were allowed, which "previous" node would be referred by the node given to AddLast? It can't be a member of two lists for this very reason.

[Erich Mirabal]

@John Kraft: Linked-Lists are one implementation of the idea of a List (versus "List" in C# being an array-based implementation of a list). They just have different costs for the type of usage you want. I can see the need to merge two linked-lists together.

[Boti]

does this do the right thing for linked lists? or does it use the default iterate-over-everything method?

[Reed Copsey]

It does the iterate-over-everything method.

[Erich Mirabal]

I think he means the efficiency of doing one operation (manipulate the "pointers" to append one list to the other) versus iterating over all the entries of either one. O(1) vs O(n) for the append operation.

[Jon Skeet]

Manipulating the pointers directly would break the second list though.

[Don Kirkby]

Can you clarify what you mean when you say iteration and appending are O(1)? It doesn't sound right to me. I think appending one item is O(1), but iterating over n items is O(n).

[Jon Skeet]

It's the "of each entry" that's O(1). It's O(n) over the whole lot, yes. Will edit to make that clearer.

[Erich Mirabal]

I know, I'm just saying that is what he meant. It doesn't seem that far out there to be able to do that (merge two lists), but the current .NET implementation makes it impossible with LinkedList (as you point out).

[Erich Mirabal]

Appending is O(1) since it is a doubly-linked list with "pointers" to the first and last item.

[Erich Mirabal]

+1. Now there's an answer that even Jon Skeet would be proud of... err.. umm.. you know what I mean :)

[Jon Skeet]

Thanks for elaborating on the question - much appreciated. Must get back to that static one later on... blog post to write first though. Can't see the book going much further tonight...

[Thomas Levesque]

See my updated answer to avoid iterating over llist1 (you still have to iterate over llist2 though...)

[Michael Donohue]

Concat puts two IEnumerables together in a lazy way. So if the resulting list is never traversed, this operation takes O(1). If they are traversed, there is no asymptotic overhead in traversing the first list, and then the second list. So Concat is a very attractive solution for reading the combined lists. It falls short if structural modifications to the combined list are desired, as there are still two distinct backing lists underneath, and structural modifications cannot be done through IEnumerables

[nawfal]

Does not support Count., at least make the implementation so that the statement becomes Does not support Count in O(1) :)

[Erlend Graff]

Note that the PrependRange() method will fail if the source list is empty (as source.First will be null, which leads to source.AddBefore() throwing an ArgumentNullException).