Lista concatenata: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
formattazione |
||
Riga 56:
== Applicazioni delle liste concatenate ==
Le liste concatenate sono utilizzate come un mattone per la costruzione di molte altre strutture dati, come
Alle volte le liste concatenate sono utilizzate per implementare [[vettore associativo|vettori associativi]], e vengono chiamate in questo contesto '''liste associative'''. C'è poco da dire su queste liste; non sono molto efficienti e risultano, persino su piccoli insiemi di dati, meno efficienti di strutture dati basate su [[albero binario di ricerca bilanciato|alberi]] o [[hash table]]. Tuttavia a volte una lista concatenata è creata dinamicamente da un sottoinsieme di nodi di un albero e utilizzata per attraversare un insieme in modo più efficiente.
Riga 84:
È possibile risparmiare ulteriormente memoria, in alcuni casi, condividendo la stessa "coda" di elementi tra due o più liste — ossia, le liste avranno la stessa sequenza finale di elementi. In questo modo è possibile aggiungere nuovi elementi in cima alla lista mantenendo un riferimento sia alla nuova che alla vecchia versione — si tratta di un semplice esempio di [[struttura dati persistente]].
Dall'altro lato, mentre gli array permettono un [[accesso casuale]], le liste concatenate permettono soltanto un [[accesso sequenziale]] agli elementi. Le liste concatenate semplici, infatti, possono essere percorse soltanto in una direzione, rendendole inadatte ad applicazioni in cui è utile cercare velocemente un elemento utilizzando il suo indice, come nel caso dell'[[heapsort|''heapsort'']]. L'accesso sequenziale è, inoltre, più veloce negli array che nelle liste concatenate su molte macchine, grazie alla presenza di riferimenti locali e [[cache]] dei dati. Le liste concatenate non ricevono quasi nessun beneficio da una cache.
Un altro svantaggio delle liste concatenate è lo spazio in eccesso necessario per memorizzare i riferimenti, cosa che le rende poco pratiche per liste di piccoli elementi come [[Carattere (informatica)|caratteri]] e valori [[Booleano (informatica)|booleani]]. L'allocazione della memoria, effettuata in maniera distinta per ciascun nuovo elemento, risulterebbe lenta e approssimativa: il problema viene risolto se si usa il [[memory pool|''memory pool'']].
Esistono diverse varianti delle liste concatenate che tentano di risolvere alcuni dei problemi appena citati.
Riga 92:
Un lista concatenata ''unrolled'' (unrolled linked list) immagazzina più elementi in ciascun nodo della lista, aumentando la performance di caching e diminuendo l'overhead di memoria dovuto alla memorizzazione dei riferimenti. La codifica CDR fa entrambe le cose, rimpiazzando i riferimenti con i dati referenziati.
Le [[Unrolled linked list|''Unrolled linked lis''t]] memorizzano i vari elementi in ogni nodo, incrementando la performance della cache e decrementando l'[[overhead|''overhead'']] della memoria per le referenze. [[CDR coding]] fa entrambe le cose, rimpiazzando le reference con i dati, che estende oltre la fine del record di referenze.
Un buon esempio che sottolinea i pro e i contro dell'utilizzare le liste concatenate rispetto agli array si trova sviluppando un programma che risolva il [[Problema di Giosefo]]. Il problema di Giosefo è un metodo di elezione che funziona avendo un gruppo di persone messe a cerchio. Cominciando da una particolare persona, bisogna contare attorno al cerchio ''n'' volte. Una volta raggiunta la ennesima persona, la si esclude dal cerchio, quindi si conta ancora attorno al cerchio le stesse ''n'' volte ripetendo il processo, fino a quando non rimanga che una persona: la vincitrice. Quest'esempio mostra bene forze e debolezze delle liste concatenate rispetto agli array. Vedendo le persone come nodi in una lista concatenata circolare, risulta chiaro quanto facilmente si possa eliminarne una (basterebbe cambiare il collegamento del nodo precedente). D'altra parte la lista sarebbe poco efficiente nel trovare la prossima persona da eliminare: ogni eliminazione comporta lo scorrimento della lista ''n'' volte. Un array al contrario sarebbe inefficiente nel cancellare gli elementi, ad ogni cancellazione ci sarebbe da spostare ogni elemento successivo a quello eliminato, ma viceversa molto efficiente nel trovare l'ennesima persona nel cerchio, indirizzando direttamente l'elemento corrispondente per il suo indice.
Riga 404:
* Specialmente per le piccole liste, gli array indicizzati possono occupare molto meno spazio di una lista a puntatori in molte architetture.
* La [[località della referenza]] può essere migliorata legando i nodi in memoria e periodicamente riordinandoli, tuttavia questo è possibile anche con uno store generale.
* [[Allocazione dinamica della memoria|allocatori dinamici della memoria]] naif possono produrre un eccessivo ammontare di ''overhead''
* Andare a prendere un elemento da un array pre-allocato è più veloce che utilizzare l'allocazione dinamica della memoria per ogni nodo, dal momento che l'allocazione dinamica della memoria tipicamente richiede una ricerca di blocchi di memoria liberi delle dimensioni desiderate.
Riga 487:
== Immagazzinamento dei dati all'interno o all'esterno della lista ==
Costruendo una lista concatenata, ci si trova di fronte alla scelta se immagazzinare i dati direttamente nei nodi della lista, metodo chiamato ''internal storage'', o immagazzinare solamente la reference al dato, chiamato ''external storage''. L'''Internal storage'' ha il vantaggio di rendere l'accesso ai dati più efficiente, poiché richiede meno spazio totale, a causa della migliore [[località della referenza]], e semplificando la gestione della memoria della lista ( i suoi dati sono allocati e liberati nello stesso tempo dei nodi della lista).
L'''external storage'', d'altro canto, ha il vantaggio di essere più generico, poiché le stesse strutture ed il codice macchina possono essere riutilizzate per un'altra lista concatenata, dal momento che non occorre preoccuparsi della dimensione dei dato. Risulta anche facile immettere gli stessi dati in più liste concatenate. Nonostante sia possibile porre gli stessi dati, tramite una memoria interna, in molteplici liste includendo references ''next'' multiple in ogni nodo, sarebbe necessario creare routine separate per aggiungere o cancellare celle basate su ogni campo. È possibile creare liste concatenate addizionali composte di elementi che utilizzino la memoria interna per custodire le reference al nodo della lista concatenata che contiene i dati.
In generale, se un insieme di strutture dati necessita di essere incluso in molteplici liste concatenate, l'<nowiki/>''external storage'' è la soluzione migliore. Se un insieme di strutture dati necessita di essere incluso solo in una lista, l'<nowiki/>''internal storage'' è leggermente meglio, a meno che sia disponibile un package generico di liste concatenate che implementi l'<nowiki/>''external storage''. Allo stesso modo, se diversi insiemi di dati che possono essere immagazzinati nella stessa struttura dati possono essere inclusi in una singola lista concatenata, allora va bene l'''internal storage''.
Un altro approccio può essere utilizzato con alcuni linguaggi che hanno diverse strutture dati, ma tutti con lo stesso campo iniziale, includendo le referenze al ''next'' (e ''prev'' se abbiamo una lista doppiamente concatenate) nella stessa locazione. Dopo aver definito strutture dati separate per ogni tipo di dato, viene definita una struttura generica che contiene il minimo ammontare di dati condivisi da tutte le altre strutture e contenute al top ( inizio ) delle strutture. Allora possono essere create le routine generiche che utilizzano la struttura minimale che implementa le operazioni della lista, ma routine separate per dati specifici. Questo approccio è usato spesso per routine per il parsing dei messaggi, quando vengono ricevuti vari tipi di messaggio, ma tutte iniziano con lo stesso insieme di campi, normalmente includendo un campo per il tipo di messaggio. Le routine generiche sono utilizzate per aggiungere nuovi messaggi ad una coda quando vengono ricevuti e rimuoverli dalla coda per maneggiarli. Il tipo di messaggio è utilizzato per chiamare la corretta routine in grado di maneggiare quello specifico tipo di messaggio
Riga 568:
== Altre strutture collegate ==
Sia
La [[skip list|''skip list'']] è una lista concatenata a cui sono stati aggiunti livelli di puntatori per raggiungere velocemente un gran numero di elementi e quindi discendere al livello successivo. Il processo continua fino all'ultimo livello che la lista vera e propria.
Un [[albero binario]] può essere descritto come un tipo di lista concatenata dove gli elementi sono essi stessi liste concatenate dello stesso tipo. Il risultato è che ogni nodo può includere un riferimento al primo nodo di una o due altre liste concatenate, che, insieme al loro contenuto, forma il sottoramo del nodo.
Una [[unrolled linked list|''unrolled linked list'']] è una lista concatenata in cui ogni nodo contiene un vettori di dati. Ciò conduce ad un miglioramento del funzionamento della cache, dal momento che un maggior numero di elementi si trova in un'area contigua della memoria e riduce l'utilizzo di memoria, dal momento che devono essere inclusi meno metadata in ogni elemento della lista.
Un'[[hash table]] può utilizzare liste concatenate per memorizzare le catene di oggetti che hanno il medesimo hash.
| |||