Wikipedia

Lista concatenata

struttura dati dinamica
Versione del 16 set 2007 alle 19:20 di Wisbot (discussione | contributi) (Bot: sostituisco E' con È)
Questa voce o sezione sull'argomento informatica è stata parzialmente tradotta dalla lingua inglese.
Puoi contribuire terminando la traduzione o usando altre fonti. Non usare programmi di traduzione automatica. Usa {{Tradotto da}} quando hai terminato. Se nella pagina di modifica trovi del testo nascosto, controlla che sia aggiornato servendoti dei collegamenti «in altre lingue» in fondo alla colonna di sinistra. Segui i suggerimenti del progetto di riferimento.
Data "dicembre 2006" non riconosciuta. Sintassi: {{T|lingua|argomento|mese anno}}

Template:Strutture dati lineari

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.

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

Varianti

Liste linearmente concatenate

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

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.

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.

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.

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.

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

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

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.

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

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.


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.

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. Per evitare l'utilizzo di spazio aggiuntivo i nodi sentinella possono spesso essere utilizzati come referenze al primo o all'ultimo nodo della lista.

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 semplicemnete, 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 successvo; null per l'ultimo nodo
 }
 
 record List {
     Node firstNode   // punta la 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 not null {
     (do something with 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 first node 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  , l'aggiunta di una lista ha una complessità asintotica di  . 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 nodod
    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
     <fai qualcosa con node.data>
     node := node.next

Iterazione all'indietro 

 node := list.lastNode
 while node ≠ null
     <fai qualcosa 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 valorenull. 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 significatamente 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
     fai qualcosa con node.value
     node := node.next
 while node ≠ someNode

Iterazione all'indietro 

 node := someNode
 do
     fai qualcosa 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


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 linkata)
    string name;
    real balance;
 }

Creando un array di queste strutture e una variabile intera che memorizza l'indice del primo elemento può esser 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

IndexNextPrevNameBalance
014Jones, John123.45
1-10Smith, Joseph234.56
2 (listHead)4-1Adams, Adam0.00
3Ignore, Ignatius999.99
402Another, Anita876.54
5
6
7

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;
}


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;
}

Immagazzinamento dei dati all'interno o all'esterno della lista

Esempi di immagazzinamento esterno e interno

Supponiamo di voler creare una lista concatenata di famiglie e dei loro membri. Usando l'immagazzinamente 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 richiede 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 gli stack 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

Collegamenti esterni

  Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica
Estratto da "https://it.wikipedia.org/w/index.php?title=Lista_concatenata&oldid=10971557"