Developpez.com - C
X

Choisissez d'abord la catégorieensuite la rubrique :



Les listes chaînées en C.

Par CGi

Le 5 avril 2005


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(EXIT_FAILURE);
   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(EXIT_FAILURE);
   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

dblist.c :
#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(EXIT_FAILURE);
   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(EXIT_FAILURE);
   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);

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




Bonne lecture,
CGi.

Avec la contribution d'Anomaly pour la relecture.





LISTES CHAÎNÉES
  Liste simple.   Liste triée.   Liste double.


C/C++
  Les pointeurs du C/C++.   Les listes chaînées.             Liste simple.             Liste triée.             Liste double.   Les arbres.   Les tas.   Le C orienté objets ?

  1 - La fenêtre principale.   2 - Contrôles et messages.   3 - Les commandes.   4 - Dialogue std.   5 - Contexte de périph.   6 - Dessiner.   7 - Les ressources.   8 - Dialogue perso.   9 - Dialogue comm.   10 - Les accélérateurs.

Assembleur
  Assembleur sous Visual C++.

C++ BUILDER
  Trucs et astuces.   Composant.   TRichEdit.   TDrawGrid.   Application MDI.   TThread.   wxWidgets.   Style Win XP.

  Première application.   Construire un menu.   Dessiner.   Sisers, Timers...   Dialogues standards.   Dialogues perso.

DotNet
  Composant C# Builder.   Contrôle WinForm.   Application MDI.

Java
  Applet java.





Copyright 2002-2016 CGi - Tous droits réservés CGi. Toutes reproduction, utilisation ou diffusion de ce document par quelque moyen que ce soit autre que pour un usage personnel doit faire l'objet d'une autorisation écrite de la part de l'auteur, propriétaire des droits intellectuels.
Les codes sources de ce document sont fournis en l'état. L'utilisateur les utilise à ses risques et périls, sans garantie d'aucune sorte de la part de l'auteur. L'auteur n'est responsable d'aucun dommage subi par l'utilisateur pouvant résulter de l'utilisation ou de la distribution des codes sources de ce document.
De la même façon, l'auteur n'est en aucun cas responsable d'une quelconque perte de revenus ou de profits, ou de données, ou de tous dommages directs ou indirects, susceptibles de survenir du fait de l'utilisation des codes sources de ce document, quand bien même l'auteur aurait été averti de la possibilité de tels dommages. L'utilisation des codes sources de ce document vaut acceptation par l'utilisateur des termes de la licence ci-dessus.

Contacter le responsable de la rubrique C