Lista concatenata: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Correzione di uno o più errori comuni |
Nessun oggetto della modifica |
||
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.
Riga 24:
==== 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>
| |||