Réalisation d'une classe Liste Chainee

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

from __future__ import annotations


class Maillon:
    """
    Un maillon de la liste.
    """

    def __init__(self: Maillon, valeur: int, suivant: Maillon = None) -> None:
        self.valeur = valeur
        self.suivant = suivant


class Liste:
    """
    Implémentation de la classe liste.
    """

    def __init__(self: Liste, valeur: int = None) -> None:
        """
        Initialisation de l'objet. Il est possible de créer une liste
        vide ou une liste contenant un élément.

        Il est possible de créer directemnt une liste contenant plusieurs
        éléments il faut utiliser une fonctionnalité de Python que vous
        ne connaissez pas forcément et qui n'est pas au programme.
        """
        if valeur is None:
            self.maillons = None
        else:
            self.maillons = Maillon(valeur)

    def est_vide(self: Liste) -> bool:
        """ Détermine si la liste est vide. """
        return self.maillons is None

    def __len__(self: Liste) -> int:
        """ Retourne le nombre d'éléments dans la liste. """
        if self.est_vide():
            return 0
        else:
            nbre = 0
            maillon = self.maillons
            while maillon is not None:
                nbre += 1
                maillon = maillon.suivant
            return nbre

    def append(self: Liste, valeur: int) -> None:
        """
        Ajoute valeur à la fin de la liste.
        """
        if self.est_vide():
            self.maillons = Maillon(valeur)
        else:
            maillon = self.maillons
            while maillon.suivant is not None:
                maillon = maillon.suivant

            maillon.suivant = Maillon(valeur)

    def append_first(self: Liste, valeur: int) -> None:
        """
        Ajoute valeur au début de la liste.
        """
        maillon = Maillon(valeur)
        maillon.suivant = self.maillons
        self.maillons = maillon

    def pop(self: Liste) -> int:
        """
        Retire le dernier élément de la liste et le retourne.

        Lève une erreur si la liste est vide.
        """
        if self.est_vide():  # Liste vide
            raise Exception("La liste est vide !")

        maillon = self.maillons
        if maillon.suivant is None:  # Cas d'une liste à un élément
            valeur = maillon.valeur
            self.maillons = None
            return valeur
        else:
            while maillon.suivant.suivant is not None:  # Cas général
                maillon = maillon.suivant
            valeur = maillon.suivant.valeur
            maillon.suivant = None
            return valeur

    def pop_first(self: Liste) -> int:
        """
        Retire le premier élément de la liste et le retourne.

        Lève une erreur si la liste est vide.
        """
        if self.est_vide():  # Liste vide
            raise Exception("La liste est vide !")

        valeur = self.maillons.valeur
        self.maillons = self.maillons.suivant
        return valeur

    def __getitem__(self: Liste, i: int) -> int:
        """
        Redéfinition de la fonction d'accès à l'élément d'indice i.
        """
        if self.est_vide():
            raise Exception("La liste est vide !")

        maillon = self.maillons
        j = 0
        while j < i:
            if maillon is None:
                raise IndexError("Indice hors des limites !")
            maillon = maillon.suivant
            j += 1
        return maillon.valeur

    def __str__(self: Liste) -> str:
        """
        Représentation de la liste sous-forme d'une chaîne de caractères.
        """
        rep = "["

        maillon = self.maillons
        while maillon is not None:
            rep += str(maillon.valeur)
            if maillon.suivant is not None:
                rep += ", "
            maillon = maillon.suivant

        rep += "]"
        return rep