Insertion et suppression dans une liste chaînée

Insertion dans une liste chaînée

L'insertion dans une liste chaînée comporte trois étapes:
  • Créer un maillon.
  • Affecter la valeur à insérer au champ val.
  • Insérer le nouveau bloc dans la liste.

Comment créer un maillon ?

  • Allouer un espace avec la procédure prédéfinie allouer.
  • transmettre le pointeur p à la procédure allouer pour restituer l'adresse.
    • allouer(p):  allouer maillon ou bloc dans une liste chainée

Insertion du maillon en tète


Insertion du maillon en tète

Insertion du maillon ailleurs qu'en tète

Insertion du maillon ailleurs qu'en tète

Procédure inserer(L: listechainée, e: élément, pp: ptr)
début
    allouer(p)
    *p.val := e
    *p.lien := *pp.lien
    *pp.lien := p
fin

Suppression dans une liste chaînée

il suffit d'éliminer le maillon à supprimer en modifiant les champs des adresses du maillon qui pointe vers celui-ci (prédécesseur).

Suppression du maillon en tète





Suppression du maillon ailleurs qu'en tète





Procédure supprimer(L: listechainée, pp: ptr)
début
    p := *pp.lien
    *pp.lien := *p.lien
    restituer(p)
fin