Lista concatenata
Una lista è un insieme di elementi, detti anche nodi, composti ciascuno da una parte contenente le informazioni e da una parte indicante qual è l'elemento che segue. L'elemento successivo viene indicato tramite il puntatore.
Le informazioni aggregate vengono memorizzate in un array, ma si ricorre ad una lista quando il numero di elementi da memorizzare non deve essere limitato dalla dimensione dell'array.
L'accesso ad un elemento di array avviene specificando l'indice dell'elemento, mentre l'accesso ad un elemento di una lista avviene attraversando tutti gli elementi che lo precedono nella lista.
la scansione degli elementi di una lista avviene partendo dal puntatore al primo elemento della lista. Si passa da un elemento a quello successivo leggendo il campo pun dell'elemento puntato da p e, per mantenere una maniera ricorsiva, il puntatore letto viene assegnato ancora alla stessa variabile p:
p ← pun(p)
Ad esempio il primo elemento sia memorizzato all'indirizzo 100, per sapere dove si trova l'elemento successivo si deve leggere il campo pun. Il valore 80 in questo campo indica l'indirizzo del secondo elemento.
Costruzione di una lista.
Un generico elemento della lista, nella sua forma più semplice contiene il campo Info e il campo pun:
Il campo Info contiene tutte le informazioni che descrivono l'elemento (nell'esempio ci si è limitati a un intero), il campo pun contiene l'indirizzo dell'elemento successivo. Esso è dichiarato come il puntatore ad una struttura Nodo.
La procedura di inserimento di un nodo in una lista
Un elemento potrebbe venire inserito in una lista in base ad un ordine, nel qual caso bisogna scandire la lista fino a raggiungere l'elemento che lo deve seguire nell'ordine stabilito, ed inserire l'elemento tra il suo successivo e il suo precedente.
Nell'esempio il nuovo elemento da inserire si trova all'indirizzo 60. Dopo la scansione, ad esempio, si trova che deve essere inserito tra l'elemento all'indirizzo 100 e quello all'indirizzo 80.
Cioè nel campo pun dell'elemento da inserire si scrive 80 (il puntatore contenuto nell'elemento che lo precede) e nel campo pun dell'elemento che lo precede si scrive 60: l'indirizzo dell'elemento da inserire.
Coda bidirezionale
Una lista bidirezionale consente di avanzare nella lista, ma anche di invertire la direzione di scansione.
Ogni nodo di una lista bidirezionale possiede due campi puntatore: un puntatore a sinistra (ps) ed un puntatore a destra (pd).
Per una lista bidirezionale conviene creare un nodo capolista. Inizialmente i campi puntatore del nodo capolista puntano al nodo stesso.
il nodo capolista
Nell'esempio che si propone i nodi vengono inseriti ipotizzando che il campo tempo rappresenti l'orario in cui svolgere una certa attività e il campo ident rappresenti il codice dell'attività.
Per inserire un nodo nella lista;
Si scandisce la lista alla ricerca del nodo che lo precede in ordine cronologico,
Per estrarre un nodo nella lista;
Si preleva il nodo a destra del nodo capolista.
Cioè per l'inserimento si accede ai nodi consideradoli in una lista, mentre per l'estrazione si accede ai nodi come se formassero una coda.
Nella figura seguente si deve inserire il nodo puntato da p tra il nodo puntato da ptmp e il nodo puntato da prec.
L'operazione di inserimento e quella di estrazione sono mostrate nel programma seguente:
Si dichiara un record la cui struttura viene denominata Nodo: Possiede due campi dati e due campi puntatore. La variabile primo è un puntatore ad una tale struttura.
La funzione inscrono riceve il parametro p, che è un puntatore ad una struttura, e non restituisce parametri.
Si scandisce la lista a iniziare dal nodo più a destra e si prosegue fino a quando si trova un nodo con valore del tempo minore di quello da inserire.
Nei campi puntatore del nodo da inserire si scrivono gli indirizzi dei nodi laterali, mentre nei campi puntatore dei nodi laterali si scrive l'indirizzo del nodo da inserire.
La funzione che preleva un nodo dalla lista, acquisisce l'indirizzo del nodo a destra del capolista. Se legge lo stesso valore significa che la lista è vuota.
i campi puntatore laterali del nodo di testa venogono scritti nel campo puntatore dei nodi laterali, in modo da escludere questo nodo dalla concatenazione.
La funzione ritorna il puntatore al nodo estratto.
Nella funzione main si costruisce, dapprima, il nodo capolista, inserendo nel campo tempo un valore di riferimento minimo.
vengono creati 5 nodi, in ognuno dei quali viene assegnato un valore casuale al tempo e un numero crescente alla variabile ident.
Per creare i nodi si usa l'operatore new del C++, anzichè la funzione malloc del C. I nodi poi vengono inseriti in ordine cronologico.
Segue una semplice stampa di verifica del corretto inserimento dei nodi nella lista. Si vede infatti che i nodi vengono mostrati in ordine cronologico, anzichè nell'ordine di generazione.
Infine i nodi vengono estratti dalla lista e lo spazio di memoria occupato viene liberato con l'operatore delete del C++, in luogo della funzione free del C.
La stampa permette di verificare che i nodi vengono prelevati dalla testa, nell'ordine previsto.
