Les listes doublement chainées en langage C Online

Introduction du cours

Bonjour à tous les lecteurs.

Dans son tutoriel, lexou présente un nouveau type de structure de données: les listes chainées. En lisant son tutoriel, vous êtes alors capables de vous fabriquer votre propre petit module vous permettant de manipuler vos listes chainées. Seulement, son tutoriel ne fait uniquement objet des listes simplement chainées. lexou vous parle alors dans sa conclusion des listes doublement chainées.

Dans la continuité du tutoriel de lexou, je vous propose d'apprendre à manier les listes dites doublement chainées. A la fin de ce tutoriel, vous devriez être capables de mettre en place votre propre module de manipulation des listes doublement chainées. Il est aussi à noter qu'à la fin de ce tutoriel, nous aurons l'occasion d'étudier un cas d'utilisation de nos listes doublement chainées.

Afin de suivre et de comprendre pleinement les notions évoquées par ce tutoriel, je vous recommande la lecture du tutoriel de lexou ci-dessus. Il est aussi bien entendu évident qu'une lecture du tutoriel de M@teo jusqu'aux pointeurs et l'allocation dynamique est obligatoire.

Vous voilà avertis. Commençons sans plus attendre.

Première approche

Avant de commencer à programmer quoi que ce soit, nous nous devons de voir la théorie concernant les listes doublements chainées. Tout d'abord, faisons quelques rappels.

Les listes chainées se présentent comme une alternative aux tableaux pour le stockage de certaines données. En effet, dans certaines situations, l'usage des tableaux peut se révéler inefficace.

Pourquoi les tableaux ne suffisent t-ils pas ?

Vous devriez savoir que lorsque vous créez un tableau, vous connaissez sa taille à l'avance, que ce soit avec l'utilisation ou non de malloc. Ainsi, vous vous retrouvez limités par la taille de votre tableau. Il est cependant possible à tout moment d'agrandir un tableau, mais ceci n'est pas la meilleur solution envisageable. Pour pallier à cette limitation, nous allons donc utiliser des listes chainées. Alors que les éléments d'un tableau sont contigües en mémoire, les éléments d'une liste chainées sont quant à eux tous reliés via une série de pointeurs.
Ainsi, lorsque chaque élément d'une liste chainée pointe vers l'élément suivant, nous parlons de liste simplement chainée. Lorsque chaque élément d'une liste pointe à la fois vers l'élément suivant et précédent, nous parlons alors de liste doublement chainée. Retenez donc qu'une liste chainée nous permet de stocker un nombre inconnu d'éléments.

Voici une représentation schématique des listes doublement chainées:

Vous pouvez donc voir sur ce schéma que chaque élément d'une liste doublement chainée contient :

• Une donnée (ici un simple entier)

• Un pointeur vers l'élément suivant (NULL si l'élément suivant n'existe pas)

• Un pointeur vers l'élément précédent (NULL si l'élément précédent n'existe pas)

Passons maintenant à la représentation de ces listes en langage C.

Représentation d'une liste en langage C

Qu'allons nous utiliser pour nous représenter ces listes en langage C. La réponse est toute simple. Nous allons tout simplement utiliser une structure. En effet, en langage C, les structures sont très pratiques pour créer de nouveaux types de données. Pour être plus précis, nous allons utiliser exactement deux structures. Voici la première :

struct node { int data; struct node *p_next; struct node *p_prev; };

Cette première structure va nous permettre de représenter un 'node' (élément) de notre liste chaînée. Nous pouvons alors voir que chaque élément de notre liste contiendra un élément de type int. D'autre part :

• p_next pointera vers l'élément suivant (ou NULL s'il s'agit du dernier élément de la liste)

• p_prev pointera vers l'élément précédent (ou NULL s'il s'agit du premier élément)

Les liens entre les différents éléments de notre liste chaînée sont donc assurés par nos deux pointeurs p_next et p_prev.

Afin de bien visualiser nos pointeurs, nous utiliserons le préfixe p_ pour toutes nos variables pointeurs.

Pour représenter notre liste chaînée à proprement parler, nous utiliserons une deuxième liste que voici :

typedef struct dlist { size_t length; struct node *p_tail; struct node *p_head; } Dlist;

Attends attends, c'est quoi ça size_t ? Et ça veut dire quoi p_tail et p_head ?

Tout d'abord, nous utilisons une variable nommée length contenant la taille de notre liste chaînée (length = taille en anglais). Grâce à cette variable, nous aurons accès au nombre d'éléments de notre liste chaînée. Cependant, cette variable peut paraître un peu particulière puisqu'elle est de type size_t. Ce fameux size_t correspond à un entier non signé c'est à dire un entier positif (ça tombe bien car notre liste chaînée ne pourra pas contenir -1 élément). Ce type est de ce fait communément utilisé pour tout ce qui concerne les tailles (taille d'un tableau, ...).
Enfin, éclaircissons ce fameux p_tail et p_head, à quoi vont-ils bien nous servir ? Ceci est tout simple. p_head va pointer vers le premier élément de notre liste alors que p_tail va pointer vers le dernier élément. Ainsi, nous garderons de manière permanente un pointeur vers le début et la fin de la liste.

Ok, mais à quoi ça va nous servir ?

Et bien cela va tout simplement servir à faciliter les différentes opérations que nous effectuerons sur nos listes. En effet, pour exemple, lorsque nous souhaiterons ajouter un élément en fin de liste, nous n'aurons pas besoin de parcourir la liste dans sa totalité pour ajouter l'élément en fin car nous disposerons directement d'une référence vers la fin de liste ;) .
Enfin, afin de faciliter l'écriture, nous créons un alias de notre structure grâce à l'opérateur typedef. Nous appelons cet alias Dlist pour Double List. Pour utiliser une liste dans nos programmes nous utiliserons alors :

Dlist *list = NULL; /* Déclaration d'une liste vide */

Voilà, vous savez maintenant comment est définie une liste doublement chaînée en langage C. Voyons maintenant comment la manipuler.

Manipulation d'une liste doublement chainée (1/2)

Nous savons désormais comment déclarer une liste doublement chaînée en langage C. Nous allons maintenant créer des fonctions nous permettant de réaliser plusieurs opérations sur ces fameuses listes.

Avant de regarder le code, je vous conseille de réaliser ces fonctions par vous-même, vous progresserez plus vite ;) .

Commençons alors par notre première fonction.

Allouer une nouvelle liste

Avant de pouvoir commencer à utiliser notre liste chaînée, nous allons créer une fonction nous permettant d'allouer de l'espace mémoire pour notre liste chaînée. La fonction retournera la liste chaînée nouvellement créée. Voici cette fameuse fonction

Dlist *dlist_new(void) { Dlist *p_new = malloc(sizeof *p_new); if (p_new != NULL) { p_new->length = 0; p_new->p_head = NULL; p_new->p_tail = NULL; } return p_new; }

Pour respecter une certaine convention, toutes nos fonctions seront de la forme dlist_.

Comment fonctionne cette fonction ? Je pense que vous l'aurez deviné sans trop de problèmes. Tout d'abord, nous créons une variable p_new qui sera notre nouvelle liste. Nous utilisons alors malloc pour réserver de l'espace mémoire pour cette liste.

La syntaxe suivante:

int *p_data = malloc(sizeof *p_data);

Est identique à:

int *p_data = malloc(sizeof(int));

De cette manière, si l'on modifie notre type, on n'aura pas besoin de le modifier dans notre malloc ;) .

Ensuite et de manière générale, il est nécessaire de vérifier si notre malloc n'a pas échoué. En effet, si celui-ci renvoie NULL, et que nous essayons d'accéder aux éléments de notre structure Dlist, c'est le drame :D .
Enfin, nous mettons nos pointeurs p_head ainsi que p_tail à NULL (vu que notre liste est vide), puis nous initialisons la taille de notre liste à 0 et nous retournons notre nouvelle liste.

Ajouter un élément

Après avoir alloué une nouvelle liste chaînée, voyons maintenant comment ajouter un élément dans celle-ci.

Ajout en fin de liste

Grâce à la forme de notre structure, l'ajout en fin de liste va être simplifié. En effet, rappelez-vous, nous gardons toujours un pointeur vers la fin de notre liste, nous n'avons donc nul besoin de parcourir la liste en entier afin d'arriver au dernier élément, nous l'avons déjà. Voici comment va se passer l'ajout en fin de liste:

A partir de ce schéma, essayons d'en déduire un algorithme. Tout d'abord, nous devons vérifier si notre liste n'est pas NULL. Si elle ne l'est pas, nous allons créer un nouvel élément (nouveau node). Une fois celui-ci créé, nous devons stoquer notre donnée dans le champ donnée (data) de notre structure puis faire pointer p_next vers NULL car ce sera le dernier élément de notre liste. A partir de là, deux possibilités s'offrent à nous :

• S'il n'existe pas de dernier élément (donc la liste est vide) Alors

  • Nous faisons pointer p_prev vers NULL

  • Nous faisons pointer la tête et la fin de liste vers notre nouvel élément

• Sinon

  • Nous rattachons le dernier élément de notre liste à notre nouvel élément (début du chaînage)

  • Nous faisons pointer p_prev vers le dernier élément de notre liste

  • Nous faisons pointer notre fin de liste vers notre nouvel élément (fin du chaînage)

Enfin, nous incrémentons notre champ length de notre liste puis nous retournons la liste. Tout ceci constitue alors l'algorithme d'ajout en fin de liste. Essayez tout d'abord de le coder par vous même, cela sera bénéfique pour vous et vous aidera à comprendre le concept. Si vous bloquez, munissez vous d'une feuille et d'une crayon et essayez de représenter toutes les étapes sur votre feuille. Ensuite, réessayez de coder l'algorithme.
Voici l'implémentation :

Dlist *dlist_append(Dlist *p_list, int data) { if (p_list != NULL) /* On vérifie si notre liste a été allouée */ { struct node *p_new = malloc(sizeof *p_new); /* Création d'un nouveau node */ if (p_new != NULL) /* On vérifie si le malloc n'a pas échoué */ { p_new->data = data; /* On 'enregistre' notre donnée */ p_new->p_next = NULL; /* On fait pointer p_next vers NULL */ if (p_list->p_tail == NULL) /* Cas où notre liste est vide (pointeur vers fin de liste à NULL) */ { p_new->p_prev = NULL; /* On fait pointer p_prev vers NULL */ p_list->p_head = p_new; /* On fait pointer la tête de liste vers le nouvel élément */ p_list->p_tail = p_new; /* On fait pointer la fin de liste vers le nouvel élément */ } else /* Cas où des éléments sont déjà présents dans notre liste */ { p_list->p_tail->p_next = p_new; /* On relie le dernier élément de la liste vers notre nouvel élément (début du chaînage) */ p_new->p_prev = p_list->p_tail; /* On fait pointer p_prev vers le dernier élément de la liste */ p_list->p_tail = p_new; /* On fait pointer la fin de liste vers notre nouvel élément (fin du chaînage: 3 étapes) */ } p_list->length++; /* Incrémentation de la taille de la liste */ } } return p_list; /* on retourne notre nouvelle liste */ }

Le code ci-dessus est entièrement commenté, il ne sera donc pas nécessaire d'ajouter de commentaires. N'hésitez pas à relire ce morceau de code. Si vous avez des difficultés à le comprendre, jouez le rôle du compilateur et imaginez vous le déroulement de chaque instruction ;) .

Ajout en début de liste

Pour ajouter un élément en début de liste, nous allons utiliser exactement le même procédé que pour l'ajout en fin de liste. Et oui, grâce à nos pointeurs en début et en fin de liste, nous pouvons nous permettre de reprendre nos implémentations. Si vous avez bien compris comment se passait l'ajout en fin de liste, vous n'aurez aucun de mal à réaliser l'ajout en début de liste. Là aussi, essayez d'abord par vous même de programmer cet algorithme.

Voici la fonction finale :

Dlist *dlist_prepend(Dlist *p_list, int data) { if (p_list != NULL) { struct node *p_new = malloc(sizeof *p_new); if (p_new != NULL) { p_new->data = data; p_new->p_prev = NULL; if (p_list->p_tail == NULL) { p_new->p_next = NULL; p_list->p_head = p_new; p_list->p_tail = p_new; } else { p_list->p_head->p_prev = p_new; p_new->p_next = p_list->p_head; p_list->p_head = p_new; } p_list->length++; } } return p_list; }

Il y a comme des ressemblances entre les deux fonctions vous ne trouvez pas :D .

Insérer un élément

Nous disposons désormais de fonctions permettant d'ajouter un élément en début ainsi qu'en fin de liste. Mais si l'on désire ajouter un élément nimporte où dans notre liste ? Et bien nous allons justement créer une fonction pour ceci. Comment allons-nous procéder ? Posons-nous et réfléchissons cinq minutes. Tout d'abord, nous aurons besoin de parcourir notre liste. Nous aurons aussi besoin d'un compteur (que l'on nommera) i afin de nous arrêter à la position où nous souhaitons insérer notre nouvel élément. Jusqu'ici, rien de bien sorcier. Il nous faut alors réfléchir des différents cas de figure qui peuvent intervenir lorsque nous aurons trouvé notre position:

• Soit nous sommes en fin de liste

• Soit nous sommes en début de liste

• Soit nous sommes en milieu de liste

Cependant, les deux premiers cas sont très faciles à traîter. Enfin, nous disposons de fonctions permettant d'ajouter un élément en début et en fin de liste, il nous suffit donc de les réaliser. Le plus gros de notre travail sera alors de gérer le cas où nous nous trouvons en milieu de liste. Voici un petit schéma permettant de mieux cerner la situation:

Le chaînage va être légèrement plus compliqué. En effet, nous devrons tout d'abord relier nos éléments suivant et précédent à notre nouvel élément puis, inversement, nous devrons relier notre nouvel élément aux éléments suivant et...