Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 718
LiRoN Avatar asked Nov 16 '22 18:11

LiRoN


1 Answers

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

like image 89
Hugh W Avatar answered Dec 05 '22 16:12

Hugh W