Principe de fonctionnement

Une liste doublement chaînée circulaire est une structure où chaque élément possède deux références : une vers l'élément précédent et une vers l'élément suivant. La particularité réside dans le fait que le dernier élément pointe vers le premier, et vice versa, formant ainsi une boucle.

Structure du nœud

Chaque nœud encapsule trois composants essentiels :

• Une référence vers le nœud antérieur
• La valeur stockée
• Une référence vers le nœud postérieur

class Cellule<V> {
    V valeur;
    Cellule<V> precedent, suivant;
    
    Cellule(V valeur) {
        this.valeur = valeur;
    }
}

Initialisation et insertion

Lors de la création d'une liste vide, la référence de tête est nulle. L'insertion du premier élément établit une boucle où le nœud pointe vers lui-même dans les deux directions. Les insertions ultérieures s'effectuant toujours en tête de liste, en réorganisant les liens pour préserver la circularité.

La séquence d'insertion suit cette logique :

1. Instanciation d'une nouvelle cellule
2. Connexion de son successeur vers l'ancien premier élément
3. Mise à jour du prédécesseur de l'ancien premier élément
4. Établissement du lien retour vers la tête
5. Déplacement de la référence de tête

Implémentation complète

public class ListeCirculaire<E> {
    private Cellule<E> curseur;
    private int taille;
    
    public void inserer(E element) {
        if (element == null) return;
        
        Cellule<E> nouvelle = new Cellule<>(element);
        
        if (curseur == null) {
            nouvelle.precedent = nouvelle.suivant = nouvelle;
            curseur = nouvelle;
        } else {
            nouvelle.suivant = curseur.suivant;
            nouvelle.precedent = curseur;
            curseur.suivant.precedent = nouvelle;
            curseur.suivant = nouvelle;
            curseur = nouvelle;
        }
        taille++;
    }
    
    public E recuperer(int position) {
        if (position < 0 || position >= taille) {
            return null;
        }
        Cellule<E> iterateur = curseur;
        int decalage = position;
        while (decalage-- > 0) {
            iterateur = iterateur.suivant;
        }
        return iterateur.valeur;
    }
    
    public E retirerTete() {
        if (taille == 0) return null;
        
        Cellule<E> aSupprimer = curseur.suivant;
        aSupprimer.suivant.precedent = curseur;
        curseur.suivant = aSupprimer.suivant;
        
        aSupprimer.precedent = aSupprimer.suivant = null;
        taille--;
        
        if (taille == 0) curseur = null;
        return aSupprimer.valeur;
    }
    
    public E retirer(E cible) {
        if (cible == null || taille == 0) return null;
        
        Cellule<E> explorateur = curseur;
        int iterations = taille;
        
        while (iterations-- > 0) {
            if (explorateur.valeur.equals(cible)) break;
            explorateur = explorateur.suivant;
        }
        
        if (!explorateur.valeur.equals(cible)) return null;
        
        explorateur.precedent.suivant = explorateur.suivant;
        explorateur.suivant.precedent = explorateur.precedent;
        
        if (explorateur == curseur) curseur = explorateur.suivant;
        
        E resultat = explorateur.valeur;
        explorateur.precedent = explorateur.suivant = null;
        taille--;
        
        if (taille == 0) curseur = null;
        return resultat;
    }
    
    public int longueur() {
        return taille;
    }
}

Complexité algorithmique

Cette structure s'avère particulièrement efficace pour les applications nécessitant des insertions et suppressions fréquentes aux extrémités, tout en permettant un parcours bidirectionnel.