TP - Implémenter une liste chaînée

Ce TP doit conduire à créer de A à Z un module utilisable tout le reste de l'année.

Téléchargez le fichier « à trous » TAD_listes_chainees.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le dossier intitulé [Mes_modules].

Ce TP a pour but de définir une structure de données implémentant, en programmation orientée objet des listes sous la forme de listes chaînées.

Partie 1 - Classe Maillon

Les objets de la classe Maillon seront munis de deux attributs :

• valeur : la valeur de l'élément ;
• suivant : le lien qui pointe vers l'élément (le maillon) suivant.

Ces attributs seront initialisés par défaut à None.

1. Complétez le constructeur de la classe Maillon.

   class Maillon:
       def __init__(self, valeur=None, suivant=None):
           pass
   

2. Testez l'instruction suivante :

   >>> n = Maillon(4)
   >>> n
   

   1. Quel est le maillon créé par cette instruction ?
   2. A quoi correspond l'affichage obtenu ?

3. Complétez la définition de la méthode __repr__() afin d'obtenir des affichages de la forme suivante :

   >>> m = Maillon()
   >>> m
   (None, None)
   
   >>> n = Maillon(4, m)
   >>> n
   (4, (None, None))
   

Partie 2 - Classe ListeChainee

Les objets de la classe ListeChainee sont munis du seul attribut premier, initialisé à None par défaut.

Complétez les méthodes de cette classe et vérifiez votre travail à l'aide du plan de test qui suit.

Le code à compléter

class ListeChainee:
    """
    Implémentation d'une liste chaînée
    """

    def __init__(self):
        """
        Initialisation d'une liste chaînée.
        """
        pass

    def est_vide(self):
        """
        Booléen indiquant si la liste chaînée est vide
        """
        pass

    def inserer_en_tete(self, elt):
        """
        Insère un élément en tête de liste.
        """
        pass

    def tete(self):
        """
        Renvoie la valeur de l'élément en tête de liste.
        """
        pass

    def queue(self):
        """
        Renvoie la liste située en queue (pas le maillon !)
        sous la forme d'une nouvelle liste.
        Attention aux effets de bord
        """
        pass

    def __repr__(self):
        """
        Sortie: str - Chaîne d'affichage de la liste.
        """
        pass

Plan de test

Attention à la méthode queue() qui doit doit renvoyer une liste de type ListeChainee.

>>> lst = ListeChainee()
>>> lst
None

>>> lst.inserer_en_tete(2)
>>> lst.inserer_en_tete(8)
>>> lst.inserer_en_tete(5)
>>> lst
(5, (8, (2, None)))

>>> lst.tete()
5

>>> lst2 = lst.queue()
>>> lst2
(8, (2, None))

>>> lst2.inserer_en_tete(0)
>>> lst2
(0, (8, (2, None)))