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?

Essentially you're trying to end up with a single list by mutating both lists to follow on from each other, correct? — ProgrammingLlama, Jan 08 '20 at 08:33
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. — Liron Achdut, Jan 08 '20 at 08:35
Does this answer your question? [How does one add a LinkedList to a LinkedList in C#?](https://stackoverflow.com/questions/1094445/how-does-one-add-a-linkedlistt-to-a-linkedlistt-in-c) — Sushant Yelpale, Jan 08 '20 at 08:39
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. — ProgrammingLlama, Jan 08 '20 at 08:40
This is not a supported operation because to implement it in `O(1)` would mean changing BOTH lists. See [here](https://gmamaladze.wordpress.com/2011/08/06/why-net-linkedlist-does-not-support-concat-and-split-operations/) for more details. — Matthew Watson, Jan 08 '20 at 09:00
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? — Dan Rayson, Jan 08 '20 at 11:53
@SushantYelpale I've seen this question, and there are no answers to my question there.. (how to do it in O(1) without implementing) — Liron Achdut, Jan 08 '20 at 11:58
Impossible because of [LinkedListNode.List Property](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlistnode-1.list?view=netframework-4.8) which is backed by internal field (for O(1) access) and needs to be changed in all the nodes you want to append/move. — firda, Jan 08 '20 at 13:14

score 1 · Answer 1 · answered Mar 31 '22 at 08:29

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

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

1 Answers1