Lista concatenata: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m migrazione automatica di 1 collegamenti interwiki a Wikidata, d:Q7003418 |
m Bot: overlinking giorni e mesi dell'anno e modifiche minori |
||
Riga 13:
[[Lisp]], che significa ''list processor'', fu creato da [[John McCarthy]] nel [[1958]] mentre lavorava al MIT e nel [[1960]] che pubblicò le basi del linguaggio in un articolo sulla rivista [[Communications of the ACM]], intitolato "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Una delle principali strutture dati del LISP è la lista concatenata.
Nei primi [[Anni 1960|anni sessanta]], l'utilizzo di liste concatenate e di linguaggi che le supportavano come modalità di rappresentazione dei dati era ormai comune. Bert Green del [[Lincoln Laboratory]] del MIT pubblicò un articolo intitolato "Computer languages for symbol manipulation" su ''IRE Transactions on Human Factors in Electronics'' nel
Vari sistemi operativi sviluppati da Technical Systems Consultants (in origine di West Lafayette Indiana, poi di [[Raleigh]], [[North Carolina]]) utilizzavano liste concatenate come strutture dei file.
Una directory entry puntava al primo settore di un file, e le porzioni successivi venivano localizzate tramite una lista di puntatori. Sistemi che utilizzavano questa tecnica includevano
Il sistema operativo TSS, sviluppato da [[IBM]] per le macchine [[System 360]]/370, utilizzava una lista doppiamente concatenata per maneggiare il suo file system. La struttura delle directory era simile a Unix, in cui una directory poteva contenere file e/o altre directory e si estendeva per una profondità a piacere. Un programma ''flea'' ([[pulce]]) fu creato per correggere problemi di file system dopo un crash, dal momento che porzioni modificate del file si trovavano in memoria al momento del problema. Questi errori venivano corretti comparando i collegamenti all'elemento precedente e successivo. Se un collegamento era corrotto, e se veniva trovato il collegamento giusto, la lista veniva corretta ( era una lista doppiamente concatenata con due copie del puntatore). Un commento comico del codice sorgente affermava "Everyone knows a flea caller gets rid of bugs in cats".
Riga 27:
Il modo più semplice di creare una lista concatenata è una '''lista semplicemente concatenata''' (o l'abbreviazione inglese '''slist'''), che utilizza un collegamento per nodo. Questo collegamento punta al nodo successivo della lista o a un [[valore nullo]] o ad una lista vuota se è il valore finale.
<center>[[
==== Liste doppiamente concatenate ====
Riga 33:
Un tipo più sofisticato di lista concatenata è una '''lista doppiamente concatenata''' o '''lista concatenata a due vie'''. Ogni nodo possiede due collegamenti: uno punta al nodo precedente o ad un [[valore nullo]] o ad una lista vuota se è il primo nodo; l'altro punta al nodo successivo o ad un [[valore nullo]] o una lista vuota se è il nodo finale.
<center>[[
In alcuni linguaggi di bassissimo livello le [[Liste concatenate tramite XOR]] offrono un modo di implementare una lista doppiamente concatenata utilizzando una singola parola per entrambi i collegamenti, nonostante l'utilizzo di questa tecnica sia normalmente scoraggiato.
Riga 39:
=== Liste circolarmente concatenate ===
In una '''lista circolarmente concatenata''', il nodo iniziale e finale sono collegati. Questo può essere implementato sia per liste semplicemente o doppiamente concatenate. Per attraversare una lista circolarmente concatenata, si può iniziare in qualsiasi nodo e si segue la lista in entrambe le direzioni fino a ritornare al nodo di origine. Viste in un altro modo, le liste circolarmente concatenate non hanno né inizio né fine. Questo tipo di liste è utile per maneggiare buffer di dati e nei casi in cui si ha un oggetto nella lista e si desidera scorrere tutti gli altri oggetti della lista.
Il puntatore che punta all'intera lista è normalmente chiamato il puntatore finale.
Riga 65:
In generale, se si utilizza una struttura dati dinamica, dove vi sono elementi che vengono aggiunti e cancellati frequentemente e la localizzazione dei nuovi elementi aggiunti è importante, il beneficio di una lista concatenata aumenta.
=== Liste
{|style="float: right" class="wikitable"
Riga 81:
|}
Le liste concatenate hanno vari vantaggi nei confronti degli [[array]].
È 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]].
Riga 89:
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]].
Esistono diverse varianti delle liste concatenate che tentano di risolvere alcuni dei problemi appena citati.
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.
Riga 110:
== Operazioni sulle liste concatenate ==
Nel manipolare le liste concatenate sul posto, bisogna assicurarsi di non usare valori eventualmente resi non validi a seguito di
=== Liste linearmente concatenate ===
==== Liste semplicemente concatenate ====
La nostra struttura dati avrà due campi. Manteniamo inoltre una variabile ''firstNode'' che punta sempre al primo nodo nella lista, o è ''null'' per una lista vuota
Riga 120:
next ''// Un riferimento al nodo successivo; null per l'ultimo nodo''
}
'''record''' ''List'' {
''Node'' firstNode ''// punta al primo nodo della lista; null per una lista vuota''
Riga 126:
L'attraversamento di una lista semplicemente concatenata è semplice; comincia al primo nodo e segue ogni link successivo fino a che non si arriva alla fine:
node := list.firstNode
'''while''' node not null {
Riga 135:
Il codice seguente inserisce un nodo dopo un nodo esistente in una lista semplicemente concatenata. Il diagramma mostra come avviene l'inserimento. Non è possibile inserire un nuovo nodo prima di un altro preesistente; è, invece, necessario posizionarlo tenendo conto di quello precedente.
[[
'''function''' insertAfter(''Node'' node, ''Node'' newNode) { ''// inserisce newNode dopo node''
Riga 151:
In modo similare, si hanno delle funzioni per rimuovere il nodo ''dopo'' ( after ) un dato nodo e per rimuovere un nodo all'inizio della lista. Il diagramma dimostra il primo modo. Per trovare e rimuovere un particolare nodo, si deve tener traccia dell'elemento precedente.
[[
'''function''' removeAfter(''Node'' node) { ''// rimuove il nodo dopo questo''
Riga 172:
==== Liste doppiamente concatenate ====
Con le liste doppiamente concatenate ci sono ancor più puntatori da aggiornare, ma sono anche necessarie meno informazioni, dato che possiamo usare i puntatori ''all'indietro'' per osservare gli elementi precedenti nella lista. Questo permette nuove operazioni ed elimina le funzioni per i casi particolari. Aggiungeremo ai nostri nodi un campo ''prev'' che punta all'elemento precedente e alla struttura della lista un campo ''lastNode'', che punta sempre all'ultimo nodo nella lista. Entrambi i campi ''list.firstNode'' e ''list.lastNode'' sono ''null'' per una lista vuota.
'''record''' ''Node'' {
Riga 179:
prev ''// Un puntatore al node precedente; null per il primo nodo''
}
'''record''' ''List'' {
''Node'' firstNode ''// punta al primo nodo della lista; null per liste vuote''
Riga 201:
Le due funzioni che seguono sono perfettamente simmetriche e aggiungono un nodo prima o dopo un dato noto, come mostrato dal seguente diagramma:
[[
'''function''' insertAfter(''List'' list, ''Node'' node, ''Node'' newNode)
Riga 247:
'''else'''
node.prev.next := node.next
'''if''' node.next = '''null'''
list.lastNode := node.prev
Riga 292:
node.next := newNode
Per avere un "insertBefore", poniamo semplicemente "insertAfter(node.prev, newNode)". Inserire un elemento in una lista che può essere vuota richiede una funzione speciale:
'''function''' insertEnd(''List'' list, ''Node'' node)
Riga 393:
|}
Nell'esempio sopra riportato, <code>ListHead</code> dovrebbe essere posto a 2, l'indice del primo nodo della lista. Si noti che l'indice 3 e quelli da 5 a 7 non sono parte della lista. Queste celle sono disponibili per aggiunte alla lista. Creando una variabile intera <code>ListFree</code>, una [[lista libera]] dovrebbe essere creata per mantenere traccia di quali celle sono disponibili. Se tutti gli indici sono in uso, la dimensione dell'array dovrebbero essere incrementate o dovrebbero essere eliminati alcuni elementi per far posto ai nuovi che verrebbero inseriti nella lista.
Il seguente codice dovrebbe scorrere la lista e mostrare i nomi e i bilanci:
Riga 420:
== Implementazione nei linguaggi ==
Molti [[linguaggio di programmazione|linguaggi di programmazione]] come il [[Lisp]] e [[Scheme]] utilizzano liste semplicemente concatenate come strutture dati base del linguaggio. In molti altri [[linguaggio funzionale|linguaggi funzionali]], queste liste sono costruite tramite nodi, ciascuno chiamato un ''[[cons]]'' o una ''cella cons''. Il cons ha due campi: il ''[[Car e cdr|car]]'', una reference ai dati di quel nodo, e il ''[[Car e cdr|cdr]]'', una reference al nodo successivo.
Nonostante le celle cons possano essere utilizzate per costruire ulteriori strutture dati, questo è il loro scopo primario.
Riga 492:
== 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
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
In generale, se un insieme di strutture dati necessita di essere incluso in molteplici liste concatenate, l'external storage è la soluzione migliore. Se un insieme di strutture dati necessita di essere incluso solo in una lista, l'internal storage è leggermente meglio, a meno che sia disponibile un package generico di liste concatenate che implementi l'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.
Riga 515:
}
Per stampare una lista completa delle famiglie e dei loro membri usando l'immagazzinamento interno, potremmo scrivere:
aFamily := Families ''// inizia alla testa della lista della famiglia''
Riga 577:
Sia gli [[stack]] che le [[Coda (informatica)|code]] sono spesso implementati utilizzando liste concatenate, e spesso il loro uso viene ristretto al tipo di operazioni che supportano.
La [[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]] è 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.
Riga 609:
== Collegamenti esterni ==
*Del materiale sulle liste concatenate è disponibile alla [[Stanford University]] dipartimento di informatica:
**{{en}} [http://cslibrary.stanford.edu/103/ Introduzione alle liste concatenate]
**{{en}} [http://cslibrary.stanford.edu/105/ Problemi sulle liste concatenate]
| |||