Strutture dati: Le liste

Le liste

Le liste sono strutture dati che rappresentano un insieme finito ed ordinato di n oggetti dello stesso tipo, caratterizzate da due proprietà:

• Ciascun elemento della lista è contraddistinto da una posizione in base alla quale è possibile individuare relazioni di precedenza e di successione tra gli elementi.
• La lista vuota è una lista che non presenta alcun elemento.

Tipi di rappresentazione delle liste

Possiamo avere due tipi di rappresentazione delle liste:

• Liste concatenate: Sono basate su puntatori ed allocazione dinamica della memoria. Si utilizzano se ci sono modifiche (inserimenti, cancellazioni) frequenti, ed ogni elemento della lista è una coppia denominata Node = (Object, Node), ovvero il tipo di dato che contiene ed il puntatore all'elemento successivo.
• Liste tramite array collegati: Si basano su array monodimensionale e sono caratterizzate dalla definizione della capacità massima, e comportano la gestione anche della lista libera, cioè dell’insieme degli elementi dell’array che non vengono utilizzati.

Sulle liste possiamo eseguire varie operazioni tra cui inserimento in testa o in coda, ricerca di un elemento, cancellazione di un elemento, ecc.

Liste concatenate

Ogni oggetto della lista è denominato nodo e contiene un'informazione propria ed un puntatore all'elemento successivo:

In C la lista viene definita come una struttura del seguente tipo (che sarà la prima cosa da scrivere nel codice prima del main):

#include <stdio.h>

struct nodo {
datatype data; // elemento della lista (int,float,char, ecc...)
struct nodo *next; // puntatore all'elemento successivo
};
struct nodo *head=NULL; // la lista è vuota per cui il primo elemento non punta a nulla

Come però ogni cosa, anche le liste hanno vantaggi e svantaggi. I vantaggi sono:

• Non dover spostare elementi per inserimenti e cancellazioni perché basta modificare i riferimenti.
• Non è necessario un limite massimo di dimensioni della lista, e quindi può essere gestita in modo che lo spazio di memoria da essa occupata sia proporzionale al numero dei suoi elementi.

Di contro, però, le operazioni di accesso agli elementi sono costose perché bisogna scandire gli elementi della lista che precedono quello voluto; in pratica, per arrivare ad un elemento bisogna passare per tutti gli altri.

Creazione di una lista

Per prima cosa si crea una nuova lista che ha come elemento l'elemento da inserire:

struct nodo *crea_lista (datatype elem) {
struct nodo* head;
head=(struct nodo*)malloc(sizeof(struct nodo));
// inseriamo i dati
head->data=el