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????

Caravaggio

Appending linked lists doesn't seem to be a very common task either; if I remember my data structures courses from back in the day. Lists and linked lists are not the same thing. They have different purposes; thus, the behavior (or lack thereof) makes sense. – Marlyn

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. – Debar

@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. – Ball

@Erich - I agree with you. Merging linked lists is a legitimate need. What I was trying to point out, apparently poorly, was that the performance gains of a linked list (not specific to the implementation details of C#) deal with the insertion and removal of nodes, and navigation of a list of nodes in a specific sequence. The focus is on nodes contained within the list, not the list itself. Thus, it makes sense that their is no built in operation for concatenating multiple linked lists. – Marlyn

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.

Tati

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. – Ball

Manipulating the pointers directly would break the second list though. – Tati

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). – Peruzzi

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. – Tati

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). – Ball

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

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

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... – Tati

Excellent answer. It's also worth noting that not only would both lists change, but they would become inextricably linked. Adding or removing a node from one could potentially affect the other - not something you would normally expect from seemingly independent list instances. – Mckown

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). – Bailar

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

Canner

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

It does the iterate-over-everything method. – Cheeky

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

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 – Steady

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.

Quaff

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