Algorithme - Listes circulaires et doublement chaînées

Qu'est-ce qu'une liste circulaire ?

Dans le dernier nœud de la liste, le champ lien contient null, une valeur qui indique la fin. Une liste circulaire consiste à faire pointer vers le premier nœud de la liste. Elle est dit ouverte ou linéaire succ(queue)=tête.

Définition de la liste circulaire par un pointeur

liste circulaire par un pointeur

1) Parcourir la liste

Procédure parcours(L : ptr , p : ptr)
var pp:ptr
début
    pp := p
    répeter
          traiter (*pp.val)
          pp := *pp.lien
    jusqu'à (pp=p)
fin

2) Insertion

Insertion en tête

Insertion en tête

Insertion ailleurs qu'en tête

Insertion ailleurs qu'en tête

Voir:
Insertion d'un élément dans une liste chaînée.

3) Suppression

Voir: suppression d'un élément dans une liste chaînée.

Avantages et inconvénients

• Le parcours n'a pas de cas particulier.
• Trois cas pour l'insertion:
• En tête (liste vide).
• En tête (liste non vide).
• Ailleurs qu'en tête.
• Trois cas pour la suppression;
• En tête (liste à un élément).
• En tête (liste à plus d'une élément).
• Ailleurs qu'en tête

Définition de la liste circulaire par un maillon

• Le parcours se fait à partir du maillon courant qui le sentinelle.
• L'insertion n'a pas de cas particulier.
• Il faut s'assurer que le maillon à supprimer n'est pas le sentinelle.