lista concatenata

In informatica, una lista concatenata (o linked list) è una struttura dati dinamica, tra quelle fondamentali usate nella programmazione. Consiste di una sequenza di nodi, ognuno contenente campi di dati arbitrari ed uno o due riferimenti ("link") che puntano al nodo successivo e/o precedente. Una lista concatenata è un tipo di dato auto-referente, in quanto contiene un puntatore ad un altro dato dello stesso tipo. Le liste concatenate permettono l'inserzione e la rimozione di nodi in ogni punto della lista in tempo costante, ma non permettono l'accesso casuale, 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 linguaggi di programmazione, come ad esempio il Lisp e lo Scheme, che hanno già al loro interno questa struttura dati, oltre che varie operazioni per accedere al suo contenuto, oppure come il C, il C++ ed il Java, che tipicamente si basano su puntatori modificabili per creare le liste concatenate.