In informatica, una lista concatenata è una struttura dati costituita da un gruppo di nodi che insieme rappresentano una sequenza…

In quest’articolo vedremo la più semplice delle liste, la lista semplicemente concatenata. Esistono anche altri tipi di lista, le liste doppiamente concatenate, le liste circolari semplicemente concatenate e le liste circolari doppiamente concatenate ma per approfondimenti guardate pure wikipedia

Lista Concatenata

La lista semplicemente concatenata (Singly-linked List) è una lista di elementi in cui gli elementi possono essere posizionati ovunque nella memoria heap. Tutti gli elementi della lista sono collegati tra loro utilizzando un campo per memorizzare l’indirizzo del nodo successivo.
La lista semplicemente concatenata (Singly-linked List) ha una dimensione dinamica e può essere determinata solo a run-time e non in fase di compilazione.
L’immagine sopra mostra una Singly-linked List. Ci sono quattro elementi nella lista. Il puntatore “Head” è il puntatore che punta al primo elemento della lista.

Aggiunta di un nuovo elemento alla lista

 

L’algoritmo è semplice:

– Se la lista è vuota dobbiamo inserire un nuovo elemento (o nodo) come nodo di partenza.
– In caso contrario, si attraversa la lista esistente per ottenere il puntatore all’ultimo nodo;

Creiamo un nuovo nodo.
Cambiamo il puntatore successivo dell’ultimo nodo al nuovo nodo.
Il puntatore del prossimo nuovo nodo punterà a NULL e sarà l’ultimo nodo della lista.

Implementazione di una Lista Concatenata in C
#include
#include

struct node{
int data;
struct node *next;
};

struct node* add(struct node *head, int data){
struct node *tmp;

if(head == NULL){
head=(struct node *)malloc(sizeof(struct node));
if(head == NULL){
printf(“Error! memory is not available\n”);
exit(0);
}
head-> data = data;
head-> next = head;
}else{
tmp = head;

while (tmp-> next != head)
tmp = tmp-> next;
tmp-> next = (struct node *)malloc(sizeof(struct node));
if(tmp -> next == NULL)
{
printf(“Error! memory is not available\n”);
exit(0);
}
tmp = tmp-> next;
tmp-> data = data;
tmp-> next = head;
}
return head;
}

void printlist(struct node *head)
{
struct node *current;
current = head;
if(current!= NULL)
{
do
{
printf(“%d\t”,current->data);
current = current->next;
} while (current!= head);
printf(“\n”);
}
else
printf(“The list is empty\n”);

}

void destroy(struct node *head)
{
struct node *current, *tmp;

current = head->next;
head->next = NULL;
while(current != NULL) {
tmp = current->next;
free(current);
current = tmp;
}
}
void main()
{
struct node *head = NULL;
head = add(head,1); /* 1 */
printlist(head);

head = add(head,20);/* 20 */
printlist(head);

head = add(head,10);/* 1 20 10 */
printlist(head);

head = add(head,5); /* 1 20 10 5*/
printlist(head);

destroy(head);
getchar();
}