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

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

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

будет работать, однако, по-видимому, в С# LinkedList, First, Last и их свойства являются только Get.

Другим способом, о котором я мог думать, был

llist1.AddLast(llist2.First);

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

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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

Ответ 3

Здесь вы можете найти реализацию связанного списка с O (1) временем concat и split.

Почему .NET LinkedList не поддерживает операции Concat и Split?

Краткое описание

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

Меньшее потребление памяти, поэтому каждый node SimpleLinkedListNode имеет три указателя (prev, next, value) вместо четырех (prev, next, list, значение) в отличие от оригинальной реализации .NET.
Поддержка Concat и Split операции в O (1)
Поддерживает IEnumarable Reverse() перечислитель в O (1) - кстати, я не вижу причин, почему его не предоставили изначально на .NET LinkedList. Соответствующий метод расширения требует O (n).

Недостатки:

Не поддерживает подсчет.
Операция Concat оставляет второй список в несогласованном состоянии.
Операция Split оставляет исходный список в несогласованном состоянии.
Вы можете обмениваться узлами между списками.

Другое:

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

Ответ 4

Попробуйте использовать:

LinkedListNode<Type> node = new LinkedListNode<Type>(llist2.First.Value);
llist1.AddLast(node);

или

llist1.AddLast(llist2.First.Value);