Share
La prima struttura di dati che esamineremo è l'elenco collegato e con una buona ragione. Oltre ad essere una struttura quasi onnipresente utilizzata in tutto, dai sistemi operativi ai videogiochi, è anche un elemento fondamentale con cui possono essere create molte altre strutture di dati.
In un senso molto generale, lo scopo di un elenco collegato è quello di fornire un meccanismo coerente per archiviare e accedere a una quantità arbitraria di dati. Come suggerisce il nome, lo fa collegando i dati in una lista.
Prima di approfondire cosa significa, iniziamo esaminando come i dati vengono archiviati in un array.
Dati interi memorizzati in un array Come mostrato nella figura, i dati dell'array vengono memorizzati come un singolo blocco di memoria assegnato in modo contiguo, segmentato logicamente. I dati memorizzati nell'array sono posizionati in uno di questi segmenti e referenziati tramite la sua posizione, o indice, nell'array.
Questo è un buon modo per memorizzare i dati. La maggior parte dei linguaggi di programmazione facilita l'allocazione di array e il loro utilizzo. L'archiviazione di dati contigua offre vantaggi in termini di prestazioni (in particolare la localizzazione dei dati), l'iterazione dei dati è semplice e i dati sono accessibili direttamente dall'indice (accesso casuale) in tempo costante.
Ci sono momenti, tuttavia, quando un array non è la soluzione ideale.
Considera un programma con i seguenti requisiti:
Accentsconagua
NextValue metodo) finché non si incontra il numero 0xFFFF.ProcessItems metodo.Poiché i requisiti indicano che è necessario passare più valori a ProcessItems metodo in una singola chiamata, una soluzione ovvia implicherebbe l'utilizzo di una matrice di numeri interi. Per esempio:
void LoadData () // Supponiamo che 20 sia sufficiente per contenere i valori. int [] values = new int [20]; per (int i = 0; i < values.Length; i++) if (values[i] == 0xFFFF) break; values[i] = NextValue(); ProcessItems(values); void ProcessItems(int[] values) //… Process data.
Questa soluzione ha diversi problemi, ma il più clamoroso si vede quando vengono letti più di 20 valori. Poiché il programma è ora, i valori da 21 a n vengono semplicemente ignorati. Questo potrebbe essere mitigato allocando più di 20 valori, forse 200 o 2000. Forse la dimensione potrebbe essere configurata dall'utente, o forse se la matrice diventasse piena si potrebbe allocare una matrice più grande e tutti i dati esistenti copiati in essa. Alla fine queste soluzioni creano complessità e sprecano memoria.
Ciò di cui abbiamo bisogno è una collezione che ci permetta di aggiungere un numero arbitrario di valori interi e quindi di enumerare su quei numeri interi nell'ordine in cui sono stati aggiunti. La raccolta non dovrebbe avere una dimensione massima fissa e l'indicizzazione dell'accesso casuale non è necessaria. Ciò di cui abbiamo bisogno è una lista collegata.
Prima di andare avanti e imparare come è progettata e implementata la struttura dati dell'elenco collegato, vediamo in anteprima quale potrebbe essere la nostra soluzione definitiva.
static void LoadItems () LinkedList list = new LinkedList (); while (true) int value = NextValue (); if (value! = 0xFFFF) list.Add (valore); else break; ProcessItems (elenco); ProcessItem void statico (elenco LinkedList) // ... Dati di processo.
Si noti che tutti i problemi con la soluzione di array non esistono più. Non ci sono più problemi con la matrice non è abbastanza grande o l'allocazione di più del necessario.
Dovresti anche notare che questa soluzione informa alcune delle decisioni progettuali che prenderemo in seguito, cioè che il Lista collegata la classe accetta un argomento di tipo generico e implementa il IEnumerable interfaccia.
Al centro della struttura di dati dell'elenco collegato è la classe Node. Un nodo è un contenitore che offre la possibilità di memorizzare i dati e connettersi ad altri nodi.
Un nodo dell'elenco collegato contiene dati e una proprietà che punta al nodo successivo Nella sua forma più semplice, una classe Node che contiene numeri interi potrebbe avere questo aspetto:
public class Node public int Value get; impostato; Nodo pubblico Next get; impostato;
Con questo possiamo ora creare una lista concatenata molto primitiva. Nell'esempio seguente assegneremo tre nodi (primo, medio e ultimo) e quindi li collegheremo in un elenco.
// + ----- + ------ + // | 3 | null + // + ----- + ------ + Node first = new Node Value = 3; // + ----- + ------ + + ----- + ------ + // | 3 | null + | 5 | null + // + ----- + ------ + + ----- + ------ + Node middle = new Node Value = 5; // + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + // + ----- + ------ + + ----- + ------ + first.Next = middle; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + Node last = new Nodo valore = 7; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | * --- + -> | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + middle.Next = scorso;
Ora abbiamo un elenco collegato che inizia con il nodo primo e termina con il nodo scorso. Il Il prossimo la proprietà dell'ultimo nodo punta a null che è l'indicatore di fine elenco. Dato questo elenco, possiamo eseguire alcune operazioni di base. Ad esempio, il valore di ciascun nodo Dati proprietà:
statico privato vuoto PrintList (nodo nodo) while (node! = null) Console.WriteLine (node.Value); node = node.Next;
Il StampaLista il metodo funziona ripetendo su ciascun nodo nell'elenco, stampando il valore del nodo corrente e quindi passando al nodo puntato da Il prossimo proprietà.
Ora che abbiamo una comprensione di come potrebbe essere un nodo della lista collegata, diamo un'occhiata al reale LinkedListNode classe.
public class LinkedListNode /// /// Costruisce un nuovo nodo con il valore specificato. /// public LinkedListNode (valore T) valore = valore; /// /// Il valore del nodo. /// valore T pubblico get; set interno; /// /// Il nodo successivo nell'elenco collegato (null se ultimo nodo). /// public LinkedListNode Successivo get; set interno;
Prima di implementare il nostro Lista collegata classe, dobbiamo pensare a cosa vorremmo essere in grado di fare con la lista.
In precedenza abbiamo visto che la raccolta deve supportare dati fortemente tipizzati, quindi sappiamo che vogliamo creare un'interfaccia generica.
Poiché utilizziamo il framework .NET per implementare l'elenco, è logico che vogliamo che questa classe sia in grado di agire come gli altri tipi di raccolta incorporati. Il modo più semplice per farlo è implementare il ICollection interfaccia. Avviso che scelgo ICollection e non IList. Questo perché il IList l'interfaccia aggiunge la possibilità di accedere ai valori per indice. Mentre l'indicizzazione diretta è generalmente utile, non può essere implementata in modo efficiente in una lista collegata.
Tenendo presente questi requisiti, possiamo creare uno stub di classe base, quindi attraverso il resto della sezione possiamo compilare questi metodi.
public class LinkedList: System.Collections.Generic.ICollection public void Add (elemento T) throw new System.NotImplementedException (); public void Clear () throw new System.NotImplementedException (); public bool Contains (T item) lanciare System.NotImplementedException (); public void CopyTo (T [] array, int arrayIndex) lanciare System.NotImplementedException (); public int Count get; set privato; public bool IsReadOnly get throw new System.NotImplementedException (); public bool Remove (T item) lanciare System.NotImplementedException (); public System.Collections.Generic.IEnumerator GetEnumerator () throw new System.NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () throw new System.NotImplementedException ();
| Comportamento | Aggiunge il valore fornito alla fine dell'elenco collegato. |
| Prestazione | O (1) |
L'aggiunta di un elemento a un elenco collegato prevede tre passaggi:
LinkedListNode esempio.Il prossimo proprietà dell'ultimo nodo al nuovo nodo.La chiave è sapere quale nodo è l'ultimo nodo nell'elenco. Ci sono due modi in cui possiamo saperlo. Il primo modo è quello di tenere traccia del primo nodo (il nodo "testa") e percorrere l'elenco fino a quando non abbiamo trovato l'ultimo nodo. Questo approccio non richiede di tenere traccia dell'ultimo nodo, che salva un valore di memoria di riferimento (qualunque sia la dimensione del puntatore della piattaforma), ma richiede che eseguiamo un attraversamento dell'elenco ogni volta che viene aggiunto un nodo. Questo farebbe Inserisci un'operazione O (n).
Il secondo approccio richiede che teniamo traccia dell'ultimo nodo (il nodo "coda") nell'elenco e quando aggiungiamo il nuovo nodo accediamo semplicemente direttamente al nostro riferimento memorizzato. Questo è un algoritmo O (1) e quindi l'approccio preferito.
La prima cosa che dobbiamo fare è aggiungere due campi privati al Lista collegata classe: riferimenti ai primi nodi (testa) e ultimi (coda).
_head LinkedListNode privato; LinkedListNode privato _tail;
Quindi è necessario aggiungere il metodo che esegue i tre passaggi.
pubblico vuoto Aggiungi (valore T) nodo LinkedListNode = nuovo LinkedListNode (valore); if (_head == null) _head = node; _tail = node; else _tail.Next = node; _tail = node; Count ++;
Innanzitutto, assegna il nuovo LinkedListNode esempio. Successivamente, controlla se l'elenco è vuoto. Se la lista è vuota, il nuovo nodo viene aggiunto semplicemente assegnando il _capo e _coda riferimenti al nuovo nodo. Il nuovo nodo è ora sia il primo che l'ultimo nodo nell'elenco. Se la lista non è vuota, il nodo viene aggiunto alla fine della lista e il _coda il riferimento viene aggiornato per puntare alla nuova fine dell'elenco.
Il Contare la proprietà viene incrementata quando viene aggiunto un nodo per garantire il ICollection. Contare proprietà restituisce il valore preciso.
| Comportamento | Rimuove il primo nodo nell'elenco il cui valore è uguale al valore fornito. Il metodo restituisce true se un valore è stato rimosso. Altrimenti restituisce falso. |
| Prestazione | Sopra) |
Prima di parlare del Rimuovere algoritmo, diamo un'occhiata a cosa sta cercando di realizzare. Nella figura seguente, ci sono quattro nodi in una lista. Vogliamo rimuovere il nodo con il valore tre.
Una lista collegata con quattro valori Al termine della rimozione, la lista verrà modificata in modo tale che il file Il prossimo proprietà sul nodo con il valore due punti al nodo con il valore quattro.
L'elenco collegato con il nodo 3 rimosso L'algoritmo di base per la rimozione del nodo è:
Come sempre, il diavolo è nei dettagli. Ci sono alcuni casi a cui dobbiamo pensare quando rimuoviamo un nodo:
_capo e _coda campi a nullo._capo campo per indicare il nuovo nodo principale._coda campo per fare riferimento al penultimo nodo nell'elenco e impostarne il relativo Il prossimo proprietà a nullo.public bool Remove (T item) LinkedListNode previous = null; LinkedListNode current = _head; // 1: lista vuota: non fare nulla. // 2: nodo singolo: il precedente è nullo. // 3: molti nodi: // a: il nodo da rimuovere è il primo nodo. // b: il nodo da rimuovere è il mezzo o l'ultimo. while (current! = null) if (current.Value.Equals (item)) // È un nodo nel mezzo o alla fine. if (previous! = null) // Caso 3b. // Prima: Testa -> 3 -> 5 -> null // Dopo: Testa -> 3 ------> null previous.Next = current.Next; // Era la fine, quindi aggiorna _tail. if (current.Next == null) _tail = previous; else // Caso 2 o 3a. // Prima: Testa -> 3 -> 5 // Dopo: Testa ------> 5 // Testa -> 3 -> null // Testa ------> null _head = _head.Next; // L'elenco è vuoto? if (_head == null) _tail = null; Contare--; ritorna vero; precedente = corrente; current = current.Next; return false;
Il Contare la proprietà viene decrementata quando viene rimosso un nodo per garantire il ICollection. Contare proprietà restituisce il valore preciso.
| Comportamento | Restituisce un valore booleano che indica se il valore fornito esiste all'interno dell'elenco collegato. |
| Prestazione | Sopra) |
Il contiene il metodo è abbastanza semplice. Esamina ogni nodo nell'elenco, dal primo all'ultimo, e restituisce true non appena viene trovato un nodo che corrisponde al parametro. Se viene raggiunta la fine dell'elenco e il nodo non viene trovato, il metodo restituisce falso.
public bool Contains (T item) LinkedListNode current = _head; while (current! = null) if (current.Value.Equals (item)) return true; current = current.Next; return false;
| Comportamento | Restituisce un'istanza IEnumerator che consente di enumerare i valori dell'elenco collegato dal primo all'ultimo. |
| Prestazione | Il ritorno dell'istanza dell'enumeratore è un'operazione O (1). L'enumerazione di ogni elemento è un'operazione O (n). |
GetEnumerator è implementato enumerando l'elenco dal primo all'ultimo nodo e utilizza il C # dare la precedenza parola chiave per restituire il valore del nodo corrente al chiamante.
Si noti che LinkedList implementa il comportamento di iterazione nel file IEnumerable versione del metodo GetEnumerator e rimanda a questo comportamento nella versione IEnumerable.
IEnumerator IEnumerable.GetEnumerator () LinkedListNode current = _head; while (current! = null) yield return current.Value; current = current.Next; IEnumerator IEnumerable.GetEnumerator () return ((IEnumerable) this) .GetEnumerator ();
| Comportamento | Rimuove tutti gli elementi dall'elenco. |
| Prestazione | O (1) |
Il Chiaro il metodo imposta semplicemente il _capo e _coda campi a null per cancellare l'elenco. Poiché .NET è un linguaggio di raccolta dei rifiuti, i nodi non devono essere rimossi esplicitamente. È responsabilità del chiamante, non dell'elenco collegato, assicurare che se i nodi contengono IDisposable riferimenti sono stati smaltiti correttamente.
public void Clear () _head = null; _tail = null; Conteggio = 0;
| Comportamento | Copia il contenuto dell'elenco collegato dall'inizio alla fine nell'array fornito, iniziando dall'indice dell'array specificato. |
| Prestazione | Sopra) |
Il Copia a Il metodo semplicemente scorre le voci dell'elenco e usa un semplice compito per copiare gli elementi nell'array. È responsabilità del chiamante assicurarsi che l'array di destinazione contenga lo spazio libero appropriato per accogliere tutti gli elementi nell'elenco.
public void CopyTo (T [] array, int arrayIndex) LinkedListNode current = _head; while (current! = null) array [arrayIndex ++] = current.Value; current = current.Next;
| Comportamento | Restituisce un numero intero che indica il numero di elementi attualmente nell'elenco. Quando l'elenco è vuoto, il valore restituito è 0. |
| Prestazione | O (1) |
Contare è semplicemente una proprietà implementata automaticamente con un getter pubblico e un setter privato. Il vero comportamento si verifica nel Inserisci, Rimuovere, e Chiaro metodi.
int pubblico count; set privato;
| Comportamento | Restituisce false se l'elenco non è di sola lettura. |
| Prestazione | O (1) |
public bool IsReadOnly get return false;
La classe LinkedList che abbiamo appena creato è conosciuta come una lista singola e collegata. Ciò significa che esiste un solo collegamento unidirezionale tra un nodo e il nodo successivo nell'elenco. Esiste una variazione comune dell'elenco collegato che consente al chiamante di accedere all'elenco da entrambe le estremità. Questa variazione è conosciuta come una lista doppiamente collegata.
Per creare una lista doppiamente collegata dovremo prima modificare la nostra classe LinkedListNode per avere una nuova proprietà denominata Previous. Precedente agirà come Avanti, solo che punterà al nodo precedente nell'elenco.
Una lista doppiamente collegata utilizzando una proprietà del nodo Precedente Le seguenti sezioni descriveranno solo le modifiche tra la lista concatenata e la nuova lista doppiamente collegata.
L'unico cambiamento che sarà fatto nel LinkedListNode class è l'aggiunta di una nuova proprietà chiamata Precedente che punta al precedente LinkedListNode nell'elenco collegato o restituisce nullo se è il primo nodo nell'elenco.
public class LinkedListNode /// /// Costruisce un nuovo nodo con il valore specificato. /// /// public LinkedListNode (valore T) valore = valore; /// /// Il valore del nodo. /// valore T pubblico get; set interno; /// /// Il nodo successivo nell'elenco collegato (null se ultimo nodo). /// public LinkedListNode Successivo get; set interno; /// /// Il nodo precedente nell'elenco collegato (null se primo nodo). /// public LinkedListNode Precedente get; set interno;
Mentre la lista collegata singolarmente ha solo aggiunto nodi alla fine della lista, l'elenco doppiamente collegato consentirà di aggiungere nodi all'inizio e alla fine della lista usando addfirst e addlast, rispettivamente. Il ICollection. Inserisci il metodo sarà rimandato al addlast metodo per mantenere la compatibilità con il singolo collegato Elenco classe.
| Comportamento | Aggiunge il valore fornito in cima all'elenco. |
| Prestazione | O (1) |
Quando si aggiunge un nodo nella parte anteriore dell'elenco, le azioni sono molto simili all'aggiunta a un elenco collegato separatamente.
Il prossimo proprietà del nuovo nodo al vecchio nodo principale.Precedente proprietà del vecchio nodo principale sul nuovo nodo._coda campo (se necessario) e incrementare Contare.vuoto pubblico AddFirst (valore T) nodo LinkedListNode = nuovo LinkedListNode (valore); // Salva il nodo principale in modo da non perderlo. LinkedListNode temp = _head; // Punta la testa al nuovo nodo. _head = node; // Inserisci il resto dell'elenco dietro la testa. _head.Next = temp; if (Count == 0) // Se l'elenco era vuoto, head and tail dovrebbe // puntare entrambi al nuovo nodo. _tail = _head; else // Before: head -------> 5 <-> 7 -> null // After: head -> 3 <-> 5 <-> 7 -> null temp.Previous = _head; Count ++;
| Comportamento | Aggiunge il valore fornito alla fine dell'elenco. |
| Prestazione | O (1) |
Aggiungere un nodo alla fine dell'elenco è ancora più semplice che aggiungerne uno all'inizio.
Il nuovo nodo viene semplicemente aggiunto alla fine dell'elenco, aggiornando lo stato di _coda e _capo come appropriato, e Contare è incrementato.
public void AddLast (valore T) LinkedListNode node = new LinkedListNode (valore); if (Count == 0) _head = node; else _tail.Next = node; // Prima: Testa -> 3 <-> 5 -> null // After: Head -> 3 <-> 5 <-> 7 -> null // 7.Precedente = 5 nodo.Precedente = _tail; _tail = node; Conte ++;
E come accennato in precedenza, ICollection.Aggiungi ora chiamerà semplicemente addlast.
pubblico vuoto Aggiungi (valore T) AddLast (valore);
Piace Inserisci, il Rimuovere il metodo verrà esteso per supportare la rimozione dei nodi dall'inizio o dalla fine dell'elenco. Il ICollection.Rimuoverà il metodo per rimuovere gli elementi dall'inizio con l'unica modifica di aggiornare l'appropriato Precedente proprietà.
| Comportamento | Rimuove il primo valore dall'elenco. Se l'elenco è vuoto, non viene eseguita alcuna azione. Restituisce true se un valore è stato rimosso. Altrimenti restituisce falso. |
| Prestazione | O (1) |
RemoveFirst aggiorna la lista impostando la lista collegata capo proprietà al secondo nodo nell'elenco e aggiornando il suo Precedente proprietà a nullo. Questo rimuove tutti i riferimenti al nodo principale precedente, rimuovendolo dall'elenco. Se la lista contenesse solo un singleton, o fosse vuota, la lista sarà vuota (il capo e coda le proprietà saranno nullo).
pubblico vuoto RemoveFirst () if (Count! = 0) // Before: Head -> 3 <-> 5 // After: Head -------> 5 // Head -> 3 -> null // Head ------> null _head = _head.Next; Contare--; if (Count == 0) _tail = null; else // 5.Precedente era 3; ora è nullo. _head.Previous = null;
| Comportamento | Rimuove l'ultimo nodo dall'elenco. Se l'elenco è vuoto, non viene eseguita alcuna azione. Restituisce true se un valore è stato rimosso. Altrimenti, restituisce false. |
| Prestazione | O (1) |
RemoveLast funziona impostando la lista coda proprietà per essere il nodo che precede il nodo di coda corrente. Ciò rimuove l'ultimo nodo dall'elenco. Se la lista era vuota o aveva solo un nodo, quando il metodo restituisce il capo e coda proprietà, saranno entrambi nullo.
public void RemoveLast () if (Count! = 0) if (Count == 1) _head = null; _tail = null; else // Before: Head -> 3 -> 5 -> 7 // Tail = 7 // After: Head -> 3 -> 5 -> null // Tail = 5 // Null out 5's Next proprietà. _tail.Previous.Next = null; _tail = _tail.Previous; Contare--;
| Comportamento | Rimuove il primo nodo nell'elenco il cui valore è uguale al valore fornito. Il metodo restituisce true se un valore è stato rimosso. Altrimenti restituisce falso. |
| Prestazione | Sopra) |
Il ICollection. Rimuovere metodo è quasi identico alla versione collegata singolarmente tranne che il Precedente la proprietà è ora aggiornata durante l'operazione di rimozione. Per evitare codice ripetuto, il metodo chiama RemoveFirst quando viene determinato che il nodo che viene rimosso è il primo nodo nell'elenco.
public bool Remove (T item) LinkedListNode previous = null; LinkedListNode current = _head; // 1: lista vuota: non fare nulla. // 2: nodo singolo: il precedente è nullo. // 3: molti nodi: // a: il nodo da rimuovere è il primo nodo. // b: il nodo da rimuovere è il mezzo o l'ultimo. while (current! = null) // Head -> 3 -> 5 -> 7 -> null // Head -> 3 ------> 7 -> null if (current.Value.Equals (item) ) // È un nodo nel mezzo o alla fine. if (previous! = null) // Caso 3b. previous.Next = current.Next; // Era la fine, quindi aggiorna _tail. if (current.Next == null) _tail = previous; else // Before: Head -> 3 <-> 5 <-> 7 -> null // After: Head -> 3 <-------> 7 -> null // previous = 3 // current = 5 // current.Next = 7 // So ... 7.Precedente = 3 current.Next.Previous = previous; Contare--; else // Caso 2 o 3a. RemoveFirst (); return true; precedente = corrente; current = current.Next; return false;
Possiamo aggiungere nodi all'inizio e alla fine della lista, quindi? Perché ci importa? Allo stato attuale, il doppio collegato Elenco la classe non è più potente della sola lista concatenata. Ma con una sola piccola modifica, possiamo aprire tutti i tipi di comportamenti possibili. Esponendo il capo e coda Proprietà come proprietà pubbliche di sola lettura, il consumatore della lista collegata sarà in grado di implementare tutti i tipi di nuovi comportamenti.
public LinkedListNode Head get return _head; public LinkedListNode Tail get return _tail;
Con questo semplice cambiamento possiamo enumerare manualmente la lista, che ci permette di eseguire enumerazione e ricerca inversa (tail-to-head).
Ad esempio, il seguente esempio di codice mostra come utilizzare la lista Coda e Precedente proprietà per enumerare l'elenco al contrario ed eseguire alcune elaborazioni su ciascun nodo.
public void ProcessListBackwards () LinkedList list = new LinkedList (); PopulateList (lista); LinkedListNode current = list.Tail; while (corrente! = null) ProcessNode (corrente); current = current.Previous;
Inoltre, il doppio collegato Elenco classe ci consente di creare facilmente il deque classe, che è di per sé un elemento fondamentale per altre classi. Discuteremo di questa classe più avanti in un'altra sezione.
