La differenza tra l'elenco connesso singolarmente e la lista dei collegamenti duplici

Elenco collegato singolarmente vs Elenco collegato a duplice

Elenco collegato è una struttura di dati lineare utilizzata per memorizzare una raccolta di dati. Un elenco collegato assegna la memoria ai suoi elementi separatamente nel proprio blocco di memoria e la struttura complessiva viene 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 della sequenza. Un elenco doppio collegato contiene una sequenza di nodi in cui ogni nodo contiene un riferimento al nodo successivo oltre al nodo precedente.

<1>

Elenco singolo collegato

Ogni elemento in un elenco collegato singolarmente ha due campi come mostrato in Figura 1. Il campo dati contiene i dati reali memorizzati e il campo successivo contiene il riferimento all'elemento successivo nella catena. Il primo elemento dell'elenco collegato viene memorizzato come testa dell'elenco collegato.

La figura 2 rappresenta 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 ha un valore nullo nel suo campo successivo. È possibile accedere a qualsiasi elemento dell'elenco partendo dalla testa e seguendo il puntatore successivo fino a quando non si incontra l'elemento richiesto.

Lista Collegata Doppia

Ogni elemento in un elenco doppio collegato ha tre campi come mostrato nella Figura 3. Simile a un elenco collegato singolarmente, il campo dati contiene i dati reali memorizzati e il campo successivo contiene il riferimento all'elemento successivo nella catena. Inoltre, il campo precedente contiene il riferimento all'elemento precedente della catena. Il primo elemento dell'elenco collegato viene memorizzato come testa dell'elenco collegato.

La figura 4 rappresenta un elenco a due elementi con tre elementi. Tutti gli elementi intermedi memorizzano i riferimenti agli elementi precedenti e precedenti. L'ultimo elemento dell'elenco contiene un valore nullo nel suo campo successivo e il primo elemento dell'elenco contiene un valore nullo nel suo campo precedente. L'elenco dei collegamenti duplicati può essere attraversato in avanti seguendo i riferimenti successivi in ​​ciascun elemento e, analogamente, può essere attraversato indietro utilizzando i riferimenti precedenti in ciascun elemento.

Qual è la differenza tra Elenco Singly Linked e Elenco Collegato Doubly?

Ogni elemento dell'elenco singolo collegato contiene un riferimento all'elemento successivo dell'elenco, mentre ogni elemento nell'elenco a doppio collegamento contiene riferimenti all'elemento successivo nonché all'elemento precedente dell'elenco. Gli elenchi collegati a duplice distanza richiedono più spazio per ciascun elemento dell'elenco e le operazioni elementari, ad esempio l'inserimento e l'eliminazione, sono più complesse poiché devono affrontare due riferimenti. Ma gli elenchi a due link permettono una manipolazione più facile in quanto consente di attraversare l'elenco in avanti e indietro.