Lista concatenata: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Etichette: Sostituito Rimozione di avvisi di servizio Modifica visuale
Zio27 (discussione | contributi)
Annullata la modifica 112247216 di 79.52.159.159 (discussione)
Etichetta: Annulla
Riga 1:
{{NN|informatica|agosto 2018}}
*
{{organizzare|Voce pesante, soprattutto nella seconda parte. Si può valutare se scorporare alcune sezioni (come le operazioni).|informatica|agosto 2018}}
In [[informatica]], una '''lista concatenata''' (o '''''linked list''''') è una [[struttura dati]] dinamica, tra quelle fondamentali usate nella [[Programmazione (informatica)|programmazione]]. Consiste di una sequenza di nodi, ognuno contenente [[Campo (informatica)|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 (programmazione)|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 [[linguaggio di programmazione|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. [[programmazione procedurale|Linguaggi procedurali]] come il [[C (linguaggio)|C]], il [[C++]] ed il [[Java (linguaggio di programmazione)|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 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]] (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]] che 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 sessanta]], 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 (Carolina del Nord)|Raleigh]], [[Carolina del Nord]]) 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 utilizzavano 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.
 
<div align="center">[[File:Singly-linked-list.svg]]<br /><small>''Una lista semplicemente concatenata che contiene tre valori interi''</small></div>
 
==== 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.
 
<div align="center">[[File:doublylinkedlist.png]]<br /><small>''Un esempio di una lista doppiamente concatenata.''</small></div>
 
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.
 
<div class="center">[[File:Circularly-linked-list.svg]]<br /><small>''Lista circolarmente semplicemente concatenata''</small></div>
 
==== 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 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 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 le [[Pila (informatica)|pile]], 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 utilizzate 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 risultano, persino su piccoli insiemi di dati, meno efficienti di strutture dati basate su [[albero binario di ricerca bilanciato|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 ===
 
{|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 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 [[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.
 
Le [[Unrolled linked list|''Unrolled linked lis''t]] memorizzano i vari elementi in ogni nodo, incrementando la performance della cache e decrementando l'''[[overhead]]'' della memoria per le referenze. [[CDR coding]] fa entrambe le cose, rimpiazzando le reference con i dati, 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 [[Problema di Giosefo]]. Il problema di Giosefo è 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 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 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 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.
 
[[File: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.
 
[[File: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 nodo''
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 &ne; '''null'''
<fai qualcosa con node.data>
node := node.next
 
''Iterazione all'indietro''
node := list.lastNode
'''while''' node &ne; '''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:
 
[[File: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 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'''
fai qualcosa con node.value
node := node.next
'''while''' node &ne; someNode
 
''Iterazione all'indietro''
node := someNode
'''do'''
fai qualcosa con node.value
node := node.prev
'''while''' node &ne; 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 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
 
{| class="wikitable"
|-
! 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, <code>ListHead</code> 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 <code>ListFree</code>, 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 [[serializzazione|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.
* [[Allocazione dinamica della memoria|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 il 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 ([[Notazione O-grande|O]](n)) invece che costanti (nonostante sia una costante [[analisi ammortizzata|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 [[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 (tipo di dato)|record]]. Di seguito vi è un esempio completo in [[C (linguaggio)|C]]:
 
<source lang=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;
}
</source>
 
== 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'<nowiki/>''external storage'' è la soluzione migliore. Se un insieme di strutture dati necessita di essere incluso solo in una lista, l'<nowiki/>''internal storage'' è leggermente meglio, a meno che sia disponibile un package generico di liste concatenate che implementi l'<nowiki/>''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 &ne; '''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 &ne; '''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 &ne; '''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 &ne; '''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 [[cache]]s, 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 [[Pila (informatica)|pile]] 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.&nbsp;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.&nbsp;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.&nbsp;205–213, 501–505
* Green, Bert F. Jr. (1961). Computer Languages for Symbol Manipulation. ''IRE Transactions on Human Factors in Electronics.'' '''2''' pp.&nbsp;3–8.
*[[John McCarthy|McCarthy, John]] (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. ''[[Communications of the ACM]]''. <small>[https://web.archive.org/web/20131004215327/http://www-formal.stanford.edu/jmc/recursive.html] [https://web.archive.org/web/20040202215021/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]]. ''Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sections 2.2.3–2.2.5, pp.&nbsp;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 0-262-03293-7. Section 10.2: Linked lists, pp.&nbsp;204–209.
* [[Allen Newell|Newell, Allen]] and Shaw, F. C. (1957). Programming the Logic Theory Machine. ''Proceedings of the Western Joint Computer Conference.'' pp.&nbsp;230–240.
*Parlante, Nick (2001). Linked list basics. ''Stanford University''. <small>[http://cslibrary.stanford.edu/103/LinkedListBasics.pdf PDF]</small>
* [[Robert Sedgewick|Sedgewick, Robert]] ''Algorithms in C'' (1998). Addison Wesley. ISBN 0-201-31452-5, pp.&nbsp;90–109
* Shaffer, Clifford A. ''A Practical Introduction to Data Structures and Algorithm Analysis'' (1998). NJ: Prentice Hall. ISBN 0-13-660911-2, pp.&nbsp;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].
 
==Voci correlate==
*[[Lista di strutture dati]]
 
== Altri progetti ==
{{interprogetto}}
 
== Collegamenti esterni ==
*Del materiale sulle liste concatenate è disponibile alla [[Stanford University]] dipartimento di informatica:
**{{cita web|http://cslibrary.stanford.edu/103/|Introduzione alle liste concatenate|lingua=en}}
**{{cita web|http://cslibrary.stanford.edu/105/|Problemi sulle liste concatenate|lingua=en}}
*{{cita web|url=http://citeseer.ist.psu.edu/cis?q=linked+and+list+and+data+and+structure|titolo=Citazioni da CiteSeer|lingua=en}}
*{{cita web|1=http://acmacs.com/aclelland/lists/|2=Apprendere le liste|lingua=en|accesso=17 luglio 2006|urlarchivio=https://web.archive.org/web/20060628112932/http://acmacs.com/aclelland/lists/|dataarchivio=28 giugno 2006|urlmorto=sì}}
*{{cita web|http://www.cs.chalmers.se/~noble/manual/sllist.html|Implementazioni delle shared singly linked list|lingua=en}}
*{{cita web|1=http://www.mycsresource.net/articles/programming/data_structures/linkedlists|2=Introduzione alle liste concatenate con diagrammi e esempi di codice in Java|lingua=en|accesso=17 luglio 2006|urlarchivio=https://web.archive.org/web/20070927102548/http://www.mycsresource.net/articles/programming/data_structures/linkedlists|dataarchivio=27 settembre 2007|urlmorto=sì}}
 
{{strutture dati}}
{{Controllo di autorità}}
{{Portale|informatica}}
 
[[Categoria:Strutture dati]]