3 - La liste doublement chaînée.

Introduction :

Une liste doublement chaînée est une liste dont chaque élément peut accéder à l'aide de pointeurs aux éléments positionnés immédiatement avant et après lui dans la liste. Le chaînage se fait donc dans les deux sens, ce qui permet de parcourir la liste en avant comme en arrière, ce qui n'était pas possible avec la liste simple.
De plus s'il est aisé d'ajouter des éléments à chaque extrémité d'une liste simple, cela l'est beaucoup moins quand il s'agit de retirer l'élément en fin de liste (dans le sens du chaînage). La liste doublement chaînée nous en facilitera la tâche.
Comme pour la liste simple les éléments de la liste sont chaînés entre eux à l'aide de pointeurs sur des éléments du même type qu'eux. Dans le cas de la liste chaînée double, chaque élément aura un pointeur sur l'élément précédent et un pointeur sur l'élément suivant.

Un exemple concret :

Nous allons nous aider d'un exemple simple. Comme dans la liste simple nous mémoriserons seulement un entier dans chaque élément.

        typedef struct elem
        {
                int value;
                struct elem *prev;
                struct elem *next;
        } elem ;

Notre liste aura deux points d'entrée un en tête de liste l'autre en fin de liste. Pour éviter de traîner deux pointeurs, nous les mettrons dans une structure. Ceci aura pour avantage de n'avoir qu'une seule variable à traiter par liste.

        typedef struct
        {
          elem *first;
          elem *last;
        }dblist;

Nous allons construire cette liste afin qu'on puisse y insérer des éléments en début ou en fin de liste et qu'on puisse les en retirer aussi bien par le début que par la fin de liste. Aidons nous d'un schéma :

Ici aussi il faudra initialiser les pointeurs d'entrée à NULL, comme ils sont deux et pour simplifier l'utilisation de la liste nous allons nous aider d'une fonction que l'on nommera Init.

void Init(dblist *l)
{
   l->first = NULL;
   l->last = NULL;
}

L'appel de la fonction Init est donc obligatoire avant toute utilisation de la liste. Elle ne doit pas être appelée sur une liste déjà initialisée et surtout pas si la liste n'est pas vide sinon nos pointeurs de début et de fin de liste seraient perdus à jamais.

Pour l'insertion d'éléments nous utiliserons deux fonctions PushBack et PushFront la première ajoutera l'élément en fin de liste et la deuxième en début de liste. Elles recevront donc comme paramètres la valeur à mémoriser mais aussi l'adresse d'une variable de type dblist préalablement défini.

void PushBack(dblist *l, int val)
{
   elem *nouv = malloc(sizeof(elem));
   if(!nouv) exit(1);
   nouv->value = val;
   nouv->prev = l->last;
   nouv->next = NULL;
   if(l->last) l->last->next = nouv;
   else l->first = nouv;
   l->last = nouv;        
}
/******************************************************************************/

void PushFront(dblist *l, int val)
{
   elem *nouv = malloc(sizeof(elem));
   if(!nouv) exit(1);
   nouv->value = val;
   nouv->next = l->first;
   nouv->prev = NULL;      
   if(l->first) l->first->prev = nouv;
   else l->last = nouv;
   l->first = nouv;
}

Le principe est fort semblable à la liste simple, donc sans commentaire. Attention toutefois dans le cas de l'insertion du premier élément de la liste les deux pointeurs de la structure dblist devront pointer sur cet élément.
Voici un exemple d'utilisation des fonctions PushBack et PushFront :

        dblist MaListe;

        /*La liste doit obligatoirement être initialisé avant utilisation*/
        Init(&MaListe);

        PushFront(&MaListe,10);
        PushBack(&MaListe,20);

Le retrait des valeurs ce fera à l'aide des fonctions PopBack et PopFront la première retirera l'élément de fin de liste et la deuxième celui de début de liste. Elles recevront évidement comme paramètre l'adresse de la variable identifiant la liste et retourneront la valeur de l'élément retiré.

int PopBack(dblist *l)
{
   int val;
   elem *tmp = l->last;
   if(!tmp) return -1;
   val = tmp->value;
   l->last = tmp->prev;
   if(l->last) l->last->next = NULL;
   else l->first = NULL;
   free(tmp);
   return val;
}
/******************************************************************************/

int PopFront(dblist *l)
{
   int val;
   elem *tmp = l->first;
   if(!tmp) return -1;
   val = tmp->value;
   l->first = tmp->next;
   if(l->first)l->first->prev = NULL;
   else l->last = NULL;
   free(tmp);
   return val;
}

Ici aussi le principe est semblable à la liste simple, donc aussi sans commentaire. Attention toutefois dans cas du retrait du dernier élément de la liste les deux pointeurs de la structure dblist devront pointer sur NULL.

Codes sources de l'exemple :

dblist.h :

#ifndef CGI_DBLIST_H
#define CGI_DBLIST_H

 /*  Structure représantant un élément de la liste. */

        typedef struct elem
        {
                int value;
                struct elem *prev;
                struct elem *next;
        } elem ;

 /*  Structure d'accés à la liste. */

        typedef struct
        {
          elem *first;
          elem *last;
        }dblist;

#ifdef __cplusplus
extern "C" {
#endif

 /*  Initialisation de la liste. */

        void Init(dblist *l);

 /*  Ajout d'une valeur en fin de liste. */

        void PushBack(dblist *l, int val);

 /*  Ajout d'une valeur en début de liste. */

        void PushFront(dblist *l, int val);

 /*  Retrait d'une valeur en fin de liste. */

        int PopBack(dblist *l);

 /*  Retrait d'une valeur en début de liste. */

        int PopFront(dblist *l);

 /*  Affichage de toute la liste. */

        void View(dblist l);

 /*  Vidage de toute la liste. */

        void Clear(dblist *l);

#ifdef __cplusplus
}
#endif

#endif

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

#include "dblist.h"

void Init(dblist *l)
{
   l->first = NULL;
   l->last = NULL;
}
/******************************************************************************/

void PushBack(dblist *l, int val)
{
   elem *nouv = malloc(sizeof(elem));
   if(!nouv) exit(1);
   nouv->value = val;
   nouv->prev = l->last;
   nouv->next = NULL;
   if(l->last) l->last->next = nouv;
   else l->first = nouv;
   l->last = nouv;        
}
/******************************************************************************/

void PushFront(dblist *l, int val)
{
   elem *nouv = malloc(sizeof(elem));
   if(!nouv) exit(1);
   nouv->value = val;
   nouv->next = l->first;
   nouv->prev = NULL;      
   if(l->first) l->first->prev = nouv;
   else l->last = nouv;
   l->first = nouv;
}
/******************************************************************************/

int PopBack(dblist *l)
{
   int val;
   elem *tmp = l->last;
   if(!tmp) return -1;
   val = tmp->value;
   l->last = tmp->prev;
   if(l->last) l->last->next = NULL;
   else l->first = NULL;
   free(tmp);
   return val;
}
/******************************************************************************/

int PopFront(dblist *l)
{
   int val;
   elem *tmp = l->first;
   if(!tmp) return -1;
   val = tmp->value;
   l->first = tmp->next;
   if(l->first)l->first->prev = NULL;
   else l->last = NULL;
   free(tmp);
   return val;
}
/******************************************************************************/

void View(dblist l)
{
   elem *pelem = l.first;
   while(pelem)
   {
     printf("%d\n",pelem->value);
     pelem = pelem->next;
   }
}
/******************************************************************************/

void Clear(dblist *l)
{
   elem *tmp;
   elem *pelem = l->first;
   while(pelem)
   {
     tmp = pelem;
     pelem = pelem->next;
     free(tmp);
   }
   l->first = NULL;
   l->last = NULL;
}

Voici un exemple d'utilisation de la liste doublement chaînée que nous venons de construire :

main.c :

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

#include "dblist.h"

int main()
{
        dblist MaListe;

        Init(&MaListe);

        PushFront(&MaListe,10);
        PushBack(&MaListe,20);
        PushBack(&MaListe,40);
        PushFront(&MaListe,50);

        View(MaListe);
        puts("--------------");

        printf("%d\n",PopFront(&MaListe));
        printf("%d\n",PopFront(&MaListe));
        printf("%d\n",PopBack(&MaListe));
        puts("--------------");

        PushBack(&MaListe,30);
        
        printf("%d\n",PopFront(&MaListe));
        printf("%d\n",PopFront(&MaListe));
        puts("--------------");

        Clear(&MaListe);

#ifdef __WIN32__
        system("PAUSE");  /* Pour la console Windows. */
#endif
        return 0;
}

Voici le même exemple mais avec une création dynamique de la variable d'entrée.

main.c :

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

#include "dblist.h"

int main()
{
        dblist *pdbListe = malloc(sizeof(dblist));

        Init(pdbListe);

        PushFront(pdbListe,10);
        PushBack(pdbListe,20);
        PushBack(pdbListe,40);
        PushFront(pdbListe,50);

        View(*pdbListe);
        puts("--------------");

        printf("%d\n",PopFront(pdbListe));
        printf("%d\n",PopFront(pdbListe));
        printf("%d\n",PopBack(pdbListe));
        puts("--------------");

        PushBack(pdbListe,30);
        
        printf("%d\n",PopFront(pdbListe));
        printf("%d\n",PopFront(pdbListe));
        puts("--------------");

        Clear(pdbListe);

        free(pdbListe);

        system("PAUSE");
        return 0;
}

Bonne lecture,
CGi.

Avec la contribution d'Anomaly pour la relecture.