Les listes chaînées

Parent Category: Informatique et réseaux Category: Algorithme
 

 


Suppression d'un élément dans une liste chaînée

 

Utilisons la fonction libérer (en Pascal = dispose) pour libérer un emplacement occupé en mémoire.

Remarque:

  • La fonction "libérer" ne libère pas un emplacement nil et il libère une seule cellule à la fois.
  • La fonction "libérer" ne libère qu'une seule cellule de la liste et non de la liste tout entière.

Suppression en tête de liste

 

Il s'agit de retirer l'élément en tête de la liste si la liste est vide, on ne retire aucun élément et on envoye un message correspondant

procédure supp_tete(tete: Ptr)
var P: Ptr
P ← tete
si tete=nil alors
écrire('pas de suppression')
sinon
tete ← tete^.suivant
liberer(P)
fin si
fin

 

Suppression d'un élément P de la liste

 

Pour supprimer un élément P de la liste, parcourir la liste chaînée du début de la liste jusqu'au précédent de la cellule P, ensuite pointer le suivant du précédent de P ou suivant de P. Enfin libérer la cellule P. La procédure correspondante est:

procédure supp_p(tête, P: Ptr)
var P1: Ptr
début
si tete≠nil alors
P1 ← tete
tant que P1^.suivant#P faire
P1 ← P1^.suivant
fin tant que
P1^.suivant ← P^.suivant
liberer(P)
fin si
fin

 

Suppression en fin de liste

 

Pour supprimer un élément en fin de liste, il faut maintenir un pointeur à l'avant dernière cellule, ensuite libérer la dernière cellule et enfin mettre le suivant de l'avant dernière cellule à nil. La procédure correspondante est la suivante.

Procédure Supp_fin(tete: Ptr)
var P, P1: Ptr
début
P1 ← tete
P ← P1^.suivant
tant que P^.suivant≠nil faire
P1 ← P1^.suvant
P ← P^.suivant
fin tant que
P^.suivant ← nil
liberer(P)
fin