Extending List (AddRange) in O(1) in C#

Question

I'm trying to find a solution in C# to extending a list in O(1).

List's AddRange() method is of course an O(n) operation. This should have been something that LinkedList supports, but LinkedList doesn't have a method like AddRangeLast(), and trying to combine LinkedLists like this:

LinkedList<int> l1 = new LinkedList<int>(new[] { 1, 2, 3 });
LinkedList<int> l2 = new LinkedList<int>(new[] { 11, 12, 13 });
l1.AddLast(l1.First);

Throws this exception:

System.InvalidOperationException: 'The LinkedList node already belongs to a LinkedList.'

Does anyone know of a way to add a list to a list in O(1) without implementing LinkedList and LinkedListNode myself?

Grande

Essentially you're trying to end up with a single list by mutating both lists to follow on from each other, correct? – Condenser

Yes. Really I want to mutate just one list so that it's last node points to the second list's first node and its count will be increased by the other list's count. – Grande

Does this answer your question? How does one add a LinkedList<T> to a LinkedList<T> in C#? – Benedick

I think you'll run into problems with this approach because the list node stores the list instance on it, and each new node you try to add is validated to ensure that it belongs to the list. You could probably hack this to work with reflection, etc. but it might result in undefined behaviour. A better option might be to use a different linked list implementation. – Condenser

This is not a supported operation because to implement it in O(1) would mean changing BOTH lists. See here for more details. – Lifelong

Could you create a wrapper class around the two LinkedLists, and simply return an IEnumerable that loops over both lists? i.e. Do you need to expose the LinkedList implementation or are you OK with just having something to loop over both lists? – Hough

@SushantYelpale I've seen this question, and there are no answers to my question there.. (how to do it in O(1) without implementing) – Grande

Impossible because of LinkedListNode<T>.List Property which is backed by internal field (for O(1) access) and needs to be changed in all the nodes you want to append/move. – Seldom

Answer 1

No, this is not possible with System.Collections.Generic.LinkedList. From the docs:

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

There's a more in-depth answer to a near-identical question at How does one add a LinkedList to a LinkedList in C#?.

Urbina