Una struttura di dati collegata è una raccolta di dati disposti in un formato simile a una lista. Ogni pezzo di dato nella lista è indicato come un nodo. Ogni nodo è connesso a quello successivo nella lista da 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 dati collegata è chiamato elenco concatenato.
Un nodo di una struttura di dati collegata generalmente contiene due informazioni: un riferimento ai dati effettivi che vengono archiviati e un riferimento al nodo successivo dell’elenco. attraverso ciascuno dei nodi di dati, iniziando dal primo o dall’inizio della lista.Non c’è modo di trovare informazioni in una lista collegata senza spostarsi sequenzialmente attraverso i nodi dall’inizio alla fine.
La maggior parte delle strutture di dati concatenate utilizzerà meno memoria possibile durante l’esecuzione del programma.Se viene creata una lista concatenata con un solo nodo e non vengono aggiunti altri nodi, quella lista occuperà il memoria richiesta per un solo nodo, in netto contrasto con una struttura dati array in cui la dimensione dell’intero array deve essere dichiarata e allocata all’inizio del programma e non può essere modificata .
Gli elenchi collegati pagano per l’uso efficiente delle risorse di memoria richiedendo più 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 Rimuovere o riordinare i dati in un elenco collegato può anche essere più impegnativo dal punto di vista computazionale rispetto alla gestione di un array in cui gli elementi possono essere scambiati facilmente.
Non è necessario che una struttura dati collegata abbia un solo riferimento al nodo successivo; può averne diversi. Alcune liste concatenate hanno due riferimenti di nodo, uno al nodo successivo nell’elenco e uno al nodo precedente. Questi sono noti come elenchi doppiamente collegati. Questo può rendere lo spostamento attraverso un list in entrambe le direzioni molto più velocemente, anche se a spese di un maggiore utilizzo della memoria per la struttura dei dati.
È possibile che le liste concatenate abbiano tre o più riferimenti ad altri nodi della lista.Questo crea una struttura simile ad un albero con interi rami di nodi generati da uno solo.Questi tipi di dati strutture sono chiamate liste concatenate multiple.Le liste concatenate multiple sono particolarmente utili per algoritmi di ordinamento complessi che vengono utilizzati per strutturare i dati.Gli alberi di ricerca sono possibili in gran parte grazie all’uso di strutture dati collegate per creare più rami di lunghezza variabile.