Aller au menu - Aller au contenu

Icône Les listes circulaires doublement chainées en C

Avatar
Par Avatar yoch
Mise à jour : 15/04/2011
Difficulté : Facile Facile Durée d'étude : 2 heures
216 visites depuis 7 jours, classé 406/786
Bonjour,

Vous vous intéressez au structures de données dynamiques en C ?
Vous avez déjà entendu parler des listes doublement chainées, mais vous trouvez la mise en oeuvre trop compliquée ? Ou bien voulez-vous simplement en savoir davantage sur les types de listes existants ?

Je vous présente une autre manière d'implémenter les listes doublement chainées en C : avec des listes circulaires. C'est une manière qui mérite d'être mieux connue, car elle permet d'apporter une plus grande souplesse au code. Qui plus est, le concept de liste circulaire est bon à connaitre en soi, et pourra vous servir un jour...
Retour en haut
Sommaire du tutoriel :
Icône du chapitre
Retour en haut

Présentation

Le principe d'une liste doublement chainée est de garder pour chaque élément de la liste un pointeur sur l'élément précédent et sur l'élément suivant.

Image utilisateur

Cela permet notamment de simplifier l'insertion ou la suppression d'un élément donné, ainsi que le parcours en sens inverse. Cependant, cela introduit aussi une certaine dose de complexité dans le codage, car la liste finit dans les deux sens par un pointeur sur NULL, ce qui nécessite d'ajouter dans le code la gestion de ces cas particuliers.

Imaginez maintenant que l'on ferme la boucle, en faisant pointer le pointeur 'precedent' du premier élément sur le dernier élément, et vice-versa.

Ben la liste devient corrompue, aucun moyen de la parcourir sans faire une boucle infinie !


Très juste, en effet. Alors quoi, je me suis moqué de vous ? Ce tuto se terminerait donc ici ?
Bien sur que non ! :p

Nous allons créer un élément spécial, qui sera la racine de notre liste. Cet élément sera à la fois avant le premier élément et après le dernier. C'est lui qui va nous permettre de manipuler tranquillement la liste sans risquer quoi que ce soit.

Image utilisateur


Bon, je crois que le moment est venu de passer à du concret et vous montrer du code :) .
Retour en haut

Mise en oeuvre (1) : création, parcours et suppression

Définition



La définition de la liste se fait de la manière habituelle, avec une structure :

Code : C
1
2
3
4
5
6
typedef struct _e
{
    int val;            /* données quelconques - ici un entier */
    struct _e* prec;    /* pointeur sur l'élément précédent */
    struct _e* suiv;    /* pointeur sur l'élément suivant */
} Liste_Circulaire_Doublement_Chainee;


Création



Image utilisateur

En revanche, une liste vide n'est plus représentée simplement par NULL.

En effet, pour pouvoir utiliser notre liste, nous devons au préalable la créer, c'est-à-dire créer sa racine. Pour cela, nous ferons :

Code : C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Liste_Circulaire_Doublement_Chainee* creeListe (void)
{
    Liste_Circulaire_Doublement_Chainee* racine = malloc ( sizeof *racine );
    if ( racine != NULL )  /* si la racine a été correctement allouée */
    {
        /* pour l'instant, la liste est vide, 
           donc 'prec' et 'suiv' pointent vers la racine elle-même */
        racine->prec = racine;
        racine->suiv = racine;
    }
    return racine;
}


Parcourir la liste



Pour parcourir la liste, on se sert de sa racine. C'est pourquoi, on doit toujours garder un pointeur sur la racine de la liste.

Ce pointeur sur la racine sert en quelque sorte d' "objet" liste.
Il nous servira à manipuler la liste.

On commence depuis le premier élément après la racine, et on s'arrête lorsque l'on arrive à la racine.

Code : C
1
2
3
4
/* parcours à l'endroit */
Liste_Circulaire_Doublement_Chainee* it;
for ( it = liste->suiv; it != liste; it = it->suiv )
    printf("%d, ", it->val);


Code : C
1
2
3
4
/* parcours à l'envers */
Liste_Circulaire_Doublement_Chainee* rit;
for ( rit = liste->prec; rit != liste; rit = rit->prec )
    printf("%d, ", rit->val);


Vider la liste



Pour vider la liste, c'est le même principe : on parcours la liste et on libère ses éléments.

Code : C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void viderListe (Liste_Circulaire_Doublement_Chainee* liste)
{
    Liste_Circulaire_Doublement_Chainee *it, *next;

    for ( it = liste->suiv; it != liste; it = next )
    {
        next = it->suiv;  /* on enregistre le pointeur sur l'élément suivant avant de supprimer l'élément courant */
        free(it);         /* on supprime l'élément courant */
    }
}


Supprimer la liste



On vide d'abord la liste, puis on supprime la racine. Cette fois ci, il est bon de passer un pointeur sur la racine, pour pouvoir passer la racine à NULL;

Code : C
1
2
3
4
5
void supprimerListe (Liste_Circulaire_Doublement_Chainee** liste)
{
    viderListe( *liste );  /* on vide d'abord la liste */
    free( *liste ), *liste = NULL;
}


Retour en haut

Mise en oeuvre (2) : opérations sur la liste

Ajout d'éléments



Un petit aperçu en image d'une insertion dans une liste circulaire doublement chainée :

Image utilisateur


Dés à présent, vous allez comprendre tout l'intérêt de cette methode :) .

Ajouter avant / après un élément



On commence par ces opérations, car elles vont nous servir pour implémenter l'ajout en tête et en queue.

Code : C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void ajouterAvant (Liste_Circulaire_Doublement_Chainee* element, int val)
{
    Liste_Circulaire_Doublement_Chainee* nouvel_element = malloc ( sizeof *nouvel_element );
    if ( nouvel_element != NULL )
    {
        nouvel_element->val = val;
        /* on définit les pointeurs du nouvel élément */
        nouvel_element->prec = element->prec;
        nouvel_element->suiv = element;
        /* on modifie les éléments de la liste */
        element->prec->suiv = nouvel_element;
        element->prec = nouvel_element;
    }
}


Code : C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void ajouterApres (Liste_Circulaire_Doublement_Chainee* element, int val)
{
    Liste_Circulaire_Doublement_Chainee* nouvel_element = malloc ( sizeof *nouvel_element );
    if ( nouvel_element != NULL )
    {
        nouvel_element->val = val;
        /* on définit les pointeurs du nouvel élément */
        nouvel_element->prec = element;
        nouvel_element->suiv = element->suiv;
        /* on modifie les éléments de la liste */
        element->suiv->prec = nouvel_element;
        element->suiv = nouvel_element;
    }
}


Comme vous pouvez le constater, le code est ici très concis. On ne s'amuse pas à faire tout une batterie de tests.

Bien entendu, cela demande tout de même une certaine rigueur de votre part : il suffit que la liste passée en paramètre ne soit pas formée correctement pour que votre programme plante. C'est pourquoi, il est hautement recommandé de toujours utiliser les fonctions dédiées pour manipuler ce type de liste.


Ajout en tête / queue



A présent, pour ajouter un élément en début ou en fin de liste, rien de plus simple : nous allons nous servir de la racine. L'élément qui précède la racine est le dernier élément de la liste, et l'élément suivant la racine est le premier.

Code : C
1
2
3
4
void ajouterEnTete (Liste_Circulaire_Doublement_Chainee* racine, int val)
{
    ajouterApres (racine, val);
}


Code : C
1
2
3
4
void ajouterEnQueue (Liste_Circulaire_Doublement_Chainee* racine, int val)
{
    ajouterAvant (racine, val);
}


Suppression d'éléments



La suppression d'éléments est encore plus simple, puisque chaque élément connait le précédent et le suivant, et que la racine existe toujours :

Image utilisateur


Supprimer un élément



Code : C
1
2
3
4
5
6
7
void supprimerElement (Liste_Circulaire_Doublement_Chainee* element)
{
    element->prec->suiv = element->suiv;
    element->suiv->prec = element->prec;
    /* on libère la mémoire allouée */
    free(element);
}


Supprimer la tête / queue



Comme d'habitude, on utilise la racine. Attention seulement à vérifier que l'élément existe bien.

Code : C
1
2
3
4
5
void supprimerPremierElement (Liste_Circulaire_Doublement_Chainee* racine)
{
    if (racine->suiv != racine)
        supprimerElement (racine->suiv);
}


Code : C
1
2
3
4
5
void supprimerDernierElement (Liste_Circulaire_Doublement_Chainee* racine)
{
    if (racine->prec != racine)
        supprimerElement (racine->prec);
}


Accès aux éléments



Accéder au premier / dernier élément



Ici, on accède aux éléments sans les enlever de la liste :

Code : C
1
2
3
4
5
6
7
Liste_Circulaire_Doublement_Chainee* premierElement (Liste_Circulaire_Doublement_Chainee* racine)
{
    if (racine->suiv != racine)  /* on vérifie que l'élément existe bien */
        return racine->suiv;
    else                         /* sinon on retourne NULL */
        return NULL;
}


Code : C
1
2
3
4
5
6
7
Liste_Circulaire_Doublement_Chainee* dernierElement (Liste_Circulaire_Doublement_Chainee* racine)
{
    if (racine->prec != racine)  /* on vérifie que l'élément existe bien */
        return racine->prec;
    else                         /* sinon on retourne NULL */
        return NULL;
}
Retour en haut

Remarques

Opérations avancées



Il existe d'autres opérations courantes sur les listes.

Insertion d'une liste d'éléments



Pour l'insertion d'une autre liste ou sous-liste dans la liste, le principe est plus ou moins le même que l'insertion d'un élément. Il suffit de fournir l'élément avant (ou après) lequel placer la sous-liste, ainsi que le premier et le dernier élément de ladite sous-liste. Visuellement, l'opération ressemble à ceci :

Image utilisateur


Je vous laisse coder cela. :)

Tri



Le tri n'est pas une opération sur liste à proprement parler. Néanmoins, il est moins simple de trier une liste qu'un tableau en C, car impossible d'utiliser qsort().

A vous de choisir un algorithme efficace (le tri fusion est assez adapté aux listes) et de l'écrire si vous avez besoin d'une telle fonction.

Nombre d'éléments



On peut remarquer l'absence de possibilité de connaitre efficacement la taille de la liste. Selon l'implémentation proposée dans ce tuto, la fonction nombreElements() devra être codée comme suit :

Code : C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
size_t nombreElements (Liste_Circulaire_Doublement_Chainee* liste)
{
    size_t n = 0;
    Liste_Circulaire_Doublement_Chainee* it;

    for ( it = liste->suiv; it != liste; it = it->suiv )
        n++;

    return n;
}


Ce code n'est pas performant, car pour connaitre le nombre d'éléments présents dans la liste, on doit la parcourir tous ses éléments. Cette limitation peut devenir gênante selon les cas d'utilisation.

Pour stocker proprement la taille de la liste, il vaut mieux encapsuler cette dernière comme ceci :

Encapsulation



Code : C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
typedef struct _e
{
    int val;            /* données */
    struct _e* prec;    /* pointeur sur l'élément précédent */
    struct _e* suiv;    /* pointeur sur l'élément suivant */
} _elem;

typedef struct
{
    _elem *racine;      /* pointeur sur la racine de la liste */
    size_t nb_elements; /* nombre d'éléments dans la liste */
} Liste_Circulaire_Doublement_Chainee;


La structure Liste_Circulaire_Doublement_Chainee contient à présent l'élément racine et le nombre d'éléments présents dans la liste. Il nous faudra donc modifier le prototype des fonctions en conséquence.

La fonction creeListe devra initialiser le nombre d'éléments a zéro, et les fonction de modification (ajout/suppression d'éléments) devront respectivement incrémenter ou décrémenter le nombre d'éléments de la liste. Dés lors, toutes les fonctions permettant de modifier la liste doivent recevoir un pointeur sur la structure Liste_Circulaire_Doublement_Chainee...

L'ennui majeur avec ce type de methode, c'est que l'insertion d'un segment de liste dans une autre liste perd en performances : on doit parcourir pour connaitre le nombre d'éléments ajoutés.

Retour des fonctions



Une fonction modifiant un objet est dite "destructive". Les fonctions de modification de liste proposées ci-dessus sont toutes destructives, en accord avec la philosophie du langage C. C'est pourquoi le type de retour est void.

Il est tout à fait possible d'écrire des versions non-destructives de ces fonctions, c.a.d que la fonction renvoie une copie modifiée de la liste sans altérer la liste originale. Dans ce cas, les fonctions renverront une liste.

Optimisation



La réutilisation des fonctions existantes est une bonne idée d'un point de vue lisibilité, mais pas d'un point de vue des performances. Si le code est appelé a être le plus performant possible, il vaut mieux ne pas imbriquer les fonctions.

Utilité



Enfin, l'un des avantages de ce type de liste, mis à part la simplicité d'implémentation, est de pouvoir momentanément supprimer un élément de la liste sans l'effacer, pour le restaurer ensuite à la même place (le cacher en quelque sorte). Cette opération, qui exige que la liste ne soit pas modifiée entre temps, se justifie dans certains algorithme que je n'aborderai pas ici, mais sachez qu'elle existe :

Code : C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void cacherElement (Liste_Circulaire_Doublement_Chainee* element)
{
    element->prec->suiv = element->suiv;
    element->suiv->prec = element->prec;
}

void restaurerElement(Liste_Circulaire_Doublement_Chainee* element)
{
    element->prec->suiv = element;
    element->suiv->prec = element;
}
Retour en haut
Si vous avez fait du C++, vous vous êtes peut-être aperçus d'une certaine similitude entre le code proposé ici et le conteneur <list> de la STL.

C'est normal :) : je m'en suis quelque peu inspiré, pour la bonne raison que la classe <list> proposée par la STL implémente elle aussi les listes doublement chainées. D'autre part, le fait d'utiliser un noeud racine pour manipuler la liste m'a intuitivement orienté vers une approche plus "objet".

En conclusion, retenez tout de même que listes circulaires et listes doublement chainées sont deux notions indépendantes : on peut utiliser des listes circulaires simplement chainées, tout comme des listes doublement chainées qui ne seraient pas circulaires. Mais je trouve que ces deux notions se marient fort bien ensemble.
Retour en haut

Partager

Retour en haut
5 commentaires pour "Les listes circulaires doublement chainées en C"
Note moyenne : 3.80 / 4 (5 votes)
Pseudo Commentaire
Hors ligne i00k # Posté le 15/04/2011 à 08:41:11
Waboooooow
Avatar

Ville : Sèvres
Pays : France métropolitaine

 Le tuto est mieux que sa version bêta, pas mal d'explication ont été rajoutées.
Jeux flash en ligne - Crocojeux.com !
 
Hors ligne Nathalya # Posté le 15/04/2011 à 17:16:52
10+1=11
Avatar
Validateurs

Ville : Flaxlanden
Pays : France métropolitaine
Études : ESEO Angers Dijon Paris

 Le tuto n'indique pas l'utilité de faire un chainage circulaire. Pour être honnête, je n'en vois pas. Je n'ai jamais eu à faire varier la taille d'un buffer circulaire. D'ailleurs, dans les exemples montrés, la circularité n'est jamais utilisée. En fait il s'agit juste d'une astuce pour que la tête et la queue de la liste connaissent le descripteur de la liste, avec une implémentation telle que les opérations en début et en fin de liste sont identiques aux opération en milieu de liste. Bref c'est une implémentation élégante de liste doublement chaînée, mais sans plus.
Do only what only you can do.
 
Hors ligne yoch # Posté le 15/04/2011 à 17:27:13
Avatar

 Citation : Nathalya
Le tuto n'indique pas l'utilité de faire un chainage circulaire.

Pas explicitement, car l'exemple que j'ai en tête est trop spécialisé, mais je fais le point sur l'utilité de la circularité dans les remarques.
Pour un exemple concret d'utilisation, voir ce papier.

Citation : Nathalya
Pour être honnête, je n'en vois pas. [...] D'ailleurs, dans les exemples montrés, la circularité n'est jamais utilisée. En fait il s'agit juste d'une astuce pour que la tête et la queue de la liste connaissent le descripteur de la liste, avec une implémentation telle que les opérations en début et en fin de liste sont identiques aux opération en milieu de liste. Bref c'est une implémentation élégante de liste doublement chaînée, mais sans plus.

Oui, c'est bien l'objet principal du tuto.
Comprendre la messagerie électronique
Introduction à la programmation dynamique
Le backtracking par l'exemple : résoudre un sudoku
Bloquer du contenu avec le fichier hosts - La commande sed
Modifier une application Windows
 
Hors ligne Maëlan # Posté le 14/06/2011 à 19:39:09
Avatar

 Citation
L'ennui majeur avec ce type de methode, c'est que l'insertion d'un segment de liste dans une autre liste perd en performances : on doit parcourir pour connaitre le nombre d'éléments ajoutés.
Je ne comprends pas bien cette phrase. Parcourir quelle liste, celle à ajouter ou celle à agrandir ? Et pourquoi, vu que le nombre d'élément est indiqué dans la structure d'encapsulation ?

Citation
Enfin, l'un des avantages de ce type de liste, mis à part la simplicité d'implémentation, est de pouvoir momentanément supprimer un élément de la liste sans l'effacer, pour le restaurer ensuite à la même place (le cacher en quelque sorte). Cette opération, qui exige que la liste ne soit pas modifiée entre temps, se justifie dans certains algorithme que je n'aborderai pas ici, mais sachez qu'elle existe :
Si on cache ou restaure un élément, le nombre d'élément indiqué dans la structure d'encapsulation ne sera pas mis à jour, à moins de passer en plus un pointeur vers cette structure…


ÉDIT @ yoch : Merci pour les explications :)
© Message rédigé sous la seule propriété intellectuelle de son auteur Maëlan, et protégé contre toute reproduction partielle ou totale par l’ACTA (je vous remercie).
Logo de Xubuntu

Ne pas passer la main à travers l’enclos des loups.
Ne pas nourrir les lamas.
Ne pas utiliser de flash pour photographier les poneys.
Ne pas se moquer des manchots.

Un alias bien pratique : alias Taurre='cat http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf | grep TOPIC'. À ceux qui comprendront. ;)
 
Hors ligne yoch # Posté le 15/06/2011 à 08:57:03
Avatar

 Citation : Maelan44
Citation
L'ennui majeur avec ce type de methode, c'est que l'insertion d'un segment de liste dans une autre liste perd en performances : on doit parcourir pour connaitre le nombre d'éléments ajoutés.
Je ne comprends pas bien cette phrase. Parcourir quelle liste, celle à ajouter ou celle à agrandir ? Et pourquoi, vu que le nombre d'élément est indiqué dans la structure d'encapsulation ?

Celle à ajouter. Et oui, si on ajoute une liste entière, pas de problème. Je parle ici d'un segment de liste.

Typiquement, si tu connais le C++, cette fonction de la STL :
Code : C++
1
void splice ( iterator position, list<T,Allocator>& x, iterator first, iterator last );

n'aura pas la même complexité suivant les implémentations (cf. cette discussion).

Citation : Maelan44
Citation
Enfin, l'un des avantages de ce type de liste, mis à part la simplicité d'implémentation, est de pouvoir momentanément supprimer un élément de la liste sans l'effacer, pour le restaurer ensuite à la même place (le cacher en quelque sorte). Cette opération, qui exige que la liste ne soit pas modifiée entre temps, se justifie dans certains algorithme que je n'aborderai pas ici, mais sachez qu'elle existe :
Si on cache ou restaure un élément, le nombre d'élément indiqué dans la structure d'encapsulation ne sera pas mis à jour, à moins de passer en plus un pointeur vers cette structure…

Tu as raison. Je parle ici du premier type de liste (sans encapsulation et qui ne connait donc pas son nombre d'éléments). Je devrais effectivement être plus clair.
Comprendre la messagerie électronique
Introduction à la programmation dynamique
Le backtracking par l'exemple : résoudre un sudoku
Bloquer du contenu avec le fichier hosts - La commande sed
Modifier une application Windows
 

Voir tous les commentaires