Généralités
Encore appelée liste symétrique, une liste doublement chaînée est une liste dans laquelle chaque élément de la liste a deux pointeurs, l'un pointant sur son suivant et l'autre sur son précédent. La tête d'une liste doublement chaînée à son précédent qui pointe à nil, tandis que la queue à son suivant qui pointe à nil.
Déclaration d'une liste doublement chaînée
type pointeur double = ^liste double
liste double = enregistrement
info: type élément
suivant, précédent: pointeur double
fin enregstrement
type PtrD = ^listeD
listeD = enregistrement
info : entier
suiv, prec: PtrD
fin enregistrement
Création d'une liste doublement chaînée
Procédure creer_cellule(tete: PtrD)
var a: entier
début
nouveau(tete)
lire(a)
tete^.info ← a
tete^.prec ← nil
tete^.suiv ← nil
fin
Ajout d'un élément dans une liste doublement chaînée
Ajout en tete
procédure ajout_tete(tete: PtrD, val: entier)
var P: PtrD
début
nouveau(P)
P^.info ← val
P^.prec ← nil
P^.suiv ← tete
tete^.prec ← P
tete ← P
fin
Ajout avant P
procédure ajout_avant_P(tete: PtrD, val: entier)
debut
P1 ← tete
tant que P1≠P faire
P1 ← P1^.suiv
fin tnat que
nouveau(P2)
P2^.info ←- val
P2^.suiv ← P
P2^.prec ← P^.prec
P^.prec^.suiv ← P2
P^.prev ← P2
fin
Ajout en fin de liste
procédure ins_fin(tete: Ptr, val: entier)
var P: PtrD
début
P ← tete
tant que P^.suivant ≠ nil faire
P ← P^.suivant
fin tanty que
nouveau(P1)
P1^.info ← val
P1^.prec ← P
P1^.suivant ← nil
P^.suivant ←- P1
fin
Suppression d'un élément dans une liste symétrique
Suppression en tête
procédure sup_tete(tete: PtrD)
var P: PtrD
début
P ← tete
si tete#nil alors
tete ← tete^.suivant
tete^.prec ← nil
liberer(P)
fin si
fin
Suppression à la position P
Procédure Supp_P(tete: Ptr)
var P, P1: PtrD
début
P1 ← tete
tant que P1^.suivant≠P faire
P1 ← P1^.suivant
fin tant que
P1^.suivant ← P^.suivant
P^.suivant^.prec ← P1
librerer(P)
fin
Suppression en queue
procédure Sup_queue(tete: PtrD)
var P1: PtrD
début
P1 ← tete
tant que P1^.suivant ≠ nil faire
P1 ← P1^.suivant
fin tant que
P1^.prec^.suivant ← nil
liberer(P1)
fin