Liste

Indice

Definizione

Le liste collegate (dette anche linked list) sono una struttura dati astratta (ADT) molto usata in situazioni/contesti molto diversi Ci possono essere utili infatti ogni volta in cui dobbiamo memorizzare una sequenza di valori la cui lunghezza non ci è nota a priori e che può variare nel tempo.

E' inoltre utile in tutti i casi in cui dobbiamo poter inserire nuovi elementi all’inizio della sequenza, in una posizione intermedia, oppure in fondo.

Sintassi struttura dati base

struct list_element {
    element_type value;
    struct list_element *next;
};

In base al valore che ho necessita' di salvare andro' a creare una struttura dati diversa. Esempio: 

struct list_element {
    int value;
    struct list_element *next;
};

Per scrivere meno o abbreviare il nome del tipo e' possibile usare la parola chiave typedef 

typedef struct list_element {
    int value;
    struct list_element *next;
} item;

Da qui in poi usero' il tipo item per scrivere codice piu' compatto, ma questo non e' in nessun modo obbligatorio.

Inserimento in testa

La lista delle operazioni da fare e':

  1. leggere valore
  2. allocare memoria (e controllare che sia valida)
  3. copiare valore nel campo corretto dell'elemento lista
  4. collegare il nuovo elemento alla testa della lista
  5. aggiornare il puntatore alla lista
item *tmp;
item *head = NULL;
int valore_da_inserire;

scanf("%d", &valore_da_inserire); // 1
tmp = (item *)malloc(sizeof(item)); // 2
if (tmp == NULL) {
    printf("MESSAGGIO DI ERRORE");
    exit(-42);
}
tmp->value = valore_da_inserire; // 3
tmp->next = testa; // 4
testa = tmp; // 5

Stampa di una lista

E' necessario usare un ciclo while 

void stampa_lista(item *testa)
{
    while(testa != NULL) {
        printf("valore: %d\n", testa->value);
        testa = testa->next;
    }
}

Inserimento in coda

  1. creo l'elemento
  2. se la lista e' vuota aggiorno la testa della lista
  3. altrimenti devo cercare l'ultimo elemento della lista
  4. collego l'ultimo elemento al nuovo elemento creato

In tutti i casi restituisco la testa della lista in modo da gestire il caso di inserimento in lista vuota 

struct list_element *inserisci_in_coda(struct list_element *testa, int valore)
{
    struct list_element *tmp;
    struct list_element *lista;

    lista = testa;
    //creo l'elemento da inserire
    tmp = (struct list_element *)malloc(sizeof(struct list_element));
    if (tmp == NULL) {
        printf("FALLITA MALLOC\n");
        exit(-1);
    }
    tmp->value = valore;
    tmp->next = NULL;

    if (testa == NULL) {
        testa = tmp;
    } else {
        //1 cerchiamo ultimo elemento (GESTIAMO CASO LISTA NON VUOTA)
        while(lista->next != NULL) {
            lista = lista->next;
        }
        // se  arrivo qui ho testa punta all'ultimo elemento

        lista->next = tmp; // collego ultimo elemento al nuovo
    }
    return testa;
}

Validate