Cours : Les listes chaînées

Lorsque nous avons parlé de la mémoire, nous avons vu qui si nous déclarions un tableau, il avait besoin d'être stocké dans un seul bloc de mémoire, ou chaque octet est à la suite du précédent.

Si par exemple, je veux stocker la chaine Hello World!\n en mémoire :

	0	1	2	3	4	5
0
1		H	e	l	l	o
2		W	o	r	l	d
3	!	\n
4

Ce qui m'oblige à avoir des grands pans de mémoire libre, alors que notre mémoire est à accès aléatoire.

Si mon tableau est trop long cela peut très rapidement me poser des problèmes (imaginez que je veux faire des calculs statistiques avec des centaines de milliers de données numériques).

Une solution imaginée lors de la création du C était d'utiliser les pointeurs pour faire des liens entre différents éléments placés un peu partout dans la mémoire.

Le principe

Une liste chainée, c'est une liste de maillons qui contiennent chacun un pointeur vers le maillon suivant.

(Une liste est appellée doublement chainée si elle contient un pointeur vers le maillon suivant et un autre pointeur vers le maillon précédent)

Pour implémenter ce concept en C, on utilise des structures.

Exemple

Imaginons que je souhaite stocker une liste de positions sur une carte, la structure de base ressemblerait à ceci :

typedef struct s_pos position;

struct s_pos {
	int pos_y;
	int pos_x;
};

Cette structure me permet de stocker une position sur ma carte.

Je vais ensuite lui ajouter un pointeur sur une autre position :

typedef struct s_pos position;

struct s_pos {
	int pos_y;
	int pos_x;
	position * next;
};

Pour indiquer à mon dernier maillon qu'il est bien le dernier maillon de la chaine je vais pointer sa sous-variable next sur NULL.

Si je voulais stocker une liste de 3 positions dans ma mémoire :

28 ; 14
37 ; 56
42 ; 23

Si je les stocke sous forme de tableau ma mémoire ressemblera à ça :

	0	1	2	3	4	5
0	28	14	37	56	42	23
1
2
3
4

Si je les stocke sous forme de liste chainée :

	0	1	2	4	5
0		28	14
1
2	37	56
3
4				42	23

Implémentation

Les listes chaînées sont un concept de programmation, la structure des données sera différente en fonction du contexte. Par contre, elle contiendra toujours un pointeur vers le maillon suivant.

Structure de la liste chaînée d'exemple

typedef struct s_pos pos;

struct s_pos {
	int pos_y;
	int pos_x;
	pos *next;
};

Créer une liste chaînée

On créé le premier maillon en mettant son pointeur next à NULL.

pos *create_list(int pos_y, int pos_x)
{
	pos *first = malloc(sizeof(*first));
	first->pos_y = pos_y;
	first->pos_x = pos_x;
	first->next = NULL;

	return first;
}

Parcourir une liste chaînée

On utilise un pointeur temporaire tmp pour parcourir la liste tant que nous ne sommes pas à la fin de la liste.

void display_list(pos **list)
{
	pos *tmp = *list;

	while(tmp != NULL)
	{
		printf("Y : %d X : %d\n", tmp->pos_y, tmp->pos_x);
		tmp = tmp->next;
	}
}

Ajouter un maillon à la fin

On utilise un pointeur temporaire tmp pour parcourir la liste tant que nous ne sommes pas à la fin de la liste. Le next du dernier maillon devient le nouveau maillon, le next du nouveau maillon est NULL >

void add_to_end(pos **list, int pos_y, int pos_x)
{
	pos *tmp = *list;

	while(tmp->next != NULL)
	{
		tmp = tmp->next;
	}

	pos *item = malloc(sizeof(*item));
	item->pos_y = pos_y;
	item->pos_x = pos_x;
	item->next = NULL;

	tmp->next = item;
}

Retirer un maillon

On parcourt la liste jusqu'à trouver le maillon que l'on souhaite retirer. Le next du maillon précédent devient le maillon qui était le next de celui à retirer.

[ maillon ] ----> [ à retirer ] ----> [maillon]

               ___________________ 
               |                 |
[ maillon ]----|  [ à retirer]   |----> [maillon]

[ maillon ] ----> [ maillon ]

void remove_link(pos **list, int pos_y, int pos_x)
{
	pos *tmp = *list;

	while(tmp->next != NULL)
	{
		if((tmp->next->pos_x == pos_x) && (tmp->next->pos_y == pos_y))
		{
			pos *to_remove = tmp->next;
			tmp->next = to_remove->next;
			free(to_remove);
		}

		tmp = tmp->next;
	}
}

Supprimer une liste

On parcourt la liste et on utilise un pointeur temporaire pour pouvoir free les maillons un par un.

void delete_list(pos **list)
{
	pos *tmp = *list;

	while(tmp != NULL)
	{
		pos *to_remove = tmp;
		tmp = tmp->next;
		free(to_remove);
	}
}

29 September 2025