In genere le liste sono costituite da una struttura in cui è inserito un puntatore dello stesso tipo della struttura che si collegherá ad un altro elemento della lista e cosí via. Per inserire un nuovo elemento nella lista si possono usare due criteri differenti: se si vuole ottenere una lista ordinata il nuovo elemento deve essere inserito nella posizione corretta; l'altro criterio è di inserire un nuovo elemento in un posto generico della lista, solitamente all'inizio o alla fine.
Logicamente il primo criterio è molto più difficile da rispettare perché impone che prima di effettuare l'inserimento debba essere fatta una ricerca all'interno della lista in modo tale da stabilire la posizione in cui deve essere inserito il nuovo elemento. Ovviamente questo criterio ha i suoi lati positivi, infatti se volessimo stampare la lista ordinatamente basterebbe soltanto implementare la funzione che scorrendo la lista ne va stampando gli elementi. Se invece la lista non fosse stata precedentemente ordinata, prima della stampa gli elementi in ordine, avremmo dovuto ordinarli. Naturalmente se non ci interessa l'ordine della lista, ma soltanto la momorizzazione di dati, potremo decidere di inserire gli elementi in modo disordinato.
Operazioni sulle liste:
inserimento di un nuovo elemento
cancellazione
scorrimento
Anche se nominalmente le operazioni possibili sulle liste sono simili a quelle sulle code e sulle pile, praticamente si differiscono per dei particolari molto importanti. Infatti le liste consentono l'estrazione non distruttiva di ogni singolo elemento, mentre le pile e le code no.
In oltre, quando si lavora con le liste allocate dinamicamente dovremo inevitabilmente lavorare con dei puntatori semplici o doppi, e questo richiederà maggiore attenzione da parte del programmatore. Infatti una cattiva gestione dei puntatori potrebbe portare ad un comportamento anomalo del programma stesso; tipico esempio: il programmma funzione correttamente quasi sempre, ma quando si caricano troppi dati o una lista diviene molto grande si hanno risultati imprevedibili (scomparsa di dati o sovrascrittura di quelli esistenti.
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #define VAL 4
5
6 /* elemento della lista */
7 struct elemento{
8 int x;
9 struct elemento *next;
10 };
11
12
13 void ins_lista(int n, struct elemento **lista);
14 void stampa_lista(struct elemento *lista);
15 void svuota(struct elemento **lista);
16
17
18
19
20 int main(){
21 struct elemento *lista=NULL; //puntatore nullo ad una lista
22 int i,p;
23
24 for(i=0;i<VAL;i++){
25 printf("inserisci un numero: ");
26 scanf("%d",&p);
27
28 /* funzione di inserimento (si possono
29 scegliere 3 tipi di inserimento) */
30 ins_lista(p,&lista);
31 }
32 stampa_lista(lista);
33 svuota(&lista);
34 stampa_lista(lista);
35 }
36
37
38 void stampa_lista(struct elemento *lista){
39 struct elemento *tmp;
40 int i=0;
41
42 tmp=lista;
43 while(tmp){ /* equivale a scrivere while(tmp!=NULL) */
44 printf("elemento: %d\n",tmp->x);
45 tmp=tmp->next;
46 i++;
47 }
48 printf("in questa lista ci sono %d elementi\n",i);
49 }
50
51
52 /* funzione che cancella tutti gli elementi della lista */
53 void svuota(struct elemento **lista){
54 struct elemento *tmp;
55
56 if(*lista==NULL)
57 return;
58 else{
59 tmp=*lista;
60 *lista=(*lista)->next;
61 free(tmp);
62 svuota(&(*lista));
63 /* funzione ricorsiva che richiama se stessa ma con
64 l'indirizzo del puntatore successivo */
65 }
66 }
La funzione non inserita nel codice precedente sarà studiata adesso in modo da far vedere come avviene l'inserimento ordinato, quello in testa e quello in coda.
Quando si vuole inserire un nuovo elemento in una lista, se si vuole mantenere uno specifico ordine si dovranno fissare delle regole. Ad esempio, si vuole realizzare una lista con ordine crescente; ciò vuol dire che ogni elemento della lista dovrà essere preceduto da un elemento più piccolo e dovrà essere seguito da un elemento più grande. Quindi la funzione prima di inserire un nuovo elemento nella lista deve cercare la posizione corretta di inserimento.
void ins_lista(int n, struct elemento **lista){
struct elemento *punt, *punt_prec, *punt_cor;
punt_cor=*lista;
/* se punt_cor e' nullo o n e' minore o uguale di punt_cor->next */
if(punt_cor==NULL || //se la lista e' vuota o
n <= punt_cor->x)
/*il nuovo elemento e' minore o uguale
a punt_cor->x lo inserisce in testa alla lista */
{
punt=(struct elemento *)malloc(sizeof(struct elemento));
punt->x=n;
punt->next=punt_cor;
*lista=punt;
}
else{
while(punt_cor!=NULL && n > punt_cor->x){
/* fino a quando non raggiunge la fine della lista o fino a quando
n e' monore di pun_cor->x scorre la lista; queste 2 condizioni
devono essere verificate entrambe per scorrere la lista */
punt_prec=punt_cor;
punt_cor=punt_cor->next;
}
punt=(struct elemento *)malloc(sizeof(struct elemento));
punt->x=n;
/* inserisce il nuovo elemento tra punt_prec e punt_cor */
punt->next=punt_cor;
punt_prec->next=punt;
}
}
Se invece vogliamo che ogni elemento sia inserito all'inizio della lista basta fare in modo che la lista punti al nuovo elemento e il resto della lista venga attaccata al nuovo elemento inserito.
void ins_lista(int n, struct elemento **lista){
struct elemento *new;
/* alloca lo spazio per un nuovo elemento */
new=(struct elemento *)malloc(sizeof(struct elemento));
new->x=n;
new->next=(*lista);//il puntatore del nuovo elemento punta a *lista
*lista=new; //il nuovo elemento e' inserito in testa alla lista
}
Se vogliamo che il nuovo elemento venga inserito alla fine della lista, cioè vogliamo che sia l'ultimo della lista, basta ricordarci che il puntatore dell'ultimo elemento della lista sarà un puntatore nullo, quindi per trovare l'ultimo elemento della lista basta andare alla ricerca di questo puntatore nullo e ridirigerlo verso il nuovo elemento della lista che così sarà attaccato ad essa.
void ins_lista(int n, struct elemento **lista){
struct elemento *new;
if(*lista==NULL){
//controllo per verificare se la lista e' vuota
new=(struct elemento *)malloc(sizeof(struct elemento));
new->x=n;
new->next=NULL;
*lista=new;
}
else
ins_lista(n, &(*lista)->next);
/* viene richiamata la funzione ricorsivamente fino a quando non
si raggiunge la fine della lista */
}