Lista concatenata: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: aggiungo navbox {{strutture dati}} |
m Bot: fix citazione web (v. discussione) |
||
Riga 1:
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]] 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''.
Line 26 ⟶ 25:
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>[[File:Singly-linked-list.svg]]<br /><small>''Una lista semplicemente concatenata che contiene tre valori interi''</small></center>
==== Liste doppiamente concatenate ====
Line 32 ⟶ 31:
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>[[File:doublylinkedlist.png]]<br /><small>''Un esempio di una lista doppiamente concatenata.''</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.
Line 41 ⟶ 40:
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 ====
Line 589 ⟶ 588:
==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.
* Collins, William J. ''Data Structures and the Java Collections Framework'' (2002,2005) New York, NY: McGraw Hill. ISBN 0-07-282379-8, pp.
* Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford ''Introductions to Algorithms'' (2003). MIT Press. ISBN 0-262-03293-7, pp.
* Green, Bert F. Jr. (1961). Computer Languages for Symbol Manipulation. ''IRE Transactions on Human Factors in Electronics.'' '''2''' pp.
*[[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]]. ''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 0-262-03293-7. 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.
*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.
* Shaffer, Clifford A. ''A Practical Introduction to Data Structures and Algorithm Analysis'' (1998). NJ: Prentice Hall. ISBN 0-13-660911-2, pp.
* [[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).
Line 609 ⟶ 608:
== Collegamenti esterni ==
*Del materiale sulle liste concatenate è disponibile alla [[Stanford University]] dipartimento di informatica:
**{{
**{{
*{{
*{{
*{{
*{{
{{strutture dati}}
| |||