Elenco collegato singolarmente vs elenco collegato doppio
L'elenco collegato è una struttura dati lineare utilizzata per archiviare una raccolta di dati. Una lista concatenata alloca la memoria ai propri elementi separatamente nel proprio blocco di memoria e la struttura complessiva si ottiene collegando questi elementi come collegamenti in 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 oltre che 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 effettivamente memorizzati e il campo successivo contiene il riferimento all'elemento successivo della catena. Il primo elemento dell'elenco collegato viene memorizzato come inizio dell'elenco collegato.
La Figura 2 mostra un elenco collegato singolarmente con tre elementi. Ogni elemento memorizza i propri 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 iniziando dalla testa e seguendo il puntatore successivo fino a incontrare l'elemento richiesto.
Elenco doppiamente collegato
Ogni elemento in un elenco a doppio collegamento ha tre campi come mostrato nella Figura 3. Simile all'elenco a collegamento singolo, il campo dati contiene i dati effettivi memorizzati e il campo successivo contiene il riferimento all'elemento successivo della catena. Inoltre, il campo precedente contiene il riferimento all'elemento precedente nella catena. Il primo elemento dell'elenco collegato viene memorizzato come inizio dell'elenco collegato.
La Figura 4 mostra un elenco a doppio collegamento con tre elementi. Tutti gli elementi intermedi memorizzano i riferimenti al primo e al precedente elemento. 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. La lista doppiamente collegata può essere spostata in avanti seguendo i riferimenti successivi in ogni elemento e allo stesso modo può essere spostata all'indietro utilizzando i riferimenti precedenti in ogni elemento.
Qual è la differenza tra l'elenco collegato singolarmente e l'elenco collegato doppiamente?
Ogni elemento nell'elenco a collegamento singolo contiene un riferimento all'elemento successivo nell'elenco, mentre ogni elemento nell'elenco a collegamento doppio contiene riferimenti all'elemento successivo nonché all'elemento precedente nell'elenco. Le liste doppiamente concatenate richiedono più spazio per ogni elemento della lista e operazioni elementari come l'inserimento e la cancellazione sono più complesse poiché devono trattare con due riferimenti. Ma doppiamente gli elenchi di collegamento consentono una manipolazione più semplice poiché consente di attraversare l'elenco in direzioni avanti e indietro.
