Che cos'è una struttura dati collegata?
Una struttura di dati collegata è una raccolta di dati disposti in un formato simile a un elenco. Ogni pezzo di riferimento nell'elenco viene definito nodo. Ogni nodo è collegato al successivo nell'elenco mediante un riferimento all'indirizzo di memoria di quel nodo successivo. Le strutture di dati collegate vengono utilizzate al posto di un array quando il numero di nodi in un elenco è sconosciuto o potrebbe aumentare o ridursi nel corso del esecuzione del programma Il tipo più comune di struttura di dati collegati è chiamato elenco collegato.
Un nodo di una struttura di dati collegati generalmente contiene due informazioni: un riferimento ai dati effettivi archiviati e un riferimento al nodo successivo nell'elenco. Un elenco collegato viene attraversato o cercato facendo un passo attraverso ciascuno dei nodi di dati, a partire dal primo, o dal capo dell'elenco. Non è possibile trovare informazioni in un elenco collegato senza spostarsi in sequenza tra i nodi dall'inizio alla fine.
La maggior parte delle strutture dati collegate utilizzerà meno memoria possibile durante l'esecuzione del programma. Se viene creato un elenco collegato con un solo nodo e non vengono aggiunti altri nodi, tale elenco occuperà il memoria richiesta per un solo nodo, in netto contrasto con una struttura di dati di array in cui la dimensione dell'intero array deve essere dichiarata e allocata all'avvio del programma e non può essere modificata .
Gli elenchi collegati pagano per il loro uso efficiente delle risorse di memoria richiedendo maggiore potenza di calcolo. Trovare un dato specifico in un elenco collegato richiede di scorrere l'intero elenco ogni volta, quindi può essere più lento accedere alle informazioni in al centro dell'elenco Anche la rimozione o il riordino dei dati in un elenco collegato può essere più intensivo dal punto di vista computazionale rispetto alla gestione di un array in cui gli elementi possono essere scambiati facilmente.
Non è necessario che una struttura di dati collegata abbia un solo riferimento al nodo successivo; può avere diversi. Alcuni elenchi collegati hanno due riferimenti a nodo, uno al nodo successivo nell'elenco e uno al nodo precedente. Questi sono noti come elenchi doppiamente collegati. elencare in entrambe le direzioni molto più velocemente, anche se a scapito di un maggiore utilizzo della memoria per la struttura dei dati.
È possibile che gli elenchi collegati abbiano tre o più riferimenti ad altri nodi nell'elenco, creando una struttura simile a un albero con interi rami di nodi che si generano da un singolo. le strutture sono chiamate elenchi moltiplicati e gli elenchi moltiplicati sono particolarmente utili per algoritmi di ordinamento complessi che vengono utilizzati per strutturare i dati. Gli alberi di ricerca sono in gran parte possibili grazie all'uso di strutture di dati collegate per creare più rami di lunghezza variabile.