¿Cómo se agrega una LinkedList <T> a una LinkedList <T> en C#?

Question

Uno pensaría que el código simple

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

quiere trabajar, sin embargo, al parecer, en C# 's LinkedList, primero, último, y sus propiedades se consigue solamente.

El otro método que podía pensar era

llist1.AddLast(llist2.First); 

Sin embargo, esto no funciona bien - se produce un error debido a que el primer nodo de llist2 ya está en una lista enlazada.

¿Esto significa que tengo que tener un bucle que agregue manualmente cada nodo de llist2 a llist1? ¿Esto no derrota la eficiencia de las listas enlazadas ???

Answer 1

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

esto concatena las dos listas (requiere .NET 3.5). El inconveniente es que se crea una nueva instancia de LinkedList, que puede no ser lo que quiere ... Se podría hacer algo así en su lugar:

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

Answer 2

Sí, usted tiene que bucle, por desgracia. Esta es una operación O (n) - O (1) para cada entrada agregada. No hay riesgo de requerir una memoria intermedia para cambiar de tamaño y copiar, etc - aunque, por supuesto, la recolección de basura podría hacer más o menos que :) Incluso se puede escribir métodos extensión práctica:

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: comentario de Erich sugiere por qué se podría pensar esto es ineficiente, ¿por qué no unir las dos listas al actualizar el puntero "siguiente" de la cola de la primera lista y el puntero "anterior" de la cabeza del segundo? Bueno, piense en lo que sucedería con la segunda lista ... también habría cambiado.

No solo eso, sino ¿qué pasaría con la propiedad de esos nodos? Cada uno es esencialmente parte de dos listas ahora ... pero la propiedad LinkedListNode<T>.List solo puede hablar de una de ellas.

Aunque puedo ver por qué es posible que desee hacer esto en algunos casos, la forma en que se ha construido el tipo .NET LinkedList<T> básicamente lo prohíbe. Creo que este comentario de documentación explica mejor:

La clase LinkedList<T>) qué no son compatibles con el encadenamiento, la división, ciclos, u otras características que pueden dejar la lista en un estado incoherente .

Answer 3

Aquí puede encontrar la implementación de mi lista enlazada con O (1) concat y split times.

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

Breve resumen

Ventajas vs.ListaEnlazada NET:

• Menos consumo de memoria, por lo que cada nodo tiene SimpleLinkedListNode triples (anterior, siguiente, valor) en lugar de cuatro (anterior, siguiente, lista, valor) a diferencia de implementación original .NET.

• Soporta ConCat y dividir operaciones en O (1)

• Soporta empadronador IEnumarable atrás() en O (1) - por cierto, no veo ninguna razón por la que no está previsto forma nativa en la .NET LinkedList. El método de extensión apropiado requiere O (n).

Desventajas:

• no soporta contar.
• El funcionamiento de Concat deja la segunda lista en un estado incoherente.
• La operación dividida deja la lista original en un estado incoherente.
• Puede compartir nodos entre listas.

Otros:

• he elegido una estrategia alternativa para la implementación de la enumeración y encontrar las operaciones, en lugar de implementación original más prolija y puramente legible. Espero que el impacto negativo en el rendimiento siga siendo insignificante.