Lista concatenata: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: fix citazione web (v. discussione) |
m WPCleaner v1.40 - Disambigua corretti 2 collegamenti - Puntatore, Raleigh |
||
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 (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)|Java]] tipicamente si basano su puntatori modificabili per creare le liste concatenate.
Riga 13:
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.
| |||