Come si aggiunge una LinkedList <T> a una LinkedList <T> in C#?

Question

Si potrebbe pensare il codice semplice

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

avrebbe funzionato, ma a quanto pare in C 's # LinkedList, Primo, Ultimo, e le loro proprietà sono ottenere solo.

L'altro metodo che riuscivo a pensare era

llist1.AddLast(llist2.First); 

Tuttavia, questo non funziona neanche - non riesce perché il primo nodo di llist2 è già in una lista collegata.

Ciò significa che devo avere un ciclo che aggiunge manualmente ciascun nodo di llist2 a llist1? Questo non sconfigge l'efficienza delle liste collegate ????

Answer 1

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

concatena le due liste (richiede .NET 3.5). Lo svantaggio è che si crea una nuova istanza di LinkedList, che non può essere quello che vuoi ... Si potrebbe fare qualcosa di simile, invece:

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

Answer 2

Sì, è necessario loop, purtroppo. Questa è un'operazione O (n) - O (1) per ogni voce aggiunta. Non c'è alcun rischio di richiedere un buffer per essere ridimensionate e copiati, ecc - anche se naturalmente garbage collection potrebbe fare più o meno quello :) Si potrebbe anche scrivere a portata di mano i metodi di estensione:

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: il commento di Erich suggerisce perché si possa pensare questo è inefficiente - perché non unire semplicemente le due liste insieme aggiornando il puntatore "successivo" della coda della prima lista e il puntatore "prev" della testa della seconda? Bene, pensa a cosa sarebbe successo alla seconda lista ... it sarebbe cambiato pure.

Non solo, ma cosa succederebbe alla proprietà di quei nodi? Ciascuno è essenzialmente parte di due elenchi ora ... ma la proprietà LinkedListNode<T>.List può parlare solo di uno di essi.

Mentre è possibile capire il motivo per cui si potrebbe voler fare ciò in alcuni casi, il modo in cui il tipo .NET LinkedList<T> è stato costruito praticamente lo proibisce. Credo che questo commento doc lo spiega meglio:

La classe LinkedList<T>) fa non supporta il concatenamento, la scissione, cicli, o di altre caratteristiche che possono lasciare la lista in un incoerente Stato.

Answer 3

Qui è possibile trovare l'implementazione della mia lista collegata con O (1) concat e tempi intermedi.

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

Breve sintesi

Vantaggi vs.LinkedList NET:

• Meno consumo di memoria, quindi ogni nodo SimpleLinkedListNode trovi tre puntatori (prev, valore successivo) invece di quattro (prev, next, elenco, valore) a differenza implementazione originale NET.

• Supporta concat e Split operazioni in O (1)

• Supporta IEnumarable Reverse() enumerator in O (1) - a proposito non vedo alcuna ragione per cui non è previsto nativamente su .NET LinkedList. Il metodo di estensione appropriato richiede O (n).

Svantaggi:

• non supporta Conte.
• L'operazione di concatenazione lascia il secondo elenco in uno stato incoerente.
• L'operazione di divisione lascia l'elenco originale in uno stato incoerente.
• È possibile condividere nodi tra elenchi.

Altro:

• ho scelto una strategia alternativa per l'attuazione di enumerazione e trovare le operazioni, invece di implementazione originale più prolisso e puramente leggibile. Spero che l'impatto negativo sulle prestazioni rimanga insignificante.