Le Liste a Puntatore

i Vettori

L’uso degli Array monodimensionali, o Vettori, è il metodo più semplice per la memorizzazione di elenchi di elementi omogenei, pur presentando alcuni problemi: 
Vantaggi

  • L’ordinamento logico degli elementi corrisponde all’ordinamento fisico degli indirizzi.
  • Ogni elemento occupa solo la memoria corrispondente alla sua quantità di informazione, senza spazi accessori.
  • È possibile l’accesso diretto ad ogni elemento dell’insieme.
  • Se l’insieme è ordinato, è possibile effettuare una ricerca dicotomica.

Svantaggi

  • Occorre riservare preliminarmente uno spazio pari alla massima estensione prevedibile del vettore, causando uno spreco di memoria.
  • L’inserimento o l’eliminazione di elementi richiede lo slittamento di tutta la parte rimanente dell’array.
  • È possibile rappresentare solo organizzazioni lineari dei dati.

In molti casi, quindi, si rende necessario ricorrere a un metodo che permetta di assegnare alle celle un ordinamento logico arbitrario, differente dal loro ordinamento fisico, migliorando l’efficienza delle operazioni di manutenzione dei dati.

le Liste

Una Lista è una successione di elementi che occupano in memoria posizioni qualsiasi.
Ciascun elemento, o Nodo, è legato all’elemento successivo tramite un puntatore che ne contiene l’indirizzo.  Ogni Nodo della lista sarà formato da due campi:

  • un campo INFO contenente tutte le informazioni legate al nodo;
  • un campo NEXT contenente l’indirizzo del nodo successivo.

La chiave d'accesso alla Lista, puntatore di Testa, è una variabile che contiene l’indirizzo del primo elemento. L’ultimo elemento della lista riporta una marca speciale nel campo NEXT, detta NIHIL o Ø.
A seconda del metodo di allocazione della lista, può essere scelto come valore Ø un qualsiasi indirizzo non valido.
Vantaggi

  • È possibile allocare solo lo spazio di memoria necessario, ad esempio nella Heap.
  • L’inserimento o l’eliminazione di elementi richiede l’aggiornamento di due soli nodi.
  • È possibile rappresentare organizzazioni non lineari dei dati.

Svantaggi

  • L’unico modo di accedere ad un elemento è quello di scorrere tutta la lista.
  • Ogni elemento occupa lo spazio supplementare per il NEXT; lo spreco è tanto più significativo quanto più piccolo è il campo INFO.
  • Anche se l’insieme è ordinato, non è possibile effettuare una ricerca dicotomica ma solo ricerche sequenziali.
  • Ogni operazione di aggiornamento della lista (inserimento o cancellazione) richiede equivalenti operazioni di aggiornamento dell’area libera di memoria.

Ad esempio la gestione del File System su un disco avviene con la suddivisione del disco in blocchi di grandezza fissata (512 byte di informazione per DOS-Windows) con una tabella iniziale che associa ad ogni nome-file un puntatore di testa al primo blocco del file (F.A.T.).

Inserimento in una lista

Per aggiungere un nuovo elemento in una lista è sufficiente modificare solo l’elemento precedente il punto di inserimento (individuato, ad esempio, tramite una ricerca):

  1. Prec        = indirizzo del nodo precedente l’inserimento
  2. New         = indirizzo nuovo nodo
  3. INFO [New]  = informazioni da memorizzare
  4. NEXT [New]  = NEXT[Prec]
  5. NEXT [Prec] = New
Occorre rispettare l’ordine delle operazioni, in particolare i punti 4 e 5. La sequenza è la stessa anche se Prec indica l’ultimo elemento della lista (inserimento in coda):

Se l’inserimento deve avvenire in testa, occorre modificare il puntatore PT :

Per unificare le operazioni, si può utilizzare come puntatore di testa un intero Nodo (il cui campo Info andrà sprecato). In questo modo possiamo implementare la stessa procedura sia per gli inserimenti in testa (Prec indicherà il Nodo di Testa) che per gli inserimenti in un punto qualsiasi della lista.

Estrazione da una lista

Per eliminare un elemento (individuato, ad esempio, tramite una ricerca) da una lista è necessario modificare l’elemento precedente; nelle operazioni di ricerca saranno perciò necessari due puntatori: Succ, che indica l'elemento da eliminare dalla Lista, e Prec, che indica l'elemento precedente di cui modificare il campo NEXT.

  1. Succ        = indirizzo del nodo da eliminare dalla lista
  2. Prec        = indirizzo del nodo precedente
  3. NEXT [Prec] = NEXT[Succ]
  4. Libera la memoria del Nodo [Succ]

La sequenza è la stessa anche se Succ indica l’ultimo elemento della lista; viceversa, se l’estrazione deve avvenire dalla testa, occorre modificare il puntatore PT.

Anche in questo caso, utilizzando come puntatore di testa un intero Nodo, possiamo implementare la stessa procedura sia per le estrazioni dalla testa che per le estrazioni da un punto qualsiasi della lista.

Scansione di una Lista

Per accedere ad un elemento della lista occorre attraversare tutti i nodi precedenti: la scansione si arresta quando il puntatore al nodo successivo è Ø.

  1. Succ = Puntatore di Testa
  2. while (Succ != Ø)
    a. esamina INFO[Succ]
    b. Succ = NEXT[Succ]

Se la scansione, prevede successivamente un inserimento o una estrazione, è necessario utilizzare due puntatori, in modo da disporre sempre dell’indirizzo del nodo Precedente. È conveniente usare come puntatore di testa un intero nodo:

  1. Prec = indirizzo(Puntatore di Testa)
  2. Succ = NEXT [Prec]
  3. while (Succ != Ø)
    a. esamina INFO[Succ]
    b. Prec = Succ
    c. Succ = NEXT[Succ]

Esempio

Gestione di una lista lineare a singolo puntatore.
Il puntatore di testa verrà posizionato in una variabile di tipo NODO, il cui campo Info potrà essere usato per informazioni generali sulla lista. I nodi necessari alla lista verranno allocati dalla memoria Heap.
Il programma è codificato in linguaggio C (per compilatore Dev-C++).