-3

I have a List<bar> of LinkedList<foo>:

int x = y;
List<LinkedList<foo>> list = new List<LinkedList<foo>>(x);

I want to be able to move all elements of a LinkedList<foo> of list into another without create new list or nodes. This is why I choose a LinkedList<foo> type. In C++, I could use std::list::splice.

At the end, only one element of list will not be empty.

My problem is that I can't find anyway to do this, I only found method that copy two LinkedList<foo> into one or similar.

My research so far (this is not what I want):

Note: I don't care about data order, I just need performance.

Stargateur
  • 24,473
  • 8
  • 65
  • 91
  • I'm a bit confused. A `List>` would be similar to C++'s `std::vector>`. How is `List` relevant to the question? – milleniumbug Oct 06 '17 at 22:12
  • @milleniumbug I add List for the context maybe it's useless. But indeed I would like a method splice on LinkedList, or a solution that use an other container that would implement splice and have O(1) on this operation. – Stargateur Oct 06 '17 at 22:18
  • 1
    Also: are the left-hand side and the right-hand side different types like the example code says they are? And what about `List` and `LinkedList`? Not to mention, C++'s `std::list::splice` is O(n) too (but probably still fast) because the rhs list has to maintain the `size()`. – milleniumbug Oct 06 '17 at 22:27
  • 1
    [`LinkedList.AddLast`](https://msdn.microsoft.com/en-us/library/ms132176) accepts a `LinkedListNode`, and another line is needed to remove the nodes from the source. – Slai Oct 06 '17 at 22:51
  • 1
    If you need this to be O(1), you'd need a linked list class which has a a O(n) `.Count`. There's no such built-in class in .NET – milleniumbug Oct 06 '17 at 22:55
  • @Slai Not perfect but I suppose this is very close to what I want, this was simple. Thanks. – Stargateur Oct 06 '17 at 22:58

1 Answers1

2

If with "I just need performance" you mean you need the splice operation to be O(1), then, as far as I know, this is not possible with .NET.

However, you could create your own type that behaves like a LinkedList<T> and that supports such a splice operation. Of course it is not nice to implement functionality that's already present, but on the other hand a linked list is not that complicated.

Or you could create a type that wraps List<LinkedList<T>> (or something similar) and supports the operations you need. E.g. LinkedList<T> implements IEnumerable<T> and ICollection<T>, and implementing these on a wrapper for List<LinkedList<T>> is just a few lines of relatively simple code, and the splice operation would be almost for free.

Martin
  • 1,986
  • 15
  • 32