Как добавить LinkedList <T> в LinkedList <T> в C#?

Question

Казалось бы простой код

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

будет работать, однако, по-видимому, в C# LinkedList 's, первый, последний и их свойства Получить только.

Другой метод, который я мог думать

llist1.AddLast(llist2.First); 

Однако, это не работает, либо - он терпит неудачу, потому что первый узел llist2 уже в связанном списке.

Означает ли это, что у меня должен быть цикл, который вручную добавляет каждый узел LLLLLLLLLLLL1 к каждому элементу? Разве это не побеждает эффективность связанных списков ????

Answer 1

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

это объединяет два списка (требуется .NET 3.5). Недостаток заключается в том, что он создает новый экземпляр LinkedList, который не может быть то, что вы хотите ... Вы могли бы сделать что-то подобное вместо:

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

Answer 2

Да, вы должны цикла, к сожалению. Это операция O (n) - O (1) для каждой добавленной записи. Там нет риски требуют буферов быть изменена и скопирована и т.д. - хотя, конечно, вывоз мусора может сделать примерно что :) Можно даже написать удобные методы расширения:

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: комментарий Эриха предполагает, почему вы могли бы подумать это неэффективно - почему бы просто не объединить два списка вместе, обновив «следующий» указатель хвоста первого списка и указатель «prev» главы второго? Ну, подумайте о том, что произойдет со вторым списком ... это тоже изменилось бы.

Не только это, но что произойдет с владением этими узлами? Каждый из них по существу является частью двух списков ... но свойство LinkedListNode<T>.List может говорить только об одном из них.

Хотя я вижу, почему вы, возможно, захотите сделать это в некоторых случаях, способ, которым был создан тип .NET LinkedList<T>, в основном запрещает его. Я думаю, что этот документ комментарий объясняет, что лучше:

LinkedList<T>) класса делает не поддерживает цепочки, расщепление, циклов, или другие функции, которые могут покинуть список в неустойчивом состояния.

Answer 3

Здесь вы можете найти список связанных объектов с O (1) concat и split times.

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

Краткий обзор

Преимущества против.NET LinkedList:

• Меньше потребление памяти, таким образом, каждый узел SimpleLinkedListNode имеет три указателей (пред ряд, значение) вместо четырех (пред, следующих, списка, значения), в отличие от оригинальной реализации .NET.

• Поддержка Concat и Split операций в O (1)

• Поддержка IEnumarable Reverse() перечислитель в O (1) - кстати, я не вижу никаких причин, почему это не предусмотрено изначально на .NET LinkedList. Для соответствующего метода расширения требуется O (n).

Недостатки:

• Не поддерживает графа.
• Конкатентная операция оставляет второй список в несогласованном состоянии.
• Сплит-операция оставляет исходный список в несогласованном состоянии.
• Вы можете обмениваться узлами между списками.

Другое:

• Я выбрал альтернативную стратегию для осуществления перечисления и поиска операций, а не более развернутого и чисто читаемый первоначальной реализации. Я надеюсь, что отрицательное влияние на производительность остается незначительным.