class Maillon():

    def __init__(self, valeur, suivant = None):
        assert suivant is None or type(suivant) is Maillon
        self.valeur = valeur
        self.suivant = suivant

    def __str__(self):
        s = str(self.valeur)
        if not self.suivant is None : s += " " + str(self.suivant)
        return s

    def longueur(self):
        if self.suivant is None : return 1
        else : return 1 + self.suivant.longueur()

    def contient(self, elt):
        if self.valeur == elt : return True
        elif self.suivant is not None : return self.suivant.contient(elt)
        else : return False

    def append(self, elt):
        if not self.valeur is None : self.suivant = Maillon(self.valeur, self.suivant)
        self.valeur = elt

    def pop(self):
        elt = self.valeur
        if self.suivant is None : self.valeur = None   # représentation de la liste vide
        else : self.valeur, self.suivant = self.suivant.valeur, self.suivant.suivant
        return elt

    def supprimer(self, i):
        assert i >= 0
        if i == 0 :
            self.pop()
        else :
            if self.suivant is None : print("maillon inexistant")
            elif i == 1 :
                # cas où l'on souhaite supprimer le maillon suivant
                self.suivant = self.suivant.suivant
            else :
                # appel récursif pour les autres situations
                self.suivant.supprimer(i-1)

    def inserer(self, val, i):
        assert i >= 0
        if i == 0 :
            self.append(val)
        else :
            if i == 1 or self.suivant is None:
                # cas où l'on souhaite insérer la nouvelle valeur juste après
                # le maillon courant ou que le maillon courant est le dernier
                self.suivant = Maillon(val, self.suivant)
            else :
                # appel récursif pour les autres situations
                self.suivant.inserer(val, i-1)

if __name__ == "__main__" :
    # test du constructeur et du sérialiseur
    m1 = Maillon(2, None)
    chaine1 = Maillon(4, Maillon(7, Maillon(1, m1)))
    print(chaine1)
    chaine2 = Maillon(5, Maillon(8, Maillon(2, Maillon(3, Maillon(7,None)))))
    print(chaine2)
    # test des méthodes longueur et contient
    assert m1.longueur() == 1
    assert chaine1.longueur() == 4
    assert chaine2.longueur() == 5
    assert chaine1.contient(4)
    assert chaine1.contient(1)
    assert chaine1.contient(2)
    assert not chaine1.contient(5)
    # test des méthodes append et pop
    chaine1.append(6); assert str(chaine1) == "6 4 7 1 2"
    assert chaine1.pop() == 6
    assert chaine1.pop() == 4
    assert chaine1.pop() == 7
    chaine1.append(5); assert str(chaine1) == "5 1 2"
    # test de la méthode supprimer et inserer
    chaine2.supprimer(1); assert str(chaine2) == "5 2 3 7"
    chaine2.supprimer(0); assert str(chaine2) == "2 3 7"
    chaine2.inserer(4,2); assert str(chaine2) == "2 3 4 7"
    chaine2.inserer(8,0); assert str(chaine2) == "8 2 3 4 7"