Differenza tra elenco collegato singolarmente e elenco collegato dobabilmente

Elenco collegato singolarmente vs elenco collegato dobbilmente

L'elenco collegato è una struttura di dati lineare utilizzata per memorizzare una raccolta di dati. Una lista collegata assegna la memoria ai suoi elementi separatamente nel proprio blocco di memoria e la struttura generale è ottenuta 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 e al nodo precedente.

Elenco collegato singolarmente

Ogni elemento in una lista collegata 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 è memorizzato come capo dell'elenco collegato.

La Figura 2 mostra una lista collegata 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 suo campo successivo. È possibile accedere a qualsiasi elemento nella lista iniziando dalla testa e seguendo il puntatore successivo fino a quando non si incontra l'elemento richiesto.

Lista Doubly Linked

Ogni elemento in una lista doppiamente collegata ha tre campi come mostrato in Figura 3. Simile alla lista concatenata, 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 è memorizzato come capo dell'elenco collegato.

La Figura 4 mostra una lista doppiamente collegata con tre elementi. Tutti gli elementi intermedi memorizzano i riferimenti agli elementi primo e precedente. 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 concatenata può essere spostata in avanti seguendo i riferimenti successivi in ​​ciascun elemento e allo stesso modo può essere attraversata all'indietro usando i riferimenti precedenti in ciascun elemento.

Qual è la differenza tra Elenco collegato singolarmente e Elenco collegato in modo duale?

Ogni elemento dell'elenco linkato singolarmente contiene un riferimento all'elemento successivo nell'elenco, mentre ogni elemento nell'elenco con collegamenti concatenati contiene riferimenti all'elemento successivo e all'elemento precedente nell'elenco. Gli elenchi collegati doppi richiedono più spazio per ogni elemento nell'elenco e le operazioni elementari come l'inserimento e la cancellazione sono più complesse poiché devono gestire due riferimenti. Ma le liste di collegamenti doppiamente consentono una più facile manipolazione poiché consentono di attraversare la lista in direzioni avanti e indietro.