Souvent dans vos programmes, vous voudrez stocker une liste d'éléments, par exemple des clients. Mais il arrive aussi souvent que vous ne sachiez pas à la base combien de client vous devrez stocker dans votre programmer. Dans le cas ou c'est à l'utilisateur de choisir le nombre au départ, c'est facile, il suffit d'allouer l'espace mémoire suffisant mais si vous laissez le choix à l'utilisateur d'ajouter autant de client qu'il veut, quelle taille allez vous donner à votre tableau ? Une taille énorme pour prévoir ? Ou alors vous allez opter pour la réallocation de mémoire ? A première vue c'est une bonne idée, mais si on y réflechit de plus près et qu'on pense que réallouer la mémoire implique de d'abord la désallouer, de la réallouer et de recopier tout les éléments dans la nouvelle zone mémoire, on peut se dire que c'est une grosse perte de temps et d'efficacité, surtout si cela arrive souvent.

Il y a évidemment une solution pour éviter ces problèmes et elle n'est pas dans les tableaux mais dans les structures. Le principe est simple en fait, nous allons utiliser les structures et les lier les unes aux autres. En fait, pour bien comprendre les listes chainées, il faut faire la métaphore avec une chaine. Une chaine est composée de maillons, si nous avons envie d'allonger la chaine, on rajoute un maillon, si on veut la rétrecir, on en supprime, si on veut supprimer un maillon defectueux, on le retire simplement. Une liste chainée, c'est pareil mais avec des structures à la place des maillons.

Je préfère m'aider d'un exemple et d'images pour bien vous expliquer, nous allons donc voir comment constituer une liste chainée étape par étape.

Il va nous falloir quelques éléments avant de pouvoir mettre en place une liste chainée. Je vais parler ici de curseur, dans le monde de la programmation c'est en fait des pointeurs vers des structures, mais ici, nous parlerons de curseur pour une question de clarté. Sur les images, ils seront représentés par des flèches. Comme vous n'aimez pas faire les choses à moitié, on va faire directement une liste doublement chainée, c'est à dire une liste dans laquelle on pourra se déplacer en avant ou en arrière.

Il nous faut donc 3 curseurs : un qui retiendra la position actuelle dans la liste, un qui retiendra la position du premier maillon de la liste dans la mémoire et un autre qui retiendra la position du dernier maillon de la liste. Au début, ces pointeurs voudront NULL vu qu'il n'y a aucun maillon dans la liste.

Il faut également une structure qui servira à contenir les informations voulues, si nous imaginons que nous voulons retenir des clients, votre structure devra contenir le nom, le prénom, l'adresse, le numéro de téléphone,... enfin toutes les informations que vous voulez stocker sur le client mais ce n'est pas tout, la structure devra également contenir 2 curseurs, donc chaque maillon de votre liste contiendra les infos d'un client mais également deux curseurs. Effectivement, un curseur retiendra la position du maillon précédent le maillon auquel il appartient et un autre curseur retiendra la position du maillon suivant le maillon auquel il appartient.

Maintenant que nous possédons tout les éléments pour commencer, nous pouvons... commencer, et oui... Nous allons donc ajouter notre premier client. L'utilisateur va entrer les informations de celui-ci ce qui entrainera la création d'un maillon, plusieurs choses vont donc se passer. D'abord le curseur de début va pointer vers cette nouvelle structure, comme la liste était vide, l'ajout d'un élément en fait le premier de la liste, mais cela en fait également le curseur courant et le curseur de fin, ces deux curseurs vont donc également pointer vers cette structure. Une dernière chose dont il faut tenir compte, c'est les curseur au sein du nouveau maillon, ils vont etre initialisés tout les deux à NULL car il n'y a pas d'élément précédent ou suivant. En gros cela donnerait ceci :



Imaginons maintenant que le client désire ajouter un autre client. Il entre les informations nécessaires, du coup un chainon se crée, il va falloir le rattacher à la liste déjà existante. Le curseur de début ne changera pas, car le curseur qui existe deja restera le premier de la liste. Le curseur courant, c'est une question de choix. Effectivement, ce curseur indiquera la structure que nous sommes en train de lire donc, soit vous mettez à jour ce curseur pour pouvoir lire le nouvel élément ajouté, soit vous ne le mettez pas à jour pour être sur de ne pas créer de problèmes dans votre programme. Je choisis de ne pas le mettre à jour. Un curseur, qui lui va changer, est le curseur de fin, effectivement, celui-ci va devoir pointer vers le nouvel élément ajouté.

Si maintenant, nous pensons au curseur de position à l'intérieur des structures. Le curseur vers le maillon précédent du premier élément restera inchangé, par contre le curseur vers l'élément suivant lui, devra maintenant pointer vers le nouvel élément ajouté, mais il faudra aussi que le curseur vers le maillon précédent du nouvel élément pointe vers le premier élément de la liste. Graphiquement, cela donnerait ceci :



Comme vous le voyez, les curseurs sont bien à jour. Pour la clarté du reste des explications, imaginons que l'utilisateur ajoute encore 2 clients, cela donnerait :



Les curseurs sont bien à jour. Comme vous le voyez, nous pouvons voyager aisément dans notre liste chainée. Si nous désirons accéder au troisième élément, il suffit de suivre le premier curseur vers le maillon suivant pour accéder au deuxieme en modifiant ainsi la position du curseur courant, effectivement, si nous attribuons comme valeur au curseur courant la valeur du curseur vers le maillon suivant, cela revient à déplacer le curseur courant sur le deuxième élément de la liste, ensuite, nous faisons de même avec le curseur vers le maillon suivant par rapport au deuxième pour placer le curseur courant sur le troisième élément de la liste :



Vous voyez que vous pouvez ainsi vous déplacer dans le sens que vous voulez dans votre liste chainée. Passons maintenant à l'insertion d'un maillon. Quand je dis "insérer un maillon", ce n'est pas bêtement rajouter un élément à la fin de la liste chainée, ca nous l'avons deja vu, c'est plutôt insérer un maillon au beau milieu de la liste. Graphiquement cela se passerait ainsi :



Ici, nous ne touchons pas au curseur courant, ni au curseur de début et de fin, effectivement, comme le maillon est juste inséré, ces curseurs n'ont pas à être modifiés, par contre il va falloir modifier plusieurs curseurs suivants et précédents de maillon de la liste. Premièrement, nous allons devoir modifier le curseur vers le maillon suivant du maillon se trouvant avant celui inséré. Ce curseur devra pointer vers le maillon inséré. Nous devrons également modifier le curseur vers le maillon précédent du maillon se trouvant juste après le maillon inséré. Ce curseur devra pointer vers le nouveau maillon inséré. Une fois ceci fait, il faudra aussi modifier le curseur vers le maillon précédent du nouveau maillon et également modifier le curseur vers le maillon suivant du nouveau maillon. Une fois tout cela fait, le maillon sera parfaitement inséré :



Comme vous le voyez, votre liste chainée est parfaite. Le déplacement dans celle-ci est tout a fait possible et ce dans les deux sens. Passons maintenant à la suppression de maillon. Imaginons que nous voulons supprimer le premier maillon. Beaucoup de vérification devront être faites à ce moment là. Tout d'abord, nous devrons modifier le curseur de début. Deux solutions s'imposent : soit la liste contient d'autre élément et il suffit de rediriger le curseur de début vers la position pointée par le curseur vers le maillon suivant du premier maillon de la chaine, ensuite, il suffit simplement de désallouer la mémoire occupée par le premier élément de la liste et de mettre à NULL le curseur vers le maillon précédent du nouveau premier maillon. La deuxième solution est si l'élément est le seul dans la liste. Dans ce cas, c'est encore plus simple, il suffira de désallouer l'espace occupé par ce maillon et de mettre tout les curseurs de position à NULL. Dans notre exemple,cela donnerai ceci :



Ce qui donnera finalement :



Imaginons maintenant que nous voulions supprimer le maillon courant, donc celui pointé par la flèche rouge. Nous allons tout d'abord devoir faire un choix, effectivement, quand nous allons le supprimer, il va falloir choisir vers quel maillon pointera le curseur courant, soit vers le maillon précédent ou le maillon suivant. Pour notre exemple, je choisirai de le faire pointer vers le maillon précédent. Donc quand nous allons le supprimer, il va également falloir mettre à jour le curseur vers le maillon suivant du maillon précédant le maillon à supprimer, celui-ci devra pointer vers le maillon suivant le maillon à supprimer. Nous devrons également mettre à jour le curseur vers le maillon précédent du maillon suivant le maillon à supprimer, celui-ci devra pointer vers le maillon précédant le maillon à supprimer. Ensuite, nous mettons à jour le curseur vers le pointeur courant, une fois ceci fait, nous pouvons désallouer la mémoire alloué par le maillon à supprimer, graphiquement, cela donnerait ca :



Imaginons maintenant que nous voulons supprimer le maillon de début de liste. Nous devrons tout d'abord mettre à jour le curseur de début vers le maillon suivant celui que l'on va supprimer. Une fois ceci fait, nous devrons également modifier le curseur courant vu que celui-ci pointe vers le maillon à supprimer. Une fois cela fait, il faudra simplement mettre à NULL le curseur vers le maillon précédent du maillon suivant celui à supprimer. Il nous suffira enfin de désallouer la mémoire occupée par le maillon à supprimer.



Maintenant, nous allons supprimer le maillon de fin. Nous allons donc devoir modifier le curseur de fin, on va faire pointer celui-ci vers le maillon précédant celui que l'on va supprimer. Ensuite, c'est simple, il suffira de mettre à NULL le curseur vers le maillon suivant du maillon précédant le maillon à supprimer, enfin, il nous suffira de désallouer l'espace mémoire occupé par le dernier maillon de la liste. Cela donnerait donc :



Maintenant, nous allons supprimer l'élément restant, là ce n'est pas dur, il suffit de désallouer l'espace occupé par ce maillon et mettre à NULL tout les autres curseurs. Et votre liste sera vide.

Voilà, vous savez maintenant comment fonctionne une liste chainée, on peut évidemment imaginer plein d'autre manipulations de cette liste, comme par exemple la trier, l'inverser, faire une rechercher à l'intérieur,... Mais ça, il va vous falloir réflechir à comment faire, ou alors peut être que je l'expliquerai dans les TP de programmation.