In informatica, una lista concatenata (o linked list) è una struttura dati dinamica, tra quelle fondamentali usate nella programmazione. 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, solo quello sequenziale. 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, come ad esempio il Lisp e lo Scheme, che hanno già al loro interno questa struttura dati, oltre che varie operazioni per accedere al suo contenuto, oppure come il C, il C++ ed il Java, che tipicamente si basano su puntatori modificabili per creare le liste concatenate.
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 un 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 della 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. I due furono premiati con il Premio Turing nel 1975 per aver «reso contributi 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 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.
Un linguaggio di programmazione in cui le liste concatenate rappresentano una delle principali strutture dati è il Lisp, il cui nome significa list processor, che fu creato da John McCarthy nel 1958 mentre lavorava al MIT. L'informatico, nel 1960, 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.
Nei primi anni sessanta, l'utilizzo delle liste concatenate e dei linguaggi che le supportavano come modalità di rappresentazione dei dati era ormai comune. Bert Green del MIT Lincoln Laboratory 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 dell'utilizzo di un approccio a liste concatenate. Successivamente, nell'aprile 1964, un articolo di revisione, intitolato A Comparison of list-processing computer languages di Bobrow e Raphael, apparve su Communications of the ACM.
Concetti di base e nomenclatura Le liste concatenate sono composte da campi (detti elementi o nodi), che contengono: un dato il riferimento all'elemento successivo (solitamente chiamato collegamento successivo o puntatore all'elemento successivo).
La testa di una lista è il suo primo nodo, mentre con il termine coda ci si può riferire sia al resto della lista dopo la testa sia all'ultimo nodo della lista. In Lisp e in alcuni linguaggi derivati, il nodo successivo può essere chiamato cdr dell'elenco, mentre il valore del nodo principale può essere chiamato car.
Liste lineari 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 ad un valore nullo o ad una lista vuota se è il valore finale.
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.
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.
Liste circolari In una lista circolarmente concatenata, il nodo iniziale e quello finale sono collegati, con la conseguenza che esse non hanno né un inizio né una fine. Questo può essere implementato sia per liste semplicemente concatenate che per quelle doppiamente concatenate. 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 puntatore finale.
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 è 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.
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 precedente 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.
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 design simile: 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".
Applicazioni delle liste concatenate Le liste concatenate sono utilizzate come un mattone per la costruzione di molte altre strutture dati, come le pile, 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 utilizzate per implementare array 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 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.
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 bene 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 concatenata aumenta.
Liste concatenate e vettori Vettore Lista concatenata Indirizzamento O(1) O(n) Inserimento O(n) O(1) Cancellazione O(n) O(1) Persistenza No Sì singolarmente Località Ottima Pessima
Le liste concatenate hanno vari vantaggi nei confronti degli array. Gli elementi possono essere inseriti nelle liste indefinitamente, mentre un vettore verrà presto riempito e necessiterà di essere ridimensionato, un'operazione costosa che potrebbe non essere possibile se la memoria è frammentata. In modo simile, un vettore nel quale molti elementi vengano rimossi necessita di essere rimpicciolito.
È 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 dellheapsort. 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.
La lista concatenata unrolled (unrolled linked list) immagazzina più elementi in ciascun nodo della lista, aumentando la performance di caching e diminuendo loverhead di memoria dovuto alla memorizzazione dei riferimenti. La codifica CDR fa entrambe le cose, rimpiazzando i riferimenti con i dati referenziati, che estende oltre la fine del record di referenze.