Simple linked list o liste concatenate semplici (parte I)

Una lista concatenata semplice, o linked list e per brevità da qui in poi lista, è una struttura dati che consente la memorizzazione di informazioni in elementi, detti anche nodi, non contigui collegati sequenzialmente  da un legame .

Lista concatenata semplice di 3 interi

Le liste sono una struttura dati molto usta nel''informatica perché:

• memorizzano una collezione di elementi in modo non contiguo;
• consentono l'inserimento o la cancellazione di un elemento con un costo costante, in termini di complessità di calcolo;
• sono una struttura dati dinamica le cui dimensioni possono essere modificate arbitrariamente;
• possono essere sia ordinate che non ordinate;
• possono essere usate per implementare molte strutture dati astratte quali:
• pile (stacks);
• code (queues);
• code doppie (deques);
• sequenze (sequences);
• code di priorità (priority queues);
• e altro ancora.

Per implementare in linguaggio C, in modo efficiente ed efficace, una lista si usano i puntatori e il tipo di dato complesso struct. Con riferimento alla rappresentazione "frecce e scatole" usata nella figura qui sopra, le frecce si implementano con i puntatori e le scatole con le struct. Nelle "scatole" si memorizza il dato di interesse, che può essere semplice o strutturato (una struct :) e il puntatore all'elemento successivo. L'ultimo elemento della lista conterrà un puntatore pari a NULL. Qui prenderemo in considerazione il caso di dato di interesse intero e quindi una possibile implementazione del tipo della "scatola" in C è la seguente:

typedef struct node{
int  payload;            // dato contenuto nel generico nodo della lista
struct node *next;   // puntatore al prossimo elemento della lista
} nodeT;                         // Tipo del generico nodo della lista

mentre l'implementazione del tipo della "freccia" è la seguente:

typedef nodeT* nodeP; // Tipo puntatore a lista

Quindi, il puntatore (= la "freccia") all'inizio della lista, una variabile di tipo nodeP, è la seguente:

nodeP firstP = NULL;        // puntatore all'inizio della lista

Poiché è molto utile poter accedere rapidamente anche all'ultimo elemento della lista, può essere utile avere una variabile puntatore per questo scopo, da aggiornare in modo opportuno durante le operazioni che modificano la lista:

nodeP lastP  = NULL;        // puntatore all'ultimo nodo della lista

Ovviamente, in alternativa a questo approccio, si può "visitare" la lista dall'inizio fino alla fine e ottenere così il puntatore all'ultimo elemento. La scelta tra i due approcci dipende dal tipo di operazioni che devono essere fatte sulla lista.

L'aggiunta di un nuovo elemento può essere fatta all'inizio o alla fine della lista. La procedura è simile nei due casi cambia solo il puntatore su cui si lavora. Vediamo come è possibile implementar l'aggiunta alla fine della lista in uno pseudolinguaggio programmativo:

Crea nuovo_elemento;
In nuovo_elemento metti il dato di interesse e poni a NULL il puntatore al successivo elemento;
Se la lista è vuota allora
  assegna il puntatore al nuovo_elemento al puntatore al primo_elemento
  assegna il puntatore al nuovo_elemento al puntatore all'ultimo_elemento
Altrimenti
  assegna il puntatore al nuovo elemento al puntatore al successivo elemento  puntato da ultimo_elemento
  assegna  il puntatore al nuovo elemento al puntatore all'ultimo_elemento.

L'implementazione in C è quindi la seguente:

void addnode(int pl, nodeP* sP, nodeP* eP){
  nodeP tempP = (nodeP)malloc(sizeof(nodeT)); //T=0
  tempP->next      = NULL;
  tempP->payload   = pl;
  if (*eP==NULL){
    *sP           = tempP;
    *eP           = tempP;  
  } else {
    (*eP)->next   = tempP; //T=1
    *eP           = tempP; //T=2
  } 
}

Si noti che la routine riceve in ingresso un intero, per il dato da memorizzare, un puntatore al puntatore inizio lista e un puntatore al puntatore fine lista. (Att: Gli ultimi due parametri sono quindi due puntatori passati by reference, e non by value.)

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 ha consentito di aggiungere un nuovo elemento alla fine della lista senza dover prima scandire tutta la lista.