Simple linked list o liste concatenate semplici (parte II)

Se chiedete a 10 programmatori diversi : "Quali funzioni servono per gestire le liste?", probabilmente otterreste 10 risposte diverse, perché dipende dall'applicazione e dalle strutture dati complesse che si intendono implementare con le liste. Quindi, senza la pretesa di essere esaustivi, analizziamo insieme alcune funzioni di "base" per la creazione, modifica, stampa ed eliminazione di liste. In particolare, in questa piccola serie di post sulle liste collegate semplici, vedremo le seguenti funzioni:


void push(int pl, nodeP *sP, nodeP *eP);
void pop(int *pl,  nodeP *sP, nodeP *eP);
void delnode(int pl, int global, nodeP *sP, nodeP *eP);
void genlist(int N, nodeP* sP, nodeP* eP);
void destroy(nodeP *sp);
void printlistv(nodeP head);
void printlisto(nodeP head);

Per il momento concentriamoci sulle funzioni push e pop

void push(int pl, nodeP *sP, nodeP *eP);

Nella funzione addnode abbiamo visto come aggiungere un nodo alla fine della lista, qui vediamo come si aggiunge un nodo all'inizio della lista. La scelta del nome push per questa funzione è la più naturale per la similitudine che c'è tra questa funzione e l'operazione di push in una pila , o stack in Inglese.

L'algoritmo in uno pseudolinguaggio programmativo è il seguente 

Crea puntatore a nuovo_elemento;
Se ci sono problemi di allocazione di memoria stampa un messaggio di errore ed esci altrimenti vai avanti
(*nuovo_elemento)->payload = dato di interesse
(*nuovo_elemento)->next = *iniziio_lista
Se la lista era vuota allora  *fine_lista   =* nuovo_elemento
*inizio_lista = *nuovo_lelmento.

L'implementazione in C è quindi la seguente:

void push(int pl, nodeP *sP, nodeP *eP){
  nodeP tempP = (nodeP)malloc(sizeof(nodeT)); // T = 0
  if (tempP==NULL)printf("\n*** Error in function push:: Out of memory!\n");
  else {
    tempP->next = *sP;
    tempP->payload = pl; //T = 1
    if (*sP==NULL){
      *eP = tempP;
    }
    *sP = tempP; // T = 2
  }
}

Valgono qui le stesse osservazioni fatte nel caso dei parametri della addnode, ai quali si rimanda.

Nello schema qui sotto, a "frecce e scatole", si può osservare un esempio di esecuzione della funzione addnode al caso di una lista contenente già due nodi. Per semplicità, sono stati descritti gli stati della lista nei tre istanti di tempo da T0 a T2 indicati nel sorgente della funzione.

In ultimo, si noti che, in questo caso, avere a disposizione il puntatore a fine lista non è d'aiuto :).

void pop(int *pl,  nodeP *sP, nodeP *eP);

Analogamente a quanto detto per la funzione push, avremmo potuto chiamare questa funzione getfirst o extractfirst, ma a scelta del nome pop per questa funzione è la più naturale per la similitudine che c'è tra questa funzione e l'operazione di pop in una pila , o stack in Inglese.

L'algoritmo in uno pseudolinguaggio programmativo è il seguente 

Se la lista è vuota stampa un warning e esci, altrimenti continua
puntatore_temporaneo = *inizio_lista
payload_da_restituire = (*inizio_lista)->payload
(*inizio_lista)->next = *inizio_lista
Se la lista inizialmente conteneva un solo nodo allora *fine_lista=NULL
libera la memoria occupata dall'elemento puntato da puntatore_temporaneo,

L'implementazione in C è quindi la seguente:

void pop(int *pl, nodeP *sP, nodeP *eP){
  nodeP tempP;
  *pl=-99999;
  if (*sP!=NULL) {
    tempP = *sP;             // T = 0
    *pl=(*sP)->payload;
    *sP=(*sP)->next;         // T = 1
    if (*sP==NULL) *eP=NULL;
    free(tempP);             // T = 2
  } else printf("\n*** Error in function pop: list is empty!\n");
}

Il valore pop-ato dalla lista viene restituito nel parametro int pl passato by-reference.

Nello schema qui sotto, a "frecce e scatole", si può osservare un esempio di esecuzione della funzione addnode al caso di una lista contenente già due nodi. Per semplicità, sono stati descritti gli stati della lista nei tre istanti di tempo da T0 a T2 indicati nel sorgente della funzione.

In ultimo, si noti che, anche in questo caso, avere a disposizione il puntatore a fine lista non è d'aiuto :).