Cos'è una struttura di dati collegata?

Una struttura di dati collegata è una raccolta di dati disposti in un formato simile a un elenco. Ogni pezzo di dato nell'elenco viene definito come nodo. Ogni nodo è collegato a quello successivo sulElenco tramite 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 crescere o ridursi nel corso del corsoL'esecuzione del programma. Il tipo più comune di struttura dei dati collegati è chiamato elenco collegato.

Un nodo di una struttura di dati collegati contiene generalmente due informazioni e mdash;Un riferimento ai dati effettivi da archiviare e un riferimento al nodo successivo nell'elenco. Un elenco collegato viene attraversato o cercato, attraversando ciascuno dei nodi di dati, a partire dal primo,o il capo dell'elenco. Non c'è modo di trovare informazioni in un elenco collegato senza spostarsi in sequenza attraverso i nodi dall'inizio alla fine.

Le strutture di dati più collegate utilizzerà il minor numero possibile di memoria durante il programmaesecuzione. Se viene creato un elenco collegato con un solo nodo e non vengono aggiunti altri nodi, quell'elenco prenderà la memoria richiesta per un solo nodo. Questo è in StarkContrasto con una struttura di dati dell'array in cui le dimensioni dell'intero array devono essere dichiarate e allocate all'inizio del programma e non possono essere modificate.

Elenchi collegati pagano il loro uso efficiente delle risorse di memoria richiedendopiù potenza di calcolo. Trovare un pezzo specifico di DATA in un elenco collegato richiede un looping nell'intero elenco ogni volta, quindi può essere più lento accedere alle informazioni nel mezzo dell'elenco. Anche la rimozione o il riordino in un elenco collegato può essere più intenso computazionale rispetto alla gestione diArray in cui gli elementi possono essere scambiati facilmente.

Non è necessaria una struttura di dati collegati per avere un solo riferimento al nodo successivo;Può avere diversi. Alcuni elenchi collegati hanno due riferimenti al nodo, uno al nodo successivo nell'elenco e uno al nodo precedente. Questi sono noti come elenchi doppiamente collegati. Questo può fare muoversi attraverso aElenco in entrambe le direzioni molto più velocemente, sebbene a scapito dell'aumento dell'utilizzo della memoria per la struttura dei dati.

È possibile che gli elenchi collegati abbiano tre o più riferimenti ad altri nodi nell'elenco. Ciò crea una struttura similesu un albero con interi rami di nodi che si generano da uno singolo. Questi tipi di strutture di dati sono chiamati elenchi multipli collegati. Gli elenchi multipli collegati sono particolarmente utili per gli algoritmi di ordinamento complessi che vengono utilizzati per strutturare i dati.Gli alberi di ricerca sono possibili in gran parte a causa dell'uso di strutture di dati collegate per creare più rami a lunghezza variabile.