Elenco a collegamento singolo vs elenco a collegamento doppio
L'elenco collegato è una struttura di dati lineare utilizzata per memorizzare una raccolta di dati. Una lista concatenata alloca memoria ai suoi elementi separatamente nel proprio blocco di memoria e la struttura complessiva si ottiene collegando questi elementi come anelli di una catena. Un elenco collegato singolarmente è costituito da una sequenza di nodi e ogni nodo ha un riferimento al nodo successivo nella sequenza. Una lista doppiamente collegata contiene una sequenza di nodi in cui ogni nodo contiene un riferimento al nodo successivo e al nodo precedente.
Elenco collegato singolarmente
Ogni elemento in un elenco collegato singolarmente ha due campi come mostrato nella Figura 1. Il campo dati contiene i dati effettivi memorizzati e il campo successivo contiene il riferimento all'elemento successivo nella catena. Il primo elemento dell'elenco collegato viene memorizzato come capo dell'elenco collegato.
La figura 2 mostra un elenco collegato singolarmente con tre elementi. Ogni elemento memorizza i suoi dati e tutti gli elementi tranne l'ultimo memorizzano un riferimento all'elemento successivo. L'ultimo elemento contiene un valore nullo nel campo successivo. È possibile accedere a qualsiasi elemento nell'elenco partendo dall'inizio e seguendo il puntatore successivo fino a quando non si incontra l'elemento richiesto.
Lista doppiamente collegata
Ogni elemento in una lista doppiamente collegata ha tre campi come mostrato nella Figura 3. Simile all'elenco collegato singolarmente, il campo dati contiene i dati effettivi memorizzati e il campo successivo contiene il riferimento all'elemento successivo nella catena. Inoltre, il campo precedente contiene il riferimento all'elemento precedente nella catena. Il primo elemento dell'elenco collegato viene memorizzato come capo dell'elenco collegato.
La figura 4 mostra un elenco doppiamente collegato con tre elementi. Tutti gli elementi intermedi memorizzano i riferimenti al primo e agli elementi precedenti. L'ultimo elemento nell'elenco contiene un valore nullo nel campo successivo e il primo elemento nell'elenco contiene un valore nullo nel campo precedente. L'elenco doppiamente collegato può essere attraversato in avanti seguendo i riferimenti successivi in ciascun elemento e allo stesso modo può essere attraversato all'indietro utilizzando i riferimenti precedenti in ciascun elemento.
Qual è la differenza tra l'elenco con collegamento singolo e l'elenco con collegamento doppio?
Ogni elemento nell'elenco con collegamento singolo contiene un riferimento all'elemento successivo nell'elenco, mentre ogni elemento nell'elenco con collegamento doppio contiene riferimenti all'elemento successivo e all'elemento precedente nell'elenco. Gli elenchi doppiamente collegati richiedono più spazio per ogni elemento dell'elenco e le operazioni elementari come l'inserimento e l'eliminazione sono più complesse poiché devono gestire due riferimenti. Ma le liste a doppio collegamento consentono una manipolazione più semplice poiché consente di attraversare l'elenco in avanti e indietro.
