La classe CircularLinkedList permet de représenter une liste sous forme de structure chaînée circulaire. La classe Node associée représente un nœud dans cette structure. L'implémentation de la classe CircularLinkedList ainsi que celle de sa classe Node sont fournies ci-dessous. (Ces implémentations sont adaptées de celles utilisées dans le syllabus.) Certaines méthodes de la classe CircularLinkedList sont déjà implémentées, mais leur contenu est volontairement caché.

Dans une liste circulaire, le dernier nœud ne pointe pas vers None mais vers le premier nœud de la liste, ce qui forme une boucle.

Il vous est demandé d'implémenter une méthode contains(self, value) dans la classe CircularLinkedList. Cette méthode doit retourner True si la valeur donnée est présente dans l'un des nœuds de la liste, et False sinon.

Voici le code de la classe Node. Vous ne devez et pouvez pas changer cette classe Node :

class Node:
    """ Représente un noeud dans une structure de liste chaînée. """

    def __init__(self, value=None, next=None):
        """
        Crée un nouvel objet Node.
        @pre :  value est une valeur quelconque.
                next est soit None, soit un autre objet de la classe Node
        @post : Un nouvel objet Node a été initialisé.
                Le noeud contient une valeur valueet une référence vers un autre noeud next.
                Si aucune valeur ni référence n’est donnée, elles valent None.
        """
        self.__value = value
        self.__next  = next

    def value(self):
        """
        @pre :  self est un objet de la classe Node, correctement initialisé.
        @post : Retourne la valeur contenue dans ce noeud,
                ou None si aucune valeur n’a été définie.
        """
        return self.__value

    def set_value(self, value):
        """
        @pre :  value est une valeur quelconque.
        @post : La valeur de ce noeud est mise à jour avec la nouvelle valeur value.
        """
        self.__value = value

    def next(self):
        """
        @pre :  self est un objet de la classe Node, correctement initialisé.
        @post : Retourne le noeud suivant référencé par ce noeud,
                ou None s’il n’y a pas de noeud suivant.
        """
        return self.__next

    def set_next(self,node):
        """
        @pre : node est soit un objet de la classe Node soit None.
        @post : Ce noeud pointe désormais vers le noeud node donné.
        """
        self.__next = node

    def __str__(self):
        """
        @pre :  self est un objet de la classe Node, correctement initialisé.
        @post : Retourne une représentation textuelle de la valeur contenue dans ce noeud.
        """
        return str(self.value())

    def __eq__(self,other):
        """
        @pre : other est un objet de la classe Node ou None.
        @post : Retourne True si les deux noeuds contiennent la même valeur,
                False sinon.
        """
        if other is not None and isinstance(other, Node):
            return self.value() == other.value()
        return False

Voici le code de la classe CircularLinkedList :

class CircularLinkedList :
    """ Représente une liste chaînée circulaire. """

    def __init__(self):
        """
        Initialise une nouvelle liste chaînée circulaire.
        @pre : -
        @post : Une nouvelle liste vide est créée.
                Elle ne contient aucun noeud, et l’attribut head vaut None.
        """
        self.head = None

    def add(self, value):
        """
        Ajoute un nouveau noeud contenant la valeur value donnée à la fin de la liste.
        @pre : -
        @post : Un nouveau noeud est créé avec la valeur donnée.
                Ce noeud est placé à la fin de la liste et pointe vers le premier noeud de la liste.
                Si la liste était vide, le noeud pointe vers lui-même.
        """
        # IMPLEMENTATION CACHEE #

    def contains(self, value):
        """
        Vérifie si une valeur value donnée se trouve dans la liste.
        @pre : -
        @post : Retourne True si un des noeuds de la liste contient la valeur donnée,
                False sinon.
        """
        # A COMPLETER #

    def __str__(self):
        """
        @pre : -
        @post : Retourne une représentation textuelle de la liste d’éléments séparés par des espaces entre crochets :
                "[ a b c ... ]"
                Retourne "[ ]" si la liste est vide.
        """
        # IMPLEMENTATION CACHEE #