Aggiunta di un elemento in testa a una lista

Vediamo ora in che modo si può aggiungere un elemento in testa a una lista. La aggiunta in testa è la creazione di un nuovo elemento nella lista, in prima posizione. Nell'esempio della lista (2 -9 1), se si aggiunge il numero -5 in testa, la lista deve diventare (-5 2 -9 1), cioè il nuovo elemento deve diventare il primo, e di seguito ci sono i vecchi elementi della lista.

In che modo si può eseguire questa modifica? Partiamo dallo stato della memoria: alla fine della aggiunta dobbiamo arrivare a una situazione in cui c'è una nuova struttura, il cui campo next punta al primo elemento della vecchia lista. Possiamo quindi fare questo paragone fra lo stato della memoria prima della aggiunta, e quello che deve essere dopo la aggiunta.

Cominciamo con la creazione della nuova struttura. A questo scopo, definiamo un puntatore e facciamo la allocazione della struttura puntata:

  TipoLista t;

  t=malloc(sizeof(struct NodoLista));
  (*t).val=-5;

Questo crea la nuova struttura e ci mette il valore dell'intero. La struttura va ora collegata al resto della lista. Nella figura che dice come deve essere fatta la memoria alla fine, la freccia punta alla prima struttura della vecchia lista. Questa è la struttura a cui punta la freccia che parte da l. Dal momento che assegnare un puntatore equivale a spostare la punta della sua freccia nella locazione dove si trova la punta dell'altra, possiamo ottenere questo risultato facendo:

  (*t).next=l;

Resta ora soltanto una cosa da sistemare: la freccia che parte da l deve puntare alla nuova struttura. Dal momento che l'indirizzo di questa struttura si trova in t, possiamo semplicemente fare:

  l=t;

Si riporta qui sotto il programma aggiunta.c che crea una lista nel modo visto in precedenza, ci aggiunge due elementi in testa, e stampa tutta la lista. Si noti che definire una variabile come puntatore a struttura struct NodoLista, oppure come variabile di tipo TipoLista sia la stessa cosa. Infatti, la definizione del tipo TipoLista dice che le variabili di questo tipo sono effettivamente puntatori a strutture di tipo struct NodoLista.

/*
  Aggiunta di un elemento in testa a una lista.
*/

#include<stdlib.h>

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

typedef struct NodoLista *TipoLista;


/*
  stampa di una lista di lunghezza generica
*/

void StampaLista(TipoLista l) {
  TipoLista s;

  s=l;
  while(s!=NULL) {
    printf("%d ", (*s).val);
    s=(*s).next;
  }

  printf("\n");
}


/*
  main
*/

int main() {
  TipoLista l;
  TipoLista s, t;

		/* creazione della lista (2 -9 1) */

  s=NULL;
  
  t=s;
  s=malloc(sizeof(struct NodoLista));
  (*s).val=1;
  (*s).next=t;
  
  t=s;
  s=malloc(sizeof(struct NodoLista));
  (*s).val=-9;
  (*s).next=t;
  
  t=s;
  s=malloc(sizeof(struct NodoLista));
  (*s).val=2;
  (*s).next=t;
  
  l=s;

		/* aggiunge l'elemento -5 in testa alla lista */

  t=malloc(sizeof(struct NodoLista));

  (*t).val=-5;
  (*t).next=l;

  l=t;
  

		/* aggiunge l'elemento 13 in testa alla lista */

  t=malloc(sizeof(struct NodoLista));

  (*t).val=13;
  (*t).next=l;

  l=t;

  
  		/* stampa la lista */

  StampaLista(l);

  return 0;
}

Vediamo ora cosa succede nella memoria quando si esegue la prima aggiunta in testa. Supponiamo che la memoria, prima della aggiunta, abbia il contenuto riportato qui a fianco (questa volta usiamo un esempio in cui le strutture non sono memorizzate in ordine).

Quando si esegue la allocazione, si alloca la zona di memoria per una struttura, e il suo indirizzo va in t. Eseguendo l'istruzione (*t).val=-5, viene messo il valore -5 nel primo campo di questa struttura.

Ora si esegue l'istruzione (*t).next=l. L'effetto è quello di copiare il numero memorizzato in l nella variabile (*t).next. Dopo questa istruzione, nel campo next della struttura puntata da t c'è il numero che stava in l, che è l'indirizzo della prima struttura della vecchia lista.

L'ultima istruzione è la copia del contenuto di t nella variabile l. Dal momento che t contiene l'indirizzo della nuova struttura, questo fa sí che ora l contenga l'indirizzo della nuova struttura, ossia che punti alla nuova struttura.

Il fatto che l ora rappresenta la lista (-5 2 9 -1) può non essere chiaro, a prima vista. Per capire qual'è la lista indicata da un puntatore, basta seguire le freccie: l'elemento puntato da l è la struttura che contiene -5, e quindi questo è il primo elemento della lista. Seguendo il puntatore di questa struttura, si arriva alla struttura il cui primo campo è 2, poi ancora a -9 e a 1. Quindi la lista rappresentata è effettivamente (-5 2 9 -1), ossia la lista di partenza a cui è stato aggiunto un nuovo elemento.