Une liste chaînée

Une liste chaînée.

Une liste chaînée est formée de maillons : chaque maillon contient une valeur et une référence vers le maillon suivant (None pour le dernier). La liste ne mémorise que son premier maillon, la tête.

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

class ListeChainee:
    def __init__(self):
        self.tete = None          # liste vide

• Écrire la méthode ajouter_en_tete(self, x).
• Écrire la méthode longueur(self).
• Écrire la méthode element(self, i) qui renvoie la valeur d'indice i (la tête a l'indice $0$) et lève une IndexError si cet indice n'existe pas.
• Comparer le coût de l'ajout en tête et de l'accès à l'indice $i$ avec ceux d'une liste Python.