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
P₁ ← tete
tant que P₁≠P faire
P₁ ← P₁^.suiv
fin tnat que
nouveau(P₂)
P₂^.info ←- val
P₂^.suiv ← P
P₂^.prec ← P^.prec
P^.prec^.suiv ← P₂
P^.prev ← P₂
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(P₁)
P₁^.info ← val
P₁^.prec ← P
P₁^.suivant ← nil
P^.suivant ←- P₁
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, P₁: PtrD
début
P₁ ← tete
tant que P₁^.suivant≠P faire
P₁ ← P₁^.suivant
fin tant que
P₁^.suivant ← P^.suivant
P^.suivant^.prec ← P₁
librerer(P)
fin

Suppression en queue

procédure Sup_queue(tete: PtrD)
var P₁: PtrD
début
P₁ ← tete
tant que P₁^.suivant ≠ nil faire
P₁ ← P₁^.suivant
fin tant que
P₁^.prec^.suivant ← nil
liberer(P₁)
fin