Liste in C

Scopriamo cosa sono e come utilizzare le liste concatenate in C.

Cos’è una lista

Supponiamo di dover salvare una serie di elementi ma non sappiamo quanti potrebbero essere. Per dichiarare un array è necessario sapere il numero di elementi, quindi siamo costretti a scartare questa opzione. C’è forse un altro modo?

La risposta è si, bisogna utilizzare le liste.

Una lista è una serie di nodi collegati tra di loro. Per fare questo in C ogni nodo sarà una struct contenente un elemento e un puntatore al prossimo nodo. Un puntatore, chiamato testa della lista punterà al primo nodo. Il puntatore dell’ultimo invece verrà chiamato coda e punterà a NULL. Abbiamo appena descritto una lista semplice.

Tipi di liste

Esistono quattro tipi di liste:

Liste Semplici
Liste a doppio collegamento
Liste Circolari
Liste Circolari a doppio collegamento

Le Liste Semplici hanno un solo puntatore per nodo. In questo modo è possibile scorrere la lista ma solo per un senso, cioè dalla testa alla coda.

//LISTA SEMPLICE
struct nodo{
    int elemento;
    struct nodo* successivo;
}

Le Liste a doppio collegamento hanno due puntatori per nodo. Questo rende possibili scorrerle in entrambe le direzioni.

//LISTA DOPPIA
struct nodo{
  int elemento;
  struct nodo* precedente;
  struct nodo* successivo;
}

Nelle Liste Circolari l’ultimo puntatore anziché puntare a NULL punterà al primo nodo della lista formando appunto un cerchio.

Le liste circolari a doppio collegamento uniscono le caratteristiche delle precedenti e permettono quindi di scorrere un lista circolare in entrambe le direzioni.

Funzioni per liste

Qui sotto ho scritto una serie di funzioni che permettono di svolgere le operazioni principali con delle liste semplici, prova a darci un occhiata e se dovessi averne bisogno, sei libero di usarle!

Funzioni

#include <stdio.h>
#include <stdlib.h>


typedef struct nodo{

  int elemento;
  struct nodo* successivo;

} nodo;


//AGGIUNTA DI NODI NELLA LISTA
nodo* aggiungi_in_testa(int n, nodo* testa);
nodo* aggiungi_in_coda(int n,nodo* testa);
nodo* aggiungi_in_posizione(int n, int posizione, nodo* testa);

//RIMOZIONE DI NODI DALLA LISTA
nodo* rimuovi_in_testa(nodo* testa);
nodo* rimuovi_in_coda(nodo* testa);
nodo* rimuovi_in_posizione(int posizione,nodo* testa);

//ALTRE FUNZIONI
void stampa_lista(nodo* testa);
int cerca(int n, nodo* testa);
int conta(nodo* testa);

nodo* aggiungi_in_testa(int n, nodo* testa){
	if(testa != NULL){
		nodo* nodoSuccessivo = testa;
		testa = (nodo*) malloc(sizeof(nodo));
		testa -> elemento = n;
		testa -> successivo = nodoSuccessivo;
	}
	else{
		testa = (nodo*) malloc(sizeof(nodo));
		testa -> elemento = n;
		testa -> successivo = NULL;
	}
	return testa;
}

nodo* aggiungi_in_coda(int n, nodo* testa){
	if(testa != NULL){
		nodo* nodoSuccessivo = testa;
		while(nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
		}
	    nodoSuccessivo -> successivo = aggiungi_in_testa(n, NULL);
	}
	else{
		testa = aggiungi_in_testa(n, testa);
	}
	return testa;
}

nodo* aggiungi_in_posizione(int n, int posizione, nodo* testa){

	if(posizione == 0 || testa == NULL){
		testa = aggiungi_in_testa(n, testa);
	}
	else if(posizione > 0){
		int i=1;
		nodo* nodoSuccessivo = testa;
		while(i < posizione && nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
			i++;
		}
		nodoSuccessivo -> successivo = aggiungi_in_testa(n, nodoSuccessivo -> successivo);
	}
	return testa;
}

nodo* rimuovi_in_testa(nodo* testa){
	if(testa != NULL){
		nodo* daEliminare = testa;
		testa = testa -> successivo;
		free(daEliminare);
	}

	return testa;
}

nodo* rimuovi_in_coda(nodo* testa){
	if(testa != NULL){
		if(testa -> successivo != NULL){

			nodo* attuale = testa;
			nodo* daEliminare = testa -> successivo;

			while(daEliminare -> successivo != NULL){
				attuale = daEliminare;
				daEliminare = daEliminare -> successivo;
			}
	    	attuale -> successivo = rimuovi_in_testa(daEliminare);
		}
		else{
			testa = rimuovi_in_testa(testa);
		}
	}

	return testa;
}

nodo* rimuovi_in_posizione(int posizione, nodo* testa){


	if(posizione == 0 || testa -> successivo == NULL){
		testa = rimuovi_in_testa(testa);
	}
	else if(posizione > 0){
		int i=1;

		nodo* attuale = testa;
		nodo* daEliminare = testa -> successivo;

		while(i < posizione && daEliminare-> successivo != NULL){
                        attuale = daEliminare;
			daEliminare = daEliminare -> successivo;
			i++;
		}
		attuale -> successivo = rimuovi_in_testa( daEliminare -> successivo);

	}
	return testa;
}


void stampa_lista(nodo * testa){
	if(testa != NULL){
		printf("TESTA -> ");
		while(testa != NULL){
			printf("%d -> ",testa->elemento);
			testa = testa -> successivo;
		}
	    printf("NULL \n");
	}
	else {
		printf("LISTA VUOTA \n");
	}
}

int cerca(int n,nodo* testa){
	int posizione = -1;
	int trovato = 0;
	int i=0;
	while(testa != NULL && trovato == 0){
		if(testa -> elemento == n){
			posizione = i;
			trovato = 1;
		}
		i++;
		testa = testa -> successivo;
	}
	return posizione;
}

int conta(nodo* testa){
	int i=0;
	while(testa != NULL){
		i++;
		testa = testa -> successivo;
	}
	return i;
}

#include <stdio.h>
#include <stdlib.h>


typedef struct nodo{

  int elemento;
  struct nodo* successivo;

} nodo;


//AGGIUNTA DI NODI NELLA LISTA
void aggiungi_in_testa(int n, nodo** testa);
void aggiungi_in_coda(int n,nodo** testa);
void aggiungi_in_posizione(int n, int posizione, nodo** testa);

//RIMOZIONE DI NODI DALLA LISTA
void rimuovi_in_testa(nodo** testa);
void rimuovi_in_coda(nodo** testa);
void rimuovi_in_posizione(int posizione,nodo** testa);

//ALTRE FUNZIONI
void stampa_lista(nodo* testa);
int cerca(int n, nodo* testa);
int conta(nodo* testa);

void aggiungi_in_testa(int n, nodo** testa){
	nodo* nuovo = (nodo*) malloc(sizeof(nodo));
	nuovo -> elemento = n;
	nuovo -> successivo = *testa;
	*testa = nuovo;
}

void aggiungi_in_coda(int n, nodo** testa){
	if(*testa != NULL){
		nodo* nodoSuccessivo = *testa;
		while(nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
		}
	    aggiungi_in_testa(n, &(nodoSuccessivo -> successivo));
	}
	else{
		aggiungi_in_testa(n, testa);
	}
}

void aggiungi_in_posizione(int n, int posizione, nodo** testa){

	if(posizione == 0 || *testa == NULL){
		aggiungi_in_testa(n, testa);
	}
	else if(posizione > 0){
		int i=1;
		nodo* nodoSuccessivo = *testa;
		while(i < posizione && nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
			i++;
		}
		aggiungi_in_testa(n, &(nodoSuccessivo -> successivo));
	}
}

void rimuovi_in_testa(nodo** testa){
	if(*testa != NULL){
		nodo* daEliminare = *testa;
		*testa = (*testa) -> successivo;
		free(daEliminare);
	}

}

void rimuovi_in_coda(nodo** testa){
	if(*testa != NULL){
		if( (*testa) -> successivo != NULL){

			nodo* attuale = *testa;
			nodo* daEliminare = (*testa) -> successivo;

			while(daEliminare -> successivo != NULL){
				attuale = daEliminare;
				daEliminare = daEliminare -> successivo;
			}
	    	rimuovi_in_testa(&attuale->successivo);
		}
		else{
			rimuovi_in_testa(testa);
		}
	}

}

void rimuovi_in_posizione(int posizione, nodo** testa){


	if(posizione == 0 || (*testa) -> successivo == NULL){
		rimuovi_in_testa(testa);
	}
	else if(posizione > 0){
		int i=1;

		nodo* attuale = *testa;
		nodo* daEliminare = (*testa) -> successivo;

		while(i < posizione && daEliminare-> successivo != NULL){
			attuale = daEliminare;
			daEliminare = daEliminare -> successivo;
			i++;
		}
		rimuovi_in_testa( &(attuale -> successivo));

	}

}


void stampa_lista(nodo * testa){
	if(testa != NULL){
		printf("TESTA -> ");
		while(testa != NULL){
			printf("%d -> ",testa->elemento);
			testa = testa -> successivo;
		}
	    printf("NULL \n");
	}
	else {
		printf("LISTA VUOTA \n");
	}
}

int cerca(int n,nodo* testa){
	int posizione = -1;
	int trovato = 0;
	int i=0;
	while(testa != NULL && trovato == 0){
		if(testa -> elemento == n){
			posizione = i;
			trovato = 1;
		}
		i++;
		testa = testa -> successivo;
	}
	return posizione;
}

int conta(nodo* testa){
	int i=0;
	while(testa != NULL){
		i++;
		testa = testa -> successivo;
	}
	return i;
}

Programma di esempio

Utilizziamo le funzioni scritte in precedenza per gestire una lista di elementi.

#include <stdio.h>
#include <stdlib.h>

typedef struct nodo{

    int elemento;
    struct nodo* successivo;

} nodo;


//AGGIUNTA DI NODI NELLA LISTA
nodo* aggiungi_in_testa(int n, nodo* testa);
nodo* aggiungi_in_coda(int n,nodo* testa);
nodo* aggiungi_in_posizione(int n, int posizione, nodo* testa);

//RIMOZIONE DI NODI DALLA LISTA
nodo* rimuovi_in_testa(nodo* testa);
nodo* rimuovi_in_coda(nodo* testa);
nodo* rimuovi_in_posizione(int posizione,nodo* testa);

//ALTRE FUNZIONI
void stampa_lista(nodo* testa);
int cerca(int n, nodo* testa);
int conta(nodo* testa);


int main(){

	//Creo il nodo di testa e lo inserisco nella lista
	nodo *lista = NULL;
	lista = aggiungi_in_testa(1, lista);

	//LISTA: 1 -> NULL
	stampa_lista( lista );

	//Aggiungo un nodo alla fine della lista
	lista = aggiungi_in_coda(3, lista);

	//LISTA: 1 -> 3 -> NULL
	stampa_lista( lista );

	//Aggiungo nodo tra il primo e il secondo
	lista = aggiungi_in_posizione(2, 1, lista);

	//LISTA: 1 -> 2 -> 3 -> NULL
	stampa_lista( lista );

	//Conto il numero di nodi
	printf("Nodi: %d\n", conta( lista ) );

	//Cerco il nodo con elemento di valore 3 e lo elimino
	int posizioneDaEliminare = cerca(3, lista);
	lista = rimuovi_in_posizione(posizioneDaEliminare, lista);

	//LISTA: 1 -> 2 -> NULL
	stampa_lista( lista );

	return 0;

}



nodo* aggiungi_in_testa(int n, nodo* testa){
	if(testa != NULL){
		nodo* nodoSuccessivo = testa;
		testa = (nodo*) malloc(sizeof(nodo));
		testa -> elemento = n;
		testa -> successivo = nodoSuccessivo;
	}
	else{
		testa = (nodo*) malloc(sizeof(nodo));
		testa -> elemento = n;
		testa -> successivo = NULL;
	}
	return testa;
}

nodo* aggiungi_in_coda(int n, nodo* testa){
	if(testa != NULL){
		nodo* nodoSuccessivo = testa;
		while(nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
		}
	    nodoSuccessivo -> successivo = aggiungi_in_testa(n, NULL);
	}
	else{
		testa = aggiungi_in_testa(n, testa);
	}
	return testa;
}

nodo* aggiungi_in_posizione(int n, int posizione, nodo* testa){

	if(posizione == 0 || testa == NULL){
		testa = aggiungi_in_testa(n, testa);
	}
	else if(posizione > 0){
		int i=1;
		nodo* nodoSuccessivo = testa;
		while(i < posizione && nodoSuccessivo -> successivo != NULL){
			nodoSuccessivo = nodoSuccessivo -> successivo;
			i++;
		}
		nodoSuccessivo -> successivo = aggiungi_in_testa(n, nodoSuccessivo -> successivo);
	}
	return testa;
}

nodo* rimuovi_in_testa(nodo* testa){
	if(testa != NULL){
		nodo* daEliminare = testa;
		testa = testa -> successivo;
		free(daEliminare);
	}

	return testa;
}

nodo* rimuovi_in_coda(nodo* testa){
	if(testa != NULL){
		if(testa -> successivo != NULL){

			nodo* attuale = testa;
			nodo* daEliminare = testa -> successivo;

			while(daEliminare -> successivo != NULL){
				attuale = daEliminare;
				daEliminare = daEliminare -> successivo;
			}
	    	attuale -> successivo = rimuovi_in_testa(daEliminare);
		}
		else{
			testa = rimuovi_in_testa(testa);
		}
	}

	return testa;
}

nodo* rimuovi_in_posizione(int posizione, nodo* testa){


	if(posizione == 0 || testa -> successivo == NULL){
		testa = rimuovi_in_testa(testa);
	}
	else if(posizione > 0){
		int i=1;

		nodo* attuale = testa;
		nodo* daEliminare = testa -> successivo;

		while(i < posizione && daEliminare-> successivo != NULL){
                        attuale = daEliminare;
			daEliminare = daEliminare -> successivo;
			i++;
		}
		attuale -> successivo = rimuovi_in_testa( daEliminare -> successivo);

	}
	return testa;
}


void stampa_lista(nodo * testa){
	if(testa != NULL){
		printf("TESTA -> ");
		while(testa != NULL){
			printf("%d -> ",testa->elemento);
			testa = testa -> successivo;
		}
	    printf("NULL \n");
	}
	else {
		printf("LISTA VUOTA \n");
	}
}

int cerca(int n,nodo* testa){
	int posizione = -1;
	int trovato = 0;
	int i=0;
	while(testa != NULL && trovato == 0){
		if(testa -> elemento == n){
			posizione = i;
			trovato = 1;
		}
		i++;
		testa = testa -> successivo;
	}
	return posizione;
}

int conta(nodo* testa){
	int i=0;
	while(testa != NULL){
		i++;
		testa = testa -> successivo;
	}
	return i;
}

TESTA -> 1 -> NULL
TESTA -> 1 -> 3 -> NULL
TESTA -> 1 -> 2 -> 3 -> NULL
Nodi: 3
TESTA -> 1 -> 2 -> NULL