Les listes doublements chaînées

Parent Category: Informatique et réseaux Category: Algorithme

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.

 
 

24


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

 
 

25
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

 
 

26
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

 
 

27
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

 
 

28
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

 
 

29
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

 
 

30
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