Liste collegate

Una lista è una sequenza ordinata di elementi dello stesso tipo. Per esempio, (1 23 -1 2 -1) è una sequenza di numeri interi, mentre ('a' 'r' '1' 'P') è una sequenza di caratteri. La notazione che usiamo per rappresentare le sequenze è quella di mettere gli elementi fra parentesi tonde, separati da spazi.

Il modo più semplice di rappresentare delle liste in C è quello di usare gli array. In queste pagine vediamo una rappresentazione alternativa, che fa uso delle cosidette strutture collegate, in cui i vari elementi che compongono un insieme composto di dati sono rappresentati in zone di memoria che possono anche essere distanti fra loro (al contrario degli array, in cui gli elementi sono consecutivi), e sono legati fra di loro mediante puntatori.

1. la rappresentazione in memoria
2. dal tipo alla rappresentazione
3. scansione di una lista
4. costruire una lista con un ciclo
5. aggiunta di un elemento in testa
6. costruzione con aggiunte successive
7. lettura di una lista da file, in ordine inverso
8. l'operatore freccia ->
9. la notazione grafica
10. trasformare un array in una lista
11. eliminazione del primo elemento di una lista
12. eliminazione dell'ultimo elemento di una lista
13. liste passate per valore
14. aggiungere un elemento in coda a una lista
15. lettura di una lista da file
16. lettura lista da file, lineare
17. eliminazione elementi in mezzo a una lista
18. aggiungere un elemento in mezzo a una lista
19. inserimento delle medie

Il resto del programma, per quello che riguarda le lista, è coperto dal libro di esercizi. La definizione di lista data nel libro è la seguente:

struct NodoLista {
  int val;
  struct NodoLista *next;
};

typedef struct NodoLista TipoNodoLista;
typedef TipoNodoLista *TipoLista;

Questa definizione differisce da quella usata sopra solo per il fatto che si dà un nome di tipo alla struttura NodoLista, ma per il resto è assolutamente identica.