CODEWITHSUNDEEP
c#listlinked-listtime-complexityaddrange
Liron Achdut
Liron Achdut

Reputation: 931

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

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?

Upvotes: 6

Views: 1057

Answers (1)

Hugh W
Hugh W

Reputation: 1186

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

Upvotes: 1

Related Questions