Lista concatenata

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.

Una lista semplicemente concatenata che contiene tre valori interi

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 concatenata

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.

Lista circolarmente semplicemente concatenata

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 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.

La 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, 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 cosiddetto problema di Giosefo, il quale è 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.

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 dati persistente.

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.

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.

Operazioni sulle liste concatenate

Nel manipolare le liste concatenate sul posto, bisogna assicurarsi di non usare valori eventualmente resi non validi a seguito di operazioni precedenti. Questo rende gli algoritmi per inserire o cancellare i nodi di una lista concatenata in qualche modo sottili. Questa sezione contiene lo pseudocodice per aggiungere o rimuovere sul posto nodi da una lista semplicemente, doppiamente o circolarmente concatenata. Useremo null per riferirci ad un indicatore di fine lista o ad una sentinella, che potrebbe esser implementata in svariati modi.

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

 record Node {
    data // I dati da memorizzare nel nodo
    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
 }

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 ≠ null {
     <operazioni da fare con node.data>
     node := node.next
 }

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
     newNode.next := node.next
     node.next    := newNode
 }

L'inserimento all'inizio della lista richiede una funzione separata poiché bisogna aggiornare il primo nodo firstNode.

 function insertBeginning(List list, Node newNode) { // inserisce node prima del firstNode corrente
     newNode.next   := list.firstNode
     list.firstNode := newNode
 }

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
     obsoleteNode := node.next
     node.next := node.next.next
     destroy obsoleteNode
 }

 function removeBeginning(List list) { // rimuove il primo nodo 
     obsoleteNode := list.firstNode
     list.firstNode := list.firstNode.next          // punta al nodo successivo di quello cancellato
     destroy obsoleteNode
 }

Si noti che removeBeginning() pone list.firstNode a null rimuovendo l'ultimo nodo della lista.

Dal momento non è possibile ritornare indietro, non sono possibili operazioni efficiente come "insertBefore" (inserisci prima) o "removeBefore" (rimuovi prima).

L'aggiunta di una lista concatenata ad un'altra è allo stesso modo inefficiente, poiché bisogna attraversare l'intera lista per trovare la coda e, quindi, aggiungere la seconda lista a quest'ultima. Quindi se due liste linearmente concatenate sono di lunghezza $n$ , l'aggiunta di una lista ha una complessità asintotica di $O(n)$ . Nel Lisp e linguaggi derivati l'aggiunta di una lista è data dalla procedura append.

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 {
    data // I dati da immagazzinare nel nodo
    next // Un puntatore al nodo successivo; null per l'ultimo nodo
    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
     Node lastNode    // punta all'ultimo nodo della lista; null per liste vuote
 }

L'iterazione attraverso una lista doppiamente concatenata può esser fatta in entrambe le direzioni.

Iterazione in avanti

 node := list.firstNode
 while node ≠ null
     <operazioni da fare con node.data>
     node := node.next

Iterazione all'indietro

 node := list.lastNode
 while node ≠ null
     <operazioni da fare con node.data>
     node := node.prev

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)
     newNode.prev := node
     newNode.next := node.next
     if node.next = null
         list.lastNode := newNode
     else
         node.next.prev := newNode
     node.next := newNode

 function insertBefore(List list, Node node, Node newNode)
     newNode.prev := node.prev
     newNode.next := node
     if node.prev is null
         list.firstNode := newNode
     else
         node.prev.next := newNode
     node.prev    := newNode

Abbiamo anche bisogno di una funzione che inserisca un nodo all'inizio di una lista possibilmente vuota:

 function insertBeginning(List list, Node newNode)
     if list.firstNode = null
         list.firstNode := newNode
         list.lastNode  := newNode
         newNode.prev := null
         newNode.next := null
     else
         insertBefore(list, list.firstNode, newNode)

Una funzione simmetrica inserisce il nodo alla fine della lista:

 function insertEnd(List list, Node newNode)
     if list.lastNode = null
         insertBeginning(list, newNode)
     else
         insertAfter(list, list.lastNode, newNode)

Rimuovere un nodo è più facile, richiede soltanto attenzione col primo e ultimo nodo della lista:

 function remove(List list, Node node)
   if node.prev = null
       list.firstNode := node.next
   else
       node.prev.next := node.next

   if node.next = null
       list.lastNode := node.prev
   else
       node.next.prev := node.prev
   destroy node

Una sottile conseguenza di questa procedura è che il cancellare l'ultimo elemento di una lista pone sia firstNode e lastNode a null, e così permette di rimuovere l'ultimo nodo di una lista di un elemento correttamente. Si nota che non si ha bisogno di metodi separati "rimuoviPrima" o "rimuoviDopo", poiché in una lista doppiamente concatenata possiamo utilizzare "remove(node.prev)" o "remove(node.next)".

Liste circolarmente concatenate

Le liste circolarmente concatenate possono essere sia singolarmente che doppiamente concatenate. In una lista circolarmente concatenata tutti i nodi vengono collegati in un cerchio continuo, senza l'uso del valore null. Per le liste con un inizio e una fine (come una coda), si memorizza un riferimento all'ultimo nodo della lista. Il nodo next ( successivo ) dopo l'ultimo è il primo nodo. Gli elementi possono essere aggiunti alla fine della lista e rimossi all'inizio in tempo costante.

Ogni tipo di lista circolarmente concatenata beneficia del fatto che si può attraversare l'intera lista in un tempo costante partendo da un nodo qualsiasi. Questo spesso permette di evitare di memorizzare il firstNode (primo nodo) e lastNode (ultimo nodo), benché se la lista debba essere svuotata si abbia bisogno di una speciale rappresentazione per la lista vuota, tale per cui una variabile lastNode punti ad un nodo della lista o a null se la lista è vuota; utilizziamo quindi in questo caso lastNode. Questa rappresentazione semplifica significativamente l'aggiunta e la rimozione di nodi con una lista non vuota, ma le liste vuote sono un caso particolare.

Le liste circolarmente concatenate sono la struttura dati preferita da Anders Hejlsberg, il creatore di LINQ.

Liste doppiamente circolarmente concatenate

Assumendo che someNode sia un generico nodo in una lista non vuota, questo codice itera attraverso questa lista a partire da someNode:

Iterazione in avanti

 node := someNode
 do
     <operazioni da fare con node.value>
     node := node.next
 while node ≠ someNode

Iterazione all'indietro

 node := someNode
 do
     <operazioni da fare con node.value>
     node := node.prev
 while node ≠ someNode

Si noti che il test viene fatto alla fine del ciclo. È importante nel caso in cui la lista contenga solo il nodo singolo someNode.

Questa semplice funzione inserisce un nodo in una lista doppiamente circolarmente concatenata dopo un dato elemento:

 function insertAfter(Node node, Node newNode)
     newNode.next := node.next
     newNode.prev := node
     node.next.prev := newNode
     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)
     if list.lastNode = null
         node.prev := node
         node.next := node
     else
         insertAfter(list.lastNode, node)
     list.lastNode := node

Per inserire all'inizio usiamo una semplice "insertAfter(list.lastNode, node)". Per finire, per rimuovere un nodo dobbiamo affrontare il caso dove la lista sia vuota:

 function remove(List list, Node node)
     if node.next = node
         list.lastNode := null
     else
         node.next.prev := node.prev
         node.prev.next := node.next
         if node = list.lastNode
             list.lastNode := node.prev;
     destroy node

Come nelle liste doppiamente concatenate, "removeAfter" e "removeBefore" possono essere implementati con "remove(list, node.prev)" e "remove(list, node.next)".

Applicazioni delle liste concatenate utilizzando vettori di nodi

I linguaggi che non supportano alcun tipo di reference posso creare collegamenti rimpiazzando i puntatori con gli indici degli array. L'approccio consiste nell'usare un array di record, dove ogni record ha un campo intero che indica l'indice del nodo successivo (e possibilmente del precedente) nell'array. Non tutti i nodi nell'array devono esser usati. Se neppure i record sono supportati, possono esser usati gli array paralleli.

Come esempio, consideriamo la seguente lista concatenata che utilizza array anziché puntatori:

 record Entry {
    integer next; // indice della prossima entry nell'array
    integer prev; // entry precedente (se la lista è doppiamente concatenata)
    string name;
    real balance;
 }

Creando un array di queste strutture e una variabile intera che memorizza l'indice del primo elemento può essere costruita una lista concatenata:

integer listHead;
Entry Records[1000];

I collegamenti tra elementi vengono creati inizializzando i campi Next o Prev con l'indice della cella successiva (o precedente) per ogni dato elemento. Per esempio

Indice	Prossimo	Precedente	Nome	Bilancio
0	1	4	Jones, John	123.45
1	-1	0	Smith, Joseph	234.56
2 (listHead)	4	-1	Adams, Adam	0.00
3			Ignore, Ignatius	999.99
4	0	2	Another, Anita	876.54
5
6
7

Nell'esempio sopra riportato, ListHead 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 ListFree, 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:

i := listHead;
while i >= 0 { '// scorri la lista
     print i, Records[i].name, Records[i].balance // print entry
     i = Records[i].next;
}

Di fronte ad una scelta, i vantaggi di questo approccio includono:

Le liste concatenate sono rilocabili, significa che possono essere spostate in memoria a piacere e possono essere direttamente e velocemente serializzate per essere immagazzinate su disco o trasferite via rete.
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.
allocatori dinamici della memoria naif possono produrre un eccessivo ammontare di overhead nella memoria per ogni nodo allocato; quasi nessun overhead è prodotto con questo approccio.
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.

Questo tipo di approccio ha molti svantaggi: crea e maneggia uno spazio privato di memoria per i suoi nodi. Questo conduce ai seguenti problemi:

Incrementa la complessità dell'implementazione.
Ingrandire un grande array quando è pieno può essere difficile o impossibile, mentre trovare spazio per un nuovo nodo in memoria è più facile.
Aggiungere elementi ad un array dinamico alle volte (quando è pieno) può avere tempi lineari (O(n)) invece che costanti (nonostante sia una costante ammortizzata).
Usando un memory pool generale permette di lasciare più memoria per gli altri dati se la lista è più piccola del previsto o se molti nodo sono liberati.

Per queste ragioni, questo approccio è usato principalmente per quei linguaggi che non supportano l'allocazione dinamica della memoria. Questi svantaggi sono mitigati dal fatto che la lunghezza massima della lista è conosciuta nel momento in cui viene creato l'array.

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 è 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 = (node*)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;
}

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'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.

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

Esempi di immagazzinamento esterno e interno

Supponiamo di voler creare una lista concatenata di famiglie e dei loro membri. Usando l'immagazzinamento interno, la struttura potrebbe apparire come la seguente:

 record member { // membro di una famiglia
     member next
     string firstName
     integer age
 }
 record family { // la famiglia stessa
     family next
     string lastName
     string address
     member members // testa della lista dei membri della famiglia
 }

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
 while aFamily ≠ null { // itera attraverso la lista della famiglia
     stampa le informazioni riguardanti la famiglia
     aMember := aFamily.members // restituisce la lista dei membri della famiglia
     while aMember ≠ null { // itera attraversa la lista dei membri
         stampa le informazioni riguardanti il membro della famiglia
         aMember := aMember.next
     }
     aFamily := aFamily.next
 }

Usando l'immagazzinamento esterno, potremmo creare le seguenti strutture:

 record node { // struttura per un nodo generico
     node next
     pointer data // puntatore generico per i dati del nodo
 }
 record member { // struttura per i membri della famiglia
     string firstName
     integer age
 }
 record family { // struttura per la famiglia
     string lastName
     string address
     node members // testa della lista dei membri di questa famiglia
 }

Per stampare una lista completa delle famiglie e dei loro membri usando l'immagazzinamento esterno, potremmo scrivere:

 famNode := Families // inizia alla testa della lista della famiglia
 while famNode ≠ null { // itera attraverso la lista delle famiglie
     aFamily = (family)famNode.data // estrae la famiglia dal nodo
     stampa le informazioni riguardanti la famiglia
     memNode := aFamily.members // restituisce la lista dei membri della famiglia
     while memNode ≠ null { // itera attraversa la lista dei membri
         aMember := (member)memNode.data // estrae il membro della famiglia dal nodo
         stampa le informazioni riguardanti il membro della famiglia
         memNode := memNode.next
     }
     famNode := famNode.next
 }

Si nota che quando si usa l'immagazzinamento esterno. è necessario un passo in più per estrarre il record dal nodo e fare il cast verso il tipo di dato opportuno. Questo avviene perché sia la lista delle famiglie che la lista dei membri della famiglia sono memorizzate in due liste concatenate che usano la stessa struttura dati (node).

Fino a quando un membro può appartenere soltanto a una famiglia, l'immagazzinamento interno funziona bene. Se, invece, la collezione di dati si riferisce a generazioni multiple, così che una persona può apparire come figlio in una famiglia, ma genitore in un'altra, si rende necessario l'immagazzinamento esterno.

Velocizzare le ricerche

L'individuazione dell'elemento specifico in una lista concatenata anche se è ordinata, richiede normalmente un tempo O(n) (ricerca ordinata). Questo è uno degli svantaggi fondamentali delle liste concatenate rispetto alle altre strutture dati. In aggiunta alle varianti discusse nella sezione precedente, ci sono vari semplici modi per migliorare il tempo di ricerca.

In una lista non ordinata, una semplice euristica per diminuire il tempo di ricerca medio è la move-to-front heuristic, che semplicemente sposta un elemento all'inizio della lista una volta che questo è stato trovato. Questo schema, pratico per la creazione di semplici caches, assicura che l'elemento usato più di recente sia anche il più veloce da ritrovare.

Un altro approccio comune è quello di indicizzare una lista collegata usando una struttura dati esterna più efficiente. Per esempio, si può costruire un red-black tree o una hash table i cui elementi sono riferimenti ai nodi della lista collegata.

Possono essere aggiunti ad una lista molti di questi indici. Lo svantaggio è che questi indici necessitano di essere aggiornati ogni volta che si aggiunge o rimuove un nodo ( o ogni volta che l'indice viene utilizzato di nuovo)

Altre strutture collegate

Sia le pile che le 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.

Un'hash table può utilizzare liste concatenate per memorizzare le catene di oggetti che hanno il medesimo hash.

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 e Clifford Stein. Introduzione agli algoritmi, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. 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 Archiviato il 25 settembre 2009 in Internet Archive..

Voci correlate

Lista di strutture dati

Altri progetti

Wikimedia Commons contiene immagini o altri file sulle liste concatenate

Collegamenti esterni

(EN) Opere riguardanti linked list, su Open Library, Internet Archive.
(EN) Denis Howe, linked list, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
Del materiale sulle liste concatenate è disponibile alla Stanford University dipartimento di informatica:
- (EN) Introduzione alle liste concatenate, su cslibrary.stanford.edu.
- (EN) Problemi sulle liste concatenate, su cslibrary.stanford.edu.
(EN) Citazioni da CiteSeer, su citeseer.ist.psu.edu.
(EN) Apprendere le liste, su acmacs.com. URL consultato il 17 luglio 2006 (archiviato dall'url originale il 28 giugno 2006).
(EN) Implementazioni delle shared singly linked list, su cs.chalmers.se.
(EN) Introduzione alle liste concatenate con diagrammi e esempi di codice in Java, su mycsresource.net. URL consultato il 17 luglio 2006 (archiviato dall'url originale il 27 settembre 2007).

Controllo di autorità	GND (DE) 4783888-7

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

V · D · M Strutture dati
Tipi	Collezione · Container
Astratte	Array associativo (Multimap) · Lista · Pila · Coda (Deque) · Coda di priorità · Set (Multiset · Mfset)
Array	Bit array · Buffer circolare · Array dinamico · Hash table · Array sparso
Collegate	Lista di associazioni · Lista concatenata · Skip list · Unrolled linked list · Lista concatenata tramite XOR
Alberi	B-albero · Albero binario di ricerca (Albero AA · Albero AVL · RB-Albero · Albero binario di ricerca bilanciato · Albero splay) · Heap (Heap binario · Heap binomiale · Heap di Fibonacci) · Albero di Merkle · Albero SPQR · Albero PQ · Albero indicizzato binario
Grafi	Diagramma binario di decisione · Digrafo aciclico · Automa a stati finiti deterministico aciclico
Alberi di partizionamento dei dati spaziali	Albero quadramentale · M-tree · R-tree (R* tree · R+ tree) · X-tree
Lista di strutture dati