|
#REDIRECT [[Miyoshi Nagayoshi]]
{{T|lingua=inglese|argomento=informatica|data=dicembre 2006}}
{{Strutture dati lineari}}
In [[informatica]], una '''lista concatenata''' (o '''linked list''') è una delle [[struttura dati|strutture dati]] fondamentali usate nella [[programmazione]]. Essa consiste di una sequenza di nodi, ognuno contenente [[campo|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 (linguaggio)|C]], il [[C++]] ed il [[Java (linguaggio)|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|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 1960|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.
<center>[[Immagine:Singly_linked_list.png]]<br><small>''Una lista semplicemente concatenata che contiene tre valori interi''</small></center>
==== 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.
<center>[[Immagine:doublylinkedlist.png]]<br><small>''Un esempio di una lista doppiamente concantenata.''</small></center>
In alcuni linguaggi di bassissimo livello le [[Liste concatenate tramite XOR]] offrono un modo di implementare una lista doppiamente concatenata utilizzando una singola parola per entrambi i collegamenti, nonostante l'utilizzo di questa tecnica sia normalmente scoraggiato.
=== 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|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|stack]], le [[coda (informatica)|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 [[vettore associativo|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 ===
{|style="float: right" class="wikitable"
! !! Vettore !! Lista concatenata
|-
| Indirizzamento || O(1) || O(''n'')
|-
| Inserimento || O(''n'') || O(1)
|-
| Cancellazione || O(''n'') || O(1)
|-
| [[Persistenza (informatica)|Persistenza]] || No || Si singolarmente
|-
| [[Località (informatica)|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 [[Carattere (informatica)|caratteri]] e valori [[Booleano (informatica)|booleani]]. L'allocazione della memoria, effettuata in maniera distinta per ciascun nuovo elemento, risulterebbe lenta e approssimativa: il problema viene risolto se si usa il [[memory pool]].
Esistono diverse varianti delle liste concatenate che tentano di risolvere alcuni dei problemi appena citati.
Un lista concatenata ''unrolled'' (unrolled linked list) immagazzina più elementi in ciascun nodo della lista, aumentando la performance di caching e diminuendo l'overhead di memoria dovuto alla memorizzazione dei riferimenti. La codifica CDR fa entrambe le cose, rimpiazzando i riferimenti con i dati referenziati.
<!-- [[Unrolled linked list]]s store several elements in each list node, increasing cache performance while decreasing memory overhead for references. [[CDR coding]] does both these as well, by replacing references with the actual data referenced, which extends off the end of the referencing record.
A good example that highlights the pros and cons of using arrays vs. linked lists is by implementing a program that resolves the [[Josephus problem]]. The Josephus problem is an election method that works by having a group of people stand in a circle. Starting at a predetermined person, you count around the circle ''n'' times. Once you reach ''n''th person, take them out of the circle and have the members close the circle. Then count around the circle the same ''n'' times and repeat the process, until only one person is left. That person wins the election. This shows the strengths and weaknesses of a linked list vs. an array, because if you view the people as connected nodes in a circular linked list then it shows how easily the linked list is able to delete nodes (as it only has to rearrange the links to the different nodes). However, the linked list will be poor at finding the next person to remove and will need to recurse through the list till it finds that person. An array, on the other hand, will be poor at deleting nodes (or elements) as it cannot remove one node without individually shifting all the elements up the list by one. However, it is exceptionally easy to find the ''n''th person in the circle by directly referencing them by their position in the array.
-->
=== Doppiamente e semplicemente concatenate ===
Le liste doppiamente concatenate richiedono un maggiore spazio per nodo ( a meno che non si utilizzino lo [[xor linked list|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.
[[Image:Singly linked list insert after.png|center]]
'''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.
[[Image:Singly linked list delete after.png|center]]
'''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 <math>n</math>, l'aggiunta di una lista ha una [[complessità asintotica]] di <math>O(n)</math>. Nel [[Lisp]] e linguaggi derivati l'aggiunta di una lista è data dalla procedura <code>[[append]]</code>.
==== 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 (programmazione)|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:
[[Image:Doubly linked list insert after.png|center]]
'''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 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
<!--
To do an "insertBefore", we can simply "insertAfter(node.prev, newNode)". Inserting an element in a possibly empty list requires a special function:
'''function''' insertEnd(''List'' list, ''Node'' node)
'''if''' list.lastNode = '''null'''
node.prev := node
node.next := node
'''else'''
insertAfter(list.lastNode, node)
list.lastNode := node
To insert at the beginning we simply "insertAfter(list.lastNode, node)". Finally, removing a node must deal with the case where the list empties:
'''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
As in doubly-linked lists, "removeAfter" and "removeBefore" can be implemented with "remove(list, node.prev)" and "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 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
<table border='1' cellspacing='0' cellpadding='3'>
<tr><th>Index</th><th>Next</th><th>Prev</th><th>Name</th><th>Balance</th></tr>
<tr><td>0</td><td>1</td><td>4</td><td>Jones, John</td><td>123.45</td></tr>
<tr><td>1</td><td>-1</td><td>0</td><td>Smith, Joseph</td><td>234.56</td></tr>
<tr><td>2 (listHead)</td><td>4</td><td>-1</td><td>Adams, Adam</td><td>0.00</td></tr>
<tr><td>3</td><td></td><td></td><td>Ignore, Ignatius</td><td>999.99</td></tr>
<tr><td>4</td><td>0</td><td>2</td><td>Another, Anita</td><td>876.54</td></tr>
<tr><td>5</td><td></td><td></td><td></td><td></td></tr>
<tr><td>6</td><td></td><td></td><td></td><td></td></tr>
<tr><td>7</td><td></td><td></td><td></td><td></td></tr>
</table>
<!--
In the above example, <code>ListHead</code> would be set to 2, the ___location of the first entry in the list. Notice that entry 3 and 5 through 7 are not part of the list. These cells are available for any additions to the list. By creating a <code>ListFree</code> integer variable, a [[free list]] could be created to keep track of what cells are available. If all entries are in use, the size of the array would have to be increased or some elements would have to be deleted before new entries could be stored in the list.
-->
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;
}
<!--
When faced with a choice, the advantages of this approach include:
* The linked list is relocatable, meaning it can be moved about in memory at will, and it can also be quickly and directly [[serialization|serialized]] for storage on disk or transfer over a network.
* Especially for a small list, array indexes can occupy significantly less space than a full pointer on many architectures.
* [[Locality of reference]] can be improved by keeping the nodes together in memory and by periodically rearranging them, although this can also be done in a general store.
* Naïve [[dynamic memory allocation|dynamic memory allocators]] can produce an excessive amount of overhead storage for each node allocated; almost no allocation overhead is incurred per node in this approach.
* Seizing an entry from a pre-allocated array is faster than using dynamic memory allocation for each node, since dynamic memory allocation typically requires a search for a free memory block of the desired size.
This approach has one main disadvantage, however: it creates and manages a private memory space for its nodes. Not only does this increase complexity of the implementation, but growing it may be difficult or impossible, because it is large, whereas finding space for a new linked list node in a large, general memory pool is easier. This slow growth also affects algorithmic performance, as it causes a few insert operations to unexpectedly take linear ([[Big-O notation|O]](n)) instead of constant time (although it's still [[amortized analysis|amortized]] constant). Using a general memory pool also leaves more memory for other data if the list is smaller than expected or if many nodes are freed. For these reasons, this approach is mainly used for languages that do not support dynamic memory allocation. These disadvantages are also mitigated if the maximum size of the list is known at the time the array is created.
-->
== Implementazione nei linguaggi ==
Molti [[linguaggio di programmazione|linguaggi di programmazione]] come il [[Lisp]] e [[Scheme]] utilizzano liste semplicemente concatenate come strutture dati base del linguaggio. In molti altri [[linguaggio funzionale|linguaggi funzionali]], queste liste sono costruite tramite nodi, ciascuno chiamato un ''[[cons]]'' o una ''cella cons''. Il cons ha due campi: il ''[[CAR e CDR|car]]'', una reference ai dati di quel nodo, e il ''[[CAR e CDR|[cdr]]'', una reference al nodo successivo.
Nonostante le celle cons possano essere utilizzate per costruire ulteriori strutture dati, questo è il loro scopo primario.
In altri linguaggi le liste concatenate sono tipicamente costruite tramite [[reference]] e [[Record (informatica)|record]]. Di seguito vi e un esempio completo in [[C (linguaggio di programmazione)|C]]:
<pre>
#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;
}
</pre>
== Immagazzinamento dei dati all'interno o all'esterno della lista ==
<!--
When constructing a linked list, one is faced with the choice of whether to store the data of the list directly in the linked list nodes, called ''internal storage'', or to merely store a reference to the data, called ''external storage''. Internal storage has the advantage of making access to the data more efficient, requiring less storage overall, having better [[locality of reference]], and simplifying memory management for the list (its data is allocated and deallocated at the same time as the list nodes).
External storage, on the other hand, has the advantage of being more generic, in that the same data structure and machine code can be used for a linked list no matter what the size of the data is. It also makes it easy to place the same data in multiple linked lists. Although with internal storage the same data can be placed in multiple lists by including multiple ''next'' references in the node data structure, it would then be necessary to create separate routines to add or delete cells based on each field. It is possible to create aditional linked lists of elements that use internal storage by using external storage, and having the cells of the additional linked lists store references to the nodes of the linked list containing the data.
In general, if a set of data structures needs to be included in multiple linked lists, external storage is the best approach. If a set of data structures need to be included in only one linked list, then internal storage is slightly better, unless a generic linked list package using external storage is available. Likewise, if different sets of data that can be stored in the same data structure are to be included in a single linked list, then internal storage would be fine.
Another approach that can be used with some languages involves having different data structures, but all have the initial fields, including the ''next'' (and ''prev'' if double linked list) references in the same ___location. After definining separate structures for each type of data, a generic structure can be defined that contains the minimum amount of data shared by all the other structures and contained at the top (beginning) of the structures. Then generic routines can be created that use the minimal structure to perform linked list type operations, but separate routines can then handle the specific data. This approach is often used in message parsing routines, where several types of messages are received, but all start with the same set of fields, usually including a field for message type. The generic routines are used to add new messages to a queue when they are received, and remove them from the queue in order to process the message. The message type field is then used to call the correct routine to process the specific type of message.
-->
=== 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 [[cache|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 [[Coda (informatica)|code]] sono spesso implementati utilizzando liste concatenate, e spesso il loro uso viene ristretto al tipo di operazioni che supportano.
La [[skip list]] è una lista concatenata a cui sono stati aggiunti livelli di puntatori per raggiungere velocemente un gran numero di elementi e quindi discendere al livello successivo. Il processo continua fino all'ultimo livello che la lista vera e propria.
Un [[albero binario]] può essere descritto come un tipo di lista concatenata dove gli elementi sono essi stessi liste concatenate dello stesso tipo. Il risultato è che ogni nodo può includere un riferimento al primo nodo di una o due altre liste concatenate, che, insieme al loro contenuto, forma il sottoramo del nodo.
Una [[unrolled linked list]] è una lista concatenata in cui ogni nodo contiene un vettori di dati. Ciò conduce ad un miglioramento del funzionamento della cache, dal momento che un maggior numero di elementi si trova in un'area contigua della memoria e riduce l'utilizzo di memoria, dal momento che devono essere inclusi meno metadata in ogni elemento della lista.
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). [http://nist.gov/dads/HTML/linkedList.html 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.
*[[John McCarthy|McCarthy, John]] (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. ''[[Communications of the ACM]]''. <small>[http://www-formal.stanford.edu/jmc/recursive.html] [http://www-formal.stanford.edu/jmc/recursive/recursive.html HTML] [http://www-formal.stanford.edu/jmc/recursive.dvi DVI] [http://www-formal.stanford.edu/jmc/recursive.pdf PDF] [http://www-formal.stanford.edu/jmc/recursive.ps PostScript]</small>
* [[Donald Knuth|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.
* [[Allen Newell|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''. <small>[http://cslibrary.stanford.edu/103/LinkedListBasics.pdf PDF]</small>
* [[Robert Sedgewick (computer scientist)|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
* [[Maurice Vincent Wilkes|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.
* [[Maurice Vincent Wilkes|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). [http://isis.poly.edu/kulesh/stuff/src/klist/ Spiegazione delle liste concatenate del Kernel Linux].
== Collegamenti esterni ==
* {{en}} [http://nist.gov/dads/HTML/linkedList.html Descrizione] dal [[Dictionary of Algorithms and Data Structures]]
*Del materiale sulle liste concatenate è disponibile alla [[Stanford University]] dipartimento di informatica:
**{{en}} [http://cslibrary.stanford.edu/103/ Introduzione alle liste concatenate]
**{{en}} [http://cslibrary.stanford.edu/105/ Problemi sulle liste concatenate]
*{{en}} [http://citeseer.ist.psu.edu/cis?q=linked+and+list+and+data+and+structure Citazioni da CiteSeer]
*{{en}} [http://acmacs.com/aclelland/lists/ Apprendere le liste]
*{{en}} [http://home.earthlink.net/~jrhay/src/wwwsrc/src.html Generic List Container Type per ANSI C] di [[Jeff Hay]]
*{{en}} [http://www.cs.chalmers.se/~noble/manual/sllist.html Implementazioni delle shared singly linked list]
*{{en}} [http://www.mycsresource.net/articles/programming/data_structures/linkedlists Introduzione alle liste concatenate con diagrammi e esempi di codice in Java]
{{Portale|Informatica}}
[[Categoria:Strutture dati]]
[[be:Сьпіс]]
[[da:Liste (datastruktur)]]
[[de:Liste (Datenstruktur)]]
[[en:Linked list]]
[[es:Lista (estructura de datos)]]
[[fr:Liste chaînée]]
[[ko:연결 리스트]]
[[he:רשימה מקושרת]]
[[lt:Tiesinis sąrašas]]
[[hu:Láncolt lista]]
[[is:Tengdur listi]]
[[nl:Gelinkte lijst]]
[[ja:線形リスト]]
[[pl:Lista]]
[[pt:Lista ligada]]
[[ru:Линейный список]]
[[fi:Linkitetty lista]]
[[sv:Länkad lista]]
[[uk:Зв'язаний список]]
[[zh:链表]]
| 