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.
| 
