Les listes chaînées sont très utiles pour la représentation d’éléments disposant de quantités variables. Leur conception permet de modéliser de nombreuses situations impliquant une gestion ordonnée de l’information. Ainsi, les piles, les files, les arbres sont des candidats idéaux à l’utilisation de listes chaînées. Elles pourront être « simplement chaînées » ou « doublement chaînées » pour permettre un parcours en sens unique ou bien dans les deux sens.
En pratique, une liste chaînée repose sur l’usage des structures du langage C, chaque structure disposant du moyen d’atteindre au minimum son successeur (liste simplement chaînée), au mieux son prédécesseur et son successeur (liste doublement chaînée). Ce chaînage est réalisé au moyen de pointeurs, éléments essentiels à connaître pour une bonne pratique du langage c.
Un pointeur est une variable représentant l’emplacement mémoire d’une autre variable. Au lieu de contenir une valeur directement exploitable, le pointeur référence un autre emplacement qui, lui, va contenir notre information. Grâce à un pointeur nous créons une indirection dans l’accès aux données. C’est une notion extrêmement importante et elle prendra tout son sens dans les lignes qui vont suivre.
Une liste chaînée est donc un ensemble d'éléments (généralement des structures au sens "C" du terme) qui disposent chacun d'un pointeur vers la structure suivante de la liste. Si l'objet dispose à la fois des pointeurs vers les structures suivantes et précédentes, alors la liste est définie comme étant doublement chaînée.
Une structure peut être du type suivant :
struct node {
int x;
struct node *next;
};En langage C, à l'opposé d'un grand nombre d'autres langages qui masquent cette gestion mémoire, toute réservation d'objet en mémoire doit être allouée systématiquement par l'intermédiaire des fonctions de gestion de mémoire comme malloc(), calloc() ou realloc(). Il faudra également bien penser à libérer l'espace utilisé par ces structures en fin de programme. L'efficacité du langage passe par des contraintes plus strictes que celles de Python ou Rust...
/* Ceci est le premier noeud de la liste, qui permet d'initier le chainage */
struct node *head;
/* Allocation d'un espace mémoire de la taille de la structure node */
head = (struct node *)malloc(sizeof(struct node));
/* Comme il n'y a pas d'autre noeud, le pointeur vers le noeud suivant est NULL */
head->next = NULL;
/* Affecte une valeur à la variable x incluse dans le noeud */
head->x = 42;
/* Libération de la mémoire utilisée */
if (head) free(head);
Parcourir une liste chainée consiste à passer d'un noeud à l'autre par l'intermédiaire de la valeur contenue dans le pointeur next jusqu'à trouver une valeur NULL (ou 0). Dans notre exemple nous parcourons une liste simplement chainée, simplement car elle ne dispose que d'un seul sens possible de parcours (avec un chainage).
/* Pointeur sur le premier élément de la liste chainée (la tête de liste) */
struct node *ptr = head;
if (ptr) {
while (ptr->next != NULL) {
printf("%d\n", ptr->x);
ptr = ptr->next;
}
}
Si l'on souhaite ajouter un élément dans cette liste, il faut jouer avec les pointeurs pour inclure le nouveau pointeur dans la liste existante.
/* Alloue de la mémoire pour la structure sur le pointeur next */
ptr->next = (struct node *)malloc(sizeof(struct node));
/* Fait pointer le pointeur de parcours de liste sur le dernier élément alloué */
ptr = ptr->next;
/* Met le pointeur de fin de liste à NULL */
ptr->next = NULL;
ptr->x = 73;
Pour faire en sorte que la liste soit doublement chainée, il suffit de rajouter un pointeur vers la structure précédente
struct node {
int x;
struct node *prev;
struct node *next;
};
/* Pointeur de tête */
struct node *head = (struct node *)malloc(sizeof(struct node));
head->prev = NULL;
head->next = NULL;
head->x = 42; /* valeur sans importance */
Avec les deux pointeurs, nous pouvons alors parcourir la liste dans les deux sens en utilisant les pointeurs prev ou next selon le sens de recherche. Le principe est le même que pour la liste simplement chainée donc référez-vous à l'exemple qui le concerne.
Pour ajouter un élément dans la liste, il faut allouer un nouveau pointeur et refaire le chainage pour intégrer cet élément :
Une pile est une structure qui consiste à traiter les éléments dans le sens (dernier entré, premier sorti). Dans la littérature, cela s’appelle LIFO (Last In, First Out). Imaginez-vous simplement une pile d’assiettes. Si vous aviez besoin de prendre une assiette, enlèveriez-vous celle se trouvant tout en bas de la pile ? Non... La première au-dessus de la pile vous conviendrait parfaitement... En informatique, la notion de pile est exactement la même : on empile les éléments d’un côté et les dépile du même, d’où le terme LIFO.
Le haut de la pile est repéré par un pointeur. Chaque nouvelle valeur vient s’intercaler entre le pointeur de haut de pile et le premier véritable élément de la pile. Le schéma ci-contre détaille l’aspect que prend une structure empilée complète.
Les opérations possibles avec une pile sont les suivantes :
Pour l’implémentation informatique de l’algorithme relatif à la gestion d’une pile, une structure à base de tableau pourrait être mise en place, plus simple que les listes chaînées, mais également plus restrictive car il est beaucoup plus compliqué de modifier le nombre d'éléments d'un tableau que d'une liste dynamique.
