W jaki sposób można dodać obiekt LinkedList <T> do obiektu LinkedList <T> w języku C#?

Question

Można by pomyśleć prostego kodu

llist1.Last.Next = llist2.First; 
llist2.First.Previous = llist1.Last; 

będzie działać, jednak najwyraźniej w C# 's LinkedList, pierwszy, ostatni, a ich właściwości są tylko dostać.

Druga metoda mogłem pomyśleć był

llist1.AddLast(llist2.First); 

Jednak to nie działa albo - to nie dlatego, że pierwszy węzeł llist2 jest już w połączonej listy.

Czy to oznacza, że ​​muszę mieć pętlę, która ręcznie AddLast każdego węzła llist2 do Llist1? Czy to nie wpływa na efektywność połączonych list?

Answer 1

llist1 = new LinkedList<T>(llist1.Concat(llist2)); 

to łączy dwie listy (wymaga .NET 3.5). Wadą jest to, że tworzy nową instancję LinkedList, który nie może być to, co chcesz ... Można zrobić coś takiego zamiast:

foreach(var item in llist2) 
{ 
    llist1.AddLast(item); 
} 

Answer 2

Tak, masz do pętli, niestety. Jest to operacja O (n) - O (1) dla każdego dodanego wpisu. Nie ma ryzyka wymagające bufor być zmieniany i kopiowane, etc - choć oczywiście zbieranie śmieci może zrobić z grubsza, że ​​:) Można nawet napisać przydatnych metod rozszerzeń:

public static class LinkedListExtensions 
{ 
    public static void AppendRange<T>(this LinkedList<T> source, 
             IEnumerable<T> items) 
    { 
     foreach (T item in items) 
     { 
      source.AddLast(item); 
     } 
    } 

    public static void PrependRange<T>(this LinkedList<T> source, 
             IEnumerable<T> items) 
    { 
     LinkedListNode<T> first = source.First; 
     foreach (T item in items) 
     { 
      source.AddBefore(first, item); 
     } 
    } 
} 

EDIT: Komentarz Ericha sugeruje, dlaczego może myśleć jest to nieefektywne - dlaczego nie po prostu dołączyć do dwóch list razem, aktualizując "następny" wskaźnik ogona pierwszej listy i "poprzedni" wskaźnik głowy drugiego? Cóż, pomyśl o tym, co stanie się z drugą listą ... to też zmieniłoby się.

Nie tylko to, ale co stałoby się z własnością tych węzłów? Każda z nich jest obecnie częścią dwóch list ... ale właściwość LinkedListNode<T>.List może mówić tylko o jednym z nich.

Podczas gdy widzę, dlaczego warto to zrobić w niektórych przypadkach, sposób, w jaki został zbudowany typ .NET LinkedList<T>, w zasadzie go uniemożliwia. Myślę, że to wyjaśnia doc komentarz to najlepiej:

Klasa LinkedList<T>) ma nie obsługują łączenia, podziału, cykle lub innych cech, które mogą opuścić listę w niespójnym państwa.

Answer 3

Tutaj można znaleźć moją listę połączonych realizacji z O (1) konkat i czasy podziału.

Why .NET LinkedList does not support Concat and Split operations?

Krótkie podsumowanie

Zalety vs.NET LinkedList:

• Mniejsze zużycie pamięci, dzięki czemu każdy SimpleLinkedListNode węzeł ma trzy wskaźniki (wstecz, dalej, wartość) zamiast czterech (poprzednia, następnej, liście, wartości) W przeciwieństwie do pierwotnej implementacji .NET.

• Obsługuje Concat i podzielić operacji w czasie O (1)

• Obsługuje IEnumarable tyłu() wyliczający w O (1) - nawiasem mówiąc nie widzę żadnego powodu, dlaczego nie jest to przewidziane natywnie na theNET LinkedList. Odpowiednia metoda rozszerzenia wymaga O (n).

Wady:

• nie obsługuje policzyć.
• Operacja Concat pozostawia drugą listę w niespójnym stanie.
• Operacja podziału pozostawia oryginalną listę w niespójnym stanie.
• Jesteś w stanie współdzielić węzły między listami.

Inne:

• wybrałem alternatywną strategię wdrażania wyliczanie i znaleźć operacje, zamiast bardziej opisowym i czysto czytelnej oryginalnej implementacji. Mam nadzieję, że negatywny wpływ na wyniki nie będzie znaczący.