21: Introduzione alle Liste dinamiche

Siamo arrivati all’ultimo argomento di questa rubrica: oggi parliamo di liste.
Le liste sono delle strutture dati dinamiche; abbiamo visto con gli array che essi possono immagazzinare dati tutti dello stesso tipo (per esempio interi o caratteri) con la limitazione che dobbiamo dichiarare la loro lunghezza a priori, per evitare fenomeni di overflow, cioè di occupazione di memoria non dedicata al nostro programma. Se non sappiamo esattamente il numero di celle di cui il vettore ha bisogno siamo costretti a sovrastimare il loro numero, con il rischio di allocare della memoria che poi non andremo ad utilizzare. Abbiamo visto poi, qualche lezione fa, la malloc e la free, che sono un paio di funzioni incluse nella libreria stdlib del C, che ci permettono di allocare (e liberare) della memoria utilizzabile dalle nostre funzioni in modo dinamico: in particolare queste funzioni ci permettono di allocare esattamente la quantità di memoria che il programma ha bisogno per funzionare. In particolare la malloc prende in input la dimensione dell’area di memoria da allocare e restituisce il puntatore all’area di memoria allocata (qualora l’allocazione vada a buon termine).
Una lista è strutturata come una serie di nodi, uno successivo all’altro; ciascun nodo contiene un dato (o un insieme di dati) e un puntatore al nodo successivo. È possibile aggiungere ed eliminare nodi attraverso le funzioni malloc e free qualora abbiamo la necessità di farlo, il che rende le liste una struttura dati estremamente flessibile.

lista
Il primo nodo è puntato da un puntatore che prende il nome di testa della lista, che serve per accedere alla lista, mentre l’ultimo nodo contiene un puntatore a NULL (vuoto).
Questo è il caso di una lista concatenata semplice (ogni nodo contiene un puntatore al nodo successivo); nel caso di una lista concatenata doppia ogni nodo contiene 2 puntatori: uno al nodo successivo e uno a quello precedente. Se l’ultimo nodo punta al primo (ed eventualmente viceversa) si ha un anello.
La memoria utilizzata dalla lista viene allocata sulla heap, che è una porzione molto grande di memoria del calcolatore, e che a differenza dello stack che si usava per le funzioni, in C va acceduta in modo manuale dal programmatore per allocare e deallocare memoria utile per le funzioni attraverso appunto la malloc e la free.
Vediamo ora come dichiarare una lista: utilizzeremo il costruttore di tipo typedef per creare il tipo di un nodo generico della lista, in questo caso un nodo conterrà un intero e un puntatore al nodo successivo (dello stesso tipo).

#include <stdio.h>
#include <stdlib.h>

struct elemento {         //definizione del tipo di un nodo
   int inf;
   struct elemento *pun;
};

int main()
{
   struct elemento *lista;      //dichiarazione di lista variabile (locale) puntatore al primo nodo della lista
}

Nella prossima guida vedremo come aggiungere un elemento in testa o in coda alla lista e come ricercare un nodo in base a un valore da esso contenuto.
Alla prossima!

Please follow and like us: