Lista concatenata
Da Wikipedia, l'enciclopedia libera.
 |
Questa voce riguardante un argomento di informatica non è ancora stata tradotta completamente dalla lingua inglese. Terminala o riscrivila tu.
Nota: il testo da tradurre potrebbe essere nascosto: vai in modifica per visualizzarlo. |
 |
In informatica, una lista concatenata (o linked list) è una delle strutture dati fondamentali usate nella programmazione. Essa consiste di una sequenza di nodi, ognuno contenente campi di dati arbitrari ed uno o due riferimenti ("link") che puntano al nodo successivo e/o precedente. Una lista concatenata è un tipo di dato auto-referente, in quanto contiene un puntatore ad un altro dato dello stesso tipo. Le liste concatenate permettono l'inserzione e la rimozione di nodi in ogni punto della lista in tempo costante, ma non permettono l'accesso casuale. Esistono diversi tipi di liste concatenate: liste concatenate semplici, liste concatenate doppie e liste circolari.
Le liste concatenate possono essere implementate in molti linguaggi di programmazione. Linguaggi come il Lisp e lo Scheme hanno già al loro interno questa struttura dati, oltre che varie operazioni per accedere al suo contenuto. Linguaggi procedurali come il C, il C++ ed il Java tipicamente si basano su puntatori modificabili per creare le liste concatenate.
[modifica] Storia
Le liste concatenate furono sviluppate nel 1955-56 da Allen Newell, Cliff Shaw e Herbert Simon nella RAND Corporation come struttura dati fondamentale per il loro Information Processing Language. L'IPL fu utilizzato dagli autori per sviluppare i primi programmi di intelligenza artificiale, che includevano la Logic Theory Machine, il General Problem Solver, e programma per gli scacchi. Pubblicazioni sul loro lavoro apparvero su IRE Transactions on Information Theory nel 1956, e nelle conclusioni di alcune conferenze del 1957-1959, tra cui Proceedings of the Western Joint Computer Conference nel 1957 e 1958, e Information Processing (Pubblicazioni dell prima Conferenza Internazionale dell'UNESCO sull'Information Processing) del 1959. Il diagramma, ora classico, di blocchi che rappresentano i nodi della lista con frecce che puntano ai nodi successivi della lista apparve in "Programming the Logic Theory Machine" di Newell e Shaw su Proc. WJCC, nel Febbraio 1957. Newell e Simon furono premiati con l'ACM Premio Turing nel 1975 per aver "reso contribuiti basilari all'intelligenza artificiale, alla comprensione della psicologia umane e allo sviluppo delle liste".
Il problema della traduzione automatica per l'elaborazione del linguaggio naturale condusse Victor Yngve del Massachusetts Institute of Technology (MIT) ad utilizzare liste concatenate come strutture dati nel suo linguaggio di programmazione COMIT, creato per la ricerca computerizzata nel campo della linguistica. Un articolo su questo linguaggio intitolato "A programming language for mechanical translation" apparve su Mechanical Translation nel 1958.
Lisp, che significa list processor, fu creato da John McCarthy nel 1958 mentre lavorava al MIT e nel 1960 he 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 60, 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 Marzo 1961 nel quale riassumeva i vantaggi di un approccio a liste concatenate. Un articolo posteriore, "A Comparison of list-processing computer languages" di Bobrow e Raphael, apparve su Communications of the ACM nell'Aprile 1964.
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 utilizzavono questa tecnica includevano Flex (per la CPU Motorola 6800), il mini-Flex (stessa CPU), e Flex9 (per la CPU Motorola 6809). Una variante sviluppata da TSC e messa in commercio da Smoke Signal Broadcasting in California, utilizzava lo stesso concetto con una lista doppiamente concatenata.
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".
[modifica] Varianti
[modifica] Liste linearmente concatenate
[modifica] Liste semplicemente concatenate
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.
Una lista semplicemente concatenata che contiene tre valori interi
[modifica] Liste doppiamente concatenate
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.
Un esempio di una lista doppiamente concantenata.
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.
[modifica] 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.
[modifica] Liste circolari semplicemente concatenate
In una lista circolare semplicemente concatenata, ogni nodo ha un collegamento, simile alla normale lista semplicemente concatenata, eccetto per il fatto che il collegamento successivo dell'ultimo nodo punta al primo. Allo stesso modo di una lista semplicemente concatenata, i nuovi nodi possono essere efficacemente inseriti solo dopo che un nodo sia stato referenziato. Per questa ragione, è utile mantenere un riferimento solo all'ultimo elemento di una lista circolare semplicemente concatenata, dal momento che permette un veloce inserimento all'inizio e anche un accesso al primo nodo tramite il puntatore al nodo successivo dell'ultimo.
[modifica] Liste circolari doppiamente concatenate
In una lista circolare doppiamente concatenata, ogni nodo ha due collegamenti, simili alla lista doppiamente concatenata, eccetto per il fatto che il collegamento predecente del primo nodo punta all'ultimo nodo e il collegamento successivo dell'ultimo nodo punta al primo. Allo stesso modo di una lista doppiamente concatenata, l'inserimento e la cancellazione possono essere realizzati in ogni punto.
[modifica] Nodi sentinella
Le liste concatenate alle volte possiedono uno speciale nodo falso o nodo sentinella all'inizio e/o alla fine della lista che non è utilizzato per memorizzare dati. Il suo scopo è quello di semplificare o velocizzare alcune operazioni, assicurando che ogni nodo contenente i dati possieda sempre un nodo precedente e/o successivo e che ogni lista (anche quelle che non contengono dati) possiedano sempre un "primo" ed un "ultimo" nodo. Il Lisp ha un tale design - il valore speciale nil è utilizzato per marcare la fine di una lista semplicemente concatenata 'propria' o una catena di cons cells quando vengono chiamate. Una lista non deve finire in nil, ma una tale lista viene definita 'impropria'.
[modifica] Applicazioni delle liste concatenate
Le liste concatenate sono utilizzate come un mattone per la costruzione di molte altre strutture dati, come gli stack, le code e altre varianti. Il campo "dati" di un nodo può essere un'altra lista concatenata. Grazie a questo trucco, si possono costruire altre strutture dati con le liste; questa pratica ha origine nel Lisp, dove le liste concatenate sono una struttura dati primaria ( nonostante non siano l'unica), ed è ora una funzionalità comunemente utilizzata nei linguaggi di programmazione funzionali.
Alle volte le liste concatenate sono utizzate per implementare vettori associativi, e vengono chiamate in questo contesto liste associative. C'è poco da dire su queste liste; non sono molto efficienti e possono essere superate agevolemente da strutture come l'albero per ricerca binaria bilanciata persino su piccoli insiemi di dati (vedere la discussione in inglese). 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.
[modifica] Vantaggi e svantaggi nei riguardi di altre strutture dati
Come succede spesso nella programmazione e nella progettazione, nessun metodo si adatta bene ad ogni circostanza. Una lista concatenata può funzionare bere in alcuni casi, ma può causare problemi in altri. Esiste una lista dei comuni vantaggi e svantaggi delle liste concatenate. 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 concatenate aumenta.
[modifica] Liste concatenate e vettori
| Vettore | Lista concatenata | |
|---|---|---|
| Indirizzamento | O(1) | O(n) |
| Inserimento | O(n) | O(1) |
| Cancellazione | O(n) | O(1) |
| Persistenza | No | Si singolarmente |
| Località | Ottima | Pessima |
Le liste concatenate hanno vari vantaggi nei confronti degli array. Gli elementi possono essere inseriti nelle liste indefinitivamente, mentre un vettore verrà presto riempito e necessiterà di essere ridimensionato, un'operazione costosa che non potrebbe essere possibile se la memoria è frammentata. In modo simile, un vettore nel quale molti elementi vengano rimossi necessita di essere rimpicciolito.
E' 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 sequenzialeagli 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. 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 caratteri e valori 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.
[modifica] Doppiamente e semplicemente concatenate
Le liste doppiamente concatenate richiedono un maggiore spazio per nodo ( a meno che non si utilizzino lo xor-linking), e le loro operazione elementari sono più costose; ma vi sono spesso metodi più facili per manipolarle poichè consentono l'accesso sequenziale alla lista in entrambe le direzioni. In particolar modo, si può inserire o cancellare un nodo con un numero costante di operazioni dato solo l'indirizzo del nodo. Alcuni algoritmi richiedono l'accesso in entrambe le direzioni. D'altro canto, non consente il tail-sharing e non può essere utilizzata come struttura data persistente.
[modifica] Liste circolarmente concatenate e liste linearmente concatenate
Le liste circolarmente concatenate sono le più utili per descrivere le naturali strutture circolari e hanno il vantaggio di essere una struttura regolare e permettere di attraversare la lista partendo da ogni punto. Consentono inoltre un accesso veloce al primo ed all'ultimo nodo attraverso un unico puntatore (l'indirizzo dell'ultimo elemento). Il loro principale svantaggio è la complessità dell'iterazione, che alcuni casi particolari difficili da gestire.
[modifica] Nodi sentinella
I nodi sentinella possono semplificare le operazioni in certe liste. assicurando che il nodo precedente e/o prossimo esistano per ogni elemento. Tuttavia i nodi sentinella utilizzano spazio aggiunto (specialmente in applicazioni che utilizzano molte liste corte), e possono complicare altre operazioni. Per evitare l'utilizzo di spazio aggiuntivo i nodi sentinella possono spesso essere utilizzati come referenze al primo o all'ultimo nodo della lista.
[modifica] Operazioni sulle liste concatenate
[modifica] Liste linearmente concatenate
[modifica] Liste semplicemente concatenate
[modifica] Liste doppiamente concatenate
[modifica] Liste circolarmente concatenate
[modifica] Liste doppiamente circolarmente concatenate
[modifica] Applicazioni delle liste concatenate utilizzando vettori di nodi
[modifica] Implementazione nei linguaggi
Molti linguaggi di programmazione come il Lisp e Scheme utilizzano liste semplicemente concatenate come strutture dati base del linguaggio. In molti altri linguaggi funzionali, queste liste sono costruite tramite nodi, ciascuno chiamato un cons o una cella cons. Il cons ha due campi: il car, una reference ai dati di quel nodo, e il [cdr, una reference al nodo successivo. Nonostante le celle cons possano essere utilizzate per costruire ulteriori strutture dati, questo è il loro scopo primario.
In altri linguaggi le liste concatenate sono tipicamente costruite tramite reference e record. Di seguito vi e un esempio completo in C:
#include <stdio.h> /* per printf */
#include <stdlib.h> /* per malloc */
typedef struct ns {
int data;
struct ns *next;
} node;
node *list_add(node **p, int i) {
node *n = malloc(sizeof(node));
n->next = *p;
*p = n;
n->data = i;
return n;
}
void list_remove(node **p) { /* rimuove head */
if (*p != NULL) {
node *n = *p;
*p = (*p)->next;
free(n);
}
}
node **list_search(node **n, int i) {
while (*n != NULL) {
if ((*n)->data == i) {
return n;
}
n = &(*n)->next;
}
return NULL;
}
void list_print(node *n) {
if (n == NULL) {
printf("la lista è vuota\n");
}
while (n != NULL) {
printf("print %p %p %d\n", n, n->next, n->data);
n = n->next;
}
}
int main(void) {
node *n = NULL;
list_add(&n, 0); /* lista: 0 */
list_add(&n, 1); /* lista: 1 0 */
list_add(&n, 2); /* lista: 2 1 0 */
list_add(&n, 3); /* lista: 3 2 1 0 */
list_add(&n, 4); /* lista: 4 3 2 1 0 */
list_print(n);
list_remove(&n); /* rimuove il primo elemento (4) */
list_remove(&n->next); /* rimuove il nuovo secondo (2) */
list_remove(list_search(&n, 1)); /* rimuove la cella che contiene 1 (primo) */
list_remove(&n->next); /* rimuove il successivo (0) */
list_remove(&n); /* rimuove l'ultimo (3) */
list_print(n);
return 0;
}
[modifica] Immagazzinamento dei dati all'interno o all'esterno della lista
[modifica] Esempi di immagazzinamento esterno e interno
[modifica] Velocizzare le ricerche
[modifica] Altre strutture collegate
[modifica] Bibliografia
- National Institute of Standards and Technology (August 16, 2004). Definizione di una lista concatenata. Retrieved December 14, 2004.
- Antonakos, James L. and Mansfield, Kenneth C., Jr. Practical Data Structures Using C/C++ (1999). Prentice-Hall. ISBN 0-13-280843-9, pp. 165–190
- Collins, William J. Data Structures and the Java Collections Framework (2002,2005) New York, NY: McGraw Hill. ISBN 0-07-282379-8, pp. 239–303
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introductions to Algorithms (2003). MIT Press. ISBN 0-262-03293-7, pp. 205–213, 501–505
- Green, Bert F. Jr. (1961). Computer Languages for Symbol Manipulation. IRE Transactions on Human Factors in Electronics. 2 pp. 3-8.
- McCarthy, John (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM. [1] HTML DVI PDF PostScript
- Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sections 2.2.3–2.2.5, pp.254–298.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 10.2: Linked lists, pp.204–209.
- Newell, Allen and Shaw, F. C. (1957). Programming the Logic Theory Machine. Proceedings of the Western Joint Computer Conference. pp. 230-240.
- Parlante, Nick (2001). Linked list basics. Stanford University. PDF
- Sedgewick, Robert Algorithms in C (1998). Addison Wesley. ISBN 0-201-31452-5, pp. 90–109
- Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis (1998). NJ: Prentice Hall. ISBN 0-13-660911-2, pp. 77–102
- Wilkes, Maurice Vincent (1964). An Experiment with a Self-compiling Compiler for a Simple List-Processing Language. Annual Review in Automatic Programming 4, 1. Published by Pergamon Press.
- Wilkes, Maurice Vincent (1964). Lists and Why They are Useful. Proceeds of the ACM National Conference, Philadelphia 1964 (ACM Publication P-64 page F1-1); Also Computer Journal 7, 278 (1965).
- Kulesh Shanmugasundaram (April 4, 2005). Spiegazione delle liste concatenate del Kernel Linux.
[modifica] Collegamenti esterni
- (EN) Descrizione dal Dictionary of Algorithms and Data Structures
- Del materiale sulle liste concatenate è disponibile alla Stanford University dipartimento di informatica:
- (EN) Citazioni da CiteSeer
- (EN) Apprendere le liste
- (EN) Generic List Container Type per ANSI C di Jeff Hay
- (EN) Implementazioni delle shared singly linked list
- (EN) Introduzione alle liste concatenate con diagrammi e esempi di codice in Java
 Informatica |
|||||||
|---|---|---|---|---|---|---|---|
| Progetto Informatica | Portale Informatica | BarCode | |||||
|
Categorie principali
|
|||||||
