Chapitre 11 : Les Listes doublement chaînées
1 Introduction 2 Définition
Les listes doublement chaînées sont des structures de données
Les listes doublement chaînées peuvent être utilisées quand
semblables aux listes simplement chaînées. En revanche, par
plusieurs opérations d'insertion/suppression d'éléments sont rapport à ces dernières la liaison entre les éléments se fait grâce
nécessaires. Elles permettent donc à deux pointeurs (un qui pointe vers l'élément précédent et un
• de gagner en complexité sur l'insertion et la suppression qui pointe vers l'élément suivant).
par rapport à la liste simplement chaînée,
• un parcours des éléments à l'envers.
Mais, elles utilisent un pointeur supplémentaire par élément. Il faut
donc maintenir cohérent deux fois plus de variables que dans
une liste simplement chaînée
1 2
2 Définition 3 Déclaration
Le pointeur précédent du premier élément doit pointer vers NIL L'élément de la liste contiendra un champ donnée, un pointeur
(le début de la liste). Le pointeur suivant du dernier élément doit précédent et un pointeur suivant.
pointer vers NIL (la fin de la liste).
Pour accéder à un élément, la liste peut être parcourue dans les ELEMENT = structure
précédent : pointeur sur ELEMENT
deux sens :
donnée: entier
• en commençant avec la tête, le pointeur suivant permettant le suivant : pointeur sur ELEMENT
déplacement vers le prochain élément. FinStructure
• en commençant avec la queue, le pointeur précédent permettant
le déplacement vers l'élément précédent. Pour avoir le contrôle de la liste, il est préférable de sauvegarder
certains éléments : le premier élément et le dernier élément.
Le déplacement se fait dans les deux directions, du premier vers le
dernier élément et/ou du dernier vers le premier élément. 3 4
, 3 Déclaration 4 Opérations sur les listes doubles
Pour réaliser cela, une autre structure sera utilisée A. Initialisation
Cette opération doit être faite avant toute autre opération sur la
liste = Structure liste. Elle initialise le pointeur début et le pointeur fin avec le
début: pointeur sur ELEMENT pointeur NIL.
fin : pointeur sur ELEMENT
FinStructure Procédure initialisation (Var L: pointeur sur liste )
Début
Quelque soit la position dans la liste, les pointeurs début et fin L^.debut ← NIL
pointent toujours respectivement vers le 1er et le dernier élément L ^.fin ← NIL
de la liste. fin
5 6
4 Opérations sur les listes doubles 4 Opérations sur les listes doubles
B. Affichage de la liste
Pour afficher la liste entière, nous pouvons nous positionner au début /* affichage en avançant */
de la liste ou à la fin de la liste (le pointeur début ou fin le
permettra). Procédure affiche(l: pointeur sur liste)
Ensuite, en utilisant le pointeur suivant ou précédent de chaque Variable
élément la liste est parcourue du 1 er vers le dernier élément ou du courant: pointeur sur element
dernier vers le 1er élément. Début
courant ← l ^. debut /* point du départ le 1 er élément */
La condition d'arrêt est donnée par le pointeur suivant du dernier Tant que (courant <> NIL) faire
élément qui vaut NIL dans le cas de la lecture du début vers la fin de écrire(courant^.donnee)
liste, ou par le pointeur précédent du 1er élément qui vaut NIL, dans courant ← courant ^. suivant
le cas d'une lecture de la fin vers le début de la liste. finTQ
fin
7 8
1 Introduction 2 Définition
Les listes doublement chaînées sont des structures de données
Les listes doublement chaînées peuvent être utilisées quand
semblables aux listes simplement chaînées. En revanche, par
plusieurs opérations d'insertion/suppression d'éléments sont rapport à ces dernières la liaison entre les éléments se fait grâce
nécessaires. Elles permettent donc à deux pointeurs (un qui pointe vers l'élément précédent et un
• de gagner en complexité sur l'insertion et la suppression qui pointe vers l'élément suivant).
par rapport à la liste simplement chaînée,
• un parcours des éléments à l'envers.
Mais, elles utilisent un pointeur supplémentaire par élément. Il faut
donc maintenir cohérent deux fois plus de variables que dans
une liste simplement chaînée
1 2
2 Définition 3 Déclaration
Le pointeur précédent du premier élément doit pointer vers NIL L'élément de la liste contiendra un champ donnée, un pointeur
(le début de la liste). Le pointeur suivant du dernier élément doit précédent et un pointeur suivant.
pointer vers NIL (la fin de la liste).
Pour accéder à un élément, la liste peut être parcourue dans les ELEMENT = structure
précédent : pointeur sur ELEMENT
deux sens :
donnée: entier
• en commençant avec la tête, le pointeur suivant permettant le suivant : pointeur sur ELEMENT
déplacement vers le prochain élément. FinStructure
• en commençant avec la queue, le pointeur précédent permettant
le déplacement vers l'élément précédent. Pour avoir le contrôle de la liste, il est préférable de sauvegarder
certains éléments : le premier élément et le dernier élément.
Le déplacement se fait dans les deux directions, du premier vers le
dernier élément et/ou du dernier vers le premier élément. 3 4
, 3 Déclaration 4 Opérations sur les listes doubles
Pour réaliser cela, une autre structure sera utilisée A. Initialisation
Cette opération doit être faite avant toute autre opération sur la
liste = Structure liste. Elle initialise le pointeur début et le pointeur fin avec le
début: pointeur sur ELEMENT pointeur NIL.
fin : pointeur sur ELEMENT
FinStructure Procédure initialisation (Var L: pointeur sur liste )
Début
Quelque soit la position dans la liste, les pointeurs début et fin L^.debut ← NIL
pointent toujours respectivement vers le 1er et le dernier élément L ^.fin ← NIL
de la liste. fin
5 6
4 Opérations sur les listes doubles 4 Opérations sur les listes doubles
B. Affichage de la liste
Pour afficher la liste entière, nous pouvons nous positionner au début /* affichage en avançant */
de la liste ou à la fin de la liste (le pointeur début ou fin le
permettra). Procédure affiche(l: pointeur sur liste)
Ensuite, en utilisant le pointeur suivant ou précédent de chaque Variable
élément la liste est parcourue du 1 er vers le dernier élément ou du courant: pointeur sur element
dernier vers le 1er élément. Début
courant ← l ^. debut /* point du départ le 1 er élément */
La condition d'arrêt est donnée par le pointeur suivant du dernier Tant que (courant <> NIL) faire
élément qui vaut NIL dans le cas de la lecture du début vers la fin de écrire(courant^.donnee)
liste, ou par le pointeur précédent du 1er élément qui vaut NIL, dans courant ← courant ^. suivant
le cas d'une lecture de la fin vers le début de la liste. finTQ
fin
7 8
