Aller au contenu

🚇La liste chaînée⚓︎

Le maillon⚓︎

Dans une tentative de définition récursive de la pile, en Python, on a vu l'intérêt d'avoir un objet qui regroupe un élément et un lien vers la suite de la pile. Nous avions utilisé un tuple (tête, queue), où tête était l'élément au sommet, et queue la suite des données de la pile, mais nous n'avions pas pu donner le status de pile à la queue. En utilisant deux classes, nous y arriverons.

Un maillon possède deux attributs, un élément et un lien vers le suivant.

🐍 Script Python
class Maillon:
    """Un maillon est donné par son élément et son maillon suivant à droite,
    éventuellement None.
    """

    def __init__(self, élément, droite):
        self.élément = élément
        self.droite = droite

    def __str__(self):
        return str(self.élément)

Voici un exemple d'utilisation simple.

🐍 Console Python
>>> m_1 = Maillon(42, None)
>>> m_2 = Maillon(1337, m_1)
>>> m_3 = Maillon(2021, m_2)

Et le schéma associé :

\[\boxed{m_3:(2021, \text{vers }m_2)} \rightarrow \boxed{m_2:(1337, \text{vers }m_1)} \rightarrow \boxed{m_1:(42, \text{vers le vide})} \rightarrow \text{Nil}\]

Nil représente le vide.

Avec Python, le passage de paramètres se fait par un lien, l'adresse mémoire, ainsi les objets m_1 et m_2 ne sont pas copiés dans m_2 et m_3, seule leur adresse est donnée.

Le ramasse miette

Quand un objet n'est référencé nulle part, par aucune variable, qu'il ne peut donc plus être joignable, Python possède un mécanisme (le ramasse miette ; garbage collector) qui supprime les données inutilisées ; ainsi on pourra supprimer un maillon simplement en n'ayant plus aucune variable qui le référence.

On devine qu'on va pouvoir avec cette structure construire les méthodes pour une pile, mais aussi pour une file, pour une deque, et plus encore. On va pouvoir supprimer un maillon au milieu d'une chaine en faisant pointer le précédent sur un autre maillon, et pour insérer un maillon, il suffira de modifier les suivants de deux maillons...

Listes chainées à un maillon⚓︎

On va utiliser deux classes :

  • Une classe Maillon qui contient un élément et le suivant dans la liste.
  • Une classe Liste qui contient un maillon de tête et les méthodes pour la faire vivre.

On commence par construire les méthodes analogues à une pile, ensuite on complètera en deque.

Première approche, implémenter la pile⚓︎

🐍 Script Python
class Maillon:
    """Un maillon est donné par son élément et son maillon suivant à droite,
    éventuellement None.
    """

    def __init__(self, élément, droite):
        self.élément = élément
        self.droite = droite

    def __str__(self):
        return str(self.élément)


class Liste:
    """Une liste est donnée par son maillon de gauche
    ajouter/extraire à gauche correspond à empiler/dépiler
    """

    def __init__(self):
        self.maillon_gauche = None

    def est_vide(self):
        return self.maillon_gauche is None

    def ajout_gauche(self, élément):
        self.maillon_gauche = Maillon(élément, self.maillon_gauche)

    def extrait_gauche(self):
        if self.est_vide():
            raise ValueError("Liste vide")
        élément = self.maillon_gauche.élément
        self.maillon_gauche = self.maillon_gauche.droite
        return élément

    def __str__(self):
        affichage = "Contenu : "
        maillon = self.maillon_gauche
        while maillon is not None:
            affichage += str(maillon) + "::"
            maillon = maillon.droite
        affichage += " fin."
        return affichage

if __name__ == '__main__':
    # tests
    test = Liste()

    # test est_vide
    assert test.est_vide()

    # test un ajout_droite ; extraction_gauche
    test.ajout_gauche(42)
    élément = test.extrait_gauche()
    assert élément == 42
    assert test.est_vide()

    # test plusieurs ajouts
    premiers = [2, 3, 5, 7, 11]

    for élément in premiers:
        test.ajout_gauche(élément)
    assert [test.extrait_gauche()
            for _ in range(len(premiers))] == premiers[::-1]
    assert test.est_vide()

Exercice 1

Tester aussi cette implémentation de la pile. Sur FranceIOI par exemple.

Implémenter la deque⚓︎

Implémenter la deque est de difficulté comparable à implémenter la file, autant faire mieux immédiatement, on aura indirectement la file.

Exercice 2

Compléter la classe pour obtenir les méthodes de la deque. Ces méthodes sont-elles toutes efficaces ? Tester sur FranceIOI par exemple.

Réponse
🐍 Script Python
class Maillon:
    """Un maillon est donné par son élément et son maillon suivant à droite,
    éventuellement None.
    """

    def __init__(self, élément, droite):
        self.élément = élément
        self.droite = droite

    def __str__(self):
        return str(self.élément)


class Liste:
    """Une liste est donnée par son maillon de gauche
    On crée une structure de deque avec une liste simplement chaînée.
    !!! Elle n'est pas efficace à droite !!!
    """

    def __init__(self):
        self.maillon_gauche = None

    def est_vide(self):
        return self.maillon_gauche is None

    def ajout_gauche(self, élément):
        self.maillon_gauche = Maillon(élément, self.maillon_gauche)

    def extrait_gauche(self):
        if self.est_vide():
            raise ValueError("Liste vide")
        élément = self.maillon_gauche.élément
        self.maillon_gauche = self.maillon_gauche.droite
        return élément

    def __str__(self):
        affichage = "Contenu : "
        maillon = self.maillon_gauche
        while maillon is not None:
            affichage += str(maillon) + "::"
            maillon = maillon.droite
        affichage += " fin."
        return affichage

    def ajout_droite(self, élément):
        if self.est_vide():
            self.maillon_gauche = Maillon(élément, None)
        else:
            maillon = self.maillon_gauche
            while maillon.droite is not None:
                maillon = maillon.droite
            maillon.droite = Maillon(élément, None)

    def extrait_droite(self):
        if self.est_vide():
            raise ValueError("Liste vide")

        maillon = self.maillon_gauche

        if maillon.droite is None:
            élément = maillon.élément
            self.maillon_gauche = None
            return élément

        précédent = maillon
        maillon = maillon.droite
        while maillon.droite is not None:
            précédent = maillon
            maillon = maillon.droite
        élément = maillon.élément
        précédent.droite = None
        return élément


if __name__ == '__main__':
    # tests
    test = Liste()

    # test est_vide
    assert test.est_vide()

    # test un ajout/extraction à droite
    test.ajout_droite(42)
    élément = test.extrait_droite()
    assert élément == 42
    assert test.est_vide()

    # test un ajout/extraction à gauche
    test.ajout_gauche(1337)
    élément = test.extrait_gauche()
    assert élément == 1337
    assert test.est_vide()

    # test plusieurs ajouts
    premiers = [2, 3, 5, 7, 11]

    for élément in premiers:
        test.ajout_gauche(élément)
    assert [test.extrait_droite()
            for _ in range(len(premiers))] == premiers
    assert test.est_vide()

    for élément in premiers:
        test.ajout_droite(élément)
    assert [test.extrait_gauche()
            for _ in range(len(premiers))] == premiers
    assert test.est_vide()

Complexité

On pose \(n\) la longueur de la chaine. La complexité des méthodes est la suivante :

  • ajout_gauche : \(\mathcal O(1)\) ; il suffit de modifier un maillon, et d'en ajouter un. Coût constant.
  • extrait_gauche : \(\mathcal O(1)\) ; il suffit de modifier un maillon. Coût constant.

En revanche pour lire ou écrire à droite, il faut parcourir toute la chaine pour accéder à l'autre bout. Ce parcours a un coût linéaire en \(n\).

  • ajout_droite : \(\mathcal O(n)\) ; il suffit de modifier un maillon, et d'en ajouter un ; mais avant cela, il faut parcourir la liste entièrement.
  • extrait_droite : \(\mathcal O(n)\).

Première conclusion

Si on a besoin uniquement d'une structure de pile, alors la liste simplement chaînée à un maillon est bien adaptée.

Avantages :

  • Il n'y pas de limite fixée à l'avance pour la taille de la pile.
  • C'est un peu plus technique à écrire ; donc pédagogique...

Inconvénients :

  • Utilise un peu plus de mémoire, surtout si les éléments de données sont de petite taille ; dans ce cas l'empreinte mémoire est doublée. Si chaque élément de donnée est imposant, alors c'est peu sensible. Cela fournit donc une implémentation d'autant plus lente.
  • C'est un peu plus technique à écrire ; mais pédagogique...

Pour bénéficier d'une structure efficace de file (ou de deque, pour laquelle on a presque le même coût intellectuel de construction), on va utiliser :

  • des listes qui mémorisent le maillon gauche et droite,
  • et/ou des maillons qui pointent à droite et à gauche.

Listes chainées à deux maillons⚓︎

Implémenter la file⚓︎

On garde le même maillon, mais la liste possède deux attributs : maillon_gauche et maillon_droite.

Exercice 3

Écrire une classe Liste avec uniquement les méthodes d'une file.

Réponse

On peut avoir une file en conservant correctement le maillon gauche et le maillon droite de la liste.

🐍 Script Python
class Maillon:
    """Un maillon est donné par son élément et son maillon suivant à droite,
    éventuellement None.
    """

    def __init__(self, élément, droite):
        self.élément = élément
        self.droite = droite

    def __str__(self):
        return str(self.élément)


class Liste:
    """Une liste est donnée par son maillon de gauche, et son maillon droite.
    On crée une structure de file avec une liste simplement chaînée.
    ajout_droite correspond à enfiler
    extrait_gauche correspond à défiler
    """

    def __init__(self):
        self.maillon_gauche = None
        self.maillon_droite = None

    def est_vide(self):
        return (self.maillon_gauche is None) and (self.maillon_droite is None)

    def ajout_droite(self, élément):
        maillon = Maillon(élément, None)
        if self.est_vide():
            self.maillon_gauche = maillon
            self.maillon_droite = maillon
        else:
            self.maillon_droite.droite = maillon
            self.maillon_droite = maillon

    def extrait_gauche(self):
        if self.est_vide():
            raise ValueError("Liste vide")
        élément = self.maillon_gauche.élément
        self.maillon_gauche = self.maillon_gauche.droite
        if self.maillon_gauche is None:
            self.maillon_droite = None
        return élément

    def __str__(self):
        affichage = "Contenu : "
        maillon = self.maillon_gauche
        while maillon is not None:
            affichage += str(maillon) + "::"
            maillon = maillon.droite
        affichage += " fin."
        return affichage


if __name__ == '__main__':
    # tests
    test = Liste()

    # test est_vide
    assert test.est_vide()

    # test un ajout_droite ; extraction_gauche
    test.ajout_droite(42)
    élément = test.extrait_gauche()
    assert élément == 42
    assert test.est_vide()

    # test plusieurs ajouts
    premiers = [2, 3, 5, 7, 11]

    for élément in premiers:
        test.ajout_droite(élément)
    assert [test.extrait_gauche()
            for _ in range(len(premiers))] == premiers
    assert test.est_vide()

Complexité

On pose \(n\) la longueur de la chaine. La complexité des méthodes est la suivante :

  • ajout_gauche : \(\mathcal O(1)\) ; il suffit de modifier un maillon, et d'en ajouter un. Coût constant.
  • extrait_droite : \(\mathcal O(1)\) ; il suffit de modifier un maillon. Coût constant.

Conclusion

Si on a besoin de construire une classe file, cette liste simplement chaînée à deux maillons est intéressante.

Listes doublement chainées⚓︎

On utilise un nouveau type de maillon, qui possède trois attributs :

  • son élément de donnée,
  • un lien vers la gauche,
  • un lien vers la droite.

Implémenter la deque⚓︎

Exercice 4

Réécrire une implémentation de la deque avec une liste doublement chainée. Les méthodes sont-elles toutes efficaces ? Tester sur FranceIOI par exemple. Les parties gauche et droite sont totalement symétriques, il suffit de faire un copié/collé et d'échanger droite et gauche.

Réponse

On utilise des maillons qui pointent dans les deux sens.

On donne une implémentation pour une deque en conservant les deux maillons gauche et droite.

🐍 Script Python
class Maillon:
    """Un maillon est donné par son élément
     et ses maillons à gauche et à droite, éventuellement None.
    """

    def __init__(self, gauche, élément, droite):
        self.gauche = gauche
        self.élément = élément
        self.droite = droite

    def __str__(self):
        return str(self.élément)


class Liste:
    """Une liste est donnée par ses maillons de gauche et de droite.

    On crée une structure de deque avec une liste doublement chaînée.
    """

    def __init__(self):
        self.maillon_gauche = None
        self.maillon_droite = None

    def est_vide(self):
        return     (self.maillon_gauche is None) \
               and (self.maillon_droite is None)

    def ajout_gauche(self, élément):
        if self.est_vide():
            maillon = Maillon(None, élément, None)
            self.maillon_gauche = maillon
            self.maillon_droite = maillon
        else:
            # le nouveau maillon de gauche est un maillon qui
            #    - pointe à gauche vers Nil
            #    - possède l'élément donné en paramètre
            #    - pointe à droite vers l'ancien maillon de gauche
            self.maillon_gauche = Maillon(None, élément, self.maillon_gauche)

            # le nouveau maillon de gauche pointe à droite vers
            #   l'ancien maillon de gauche (pas un Nil)
            #    - il pointait avant à gauche sur Nil,
            #    - on modifie vers le nouveau maillon gauche
            self.maillon_gauche.droite.gauche = self.maillon_gauche

    def ajout_droite(self, élément):
        if self.est_vide():
            maillon = Maillon(None, élément, None)
            self.maillon_gauche = maillon
            self.maillon_droite = maillon
        else:
            # le nouveau maillon de droite est un maillon qui
            #    - pointe à droite vers Nil
            #    - possède l'élément donné en paramètre
            #    - pointe à gauche vers l'ancien maillon de droite
            self.maillon_droite = Maillon(self.maillon_droite, élément, None)

            # le nouveau maillon de droite pointe à gauche vers l'ancien maillon de droite (pas un Nil)
            #    - il pointait avant à droite sur Nil, on modifie vers le nouveau maillon droite
            self.maillon_droite.gauche.droite = self.maillon_droite

    def extrait_gauche(self):
        # cas : 0 maillon
        if self.est_vide():
            raise ValueError("Liste vide")

        # cas : 1 seul maillon
        if self.maillon_droite == self.maillon_gauche:
            élément = self.maillon_gauche.élément
            self.maillon_gauche = None
            self.maillon_droite = None
            return élément

        # cas : au moins deux maillons
        élément = self.maillon_gauche.élément
        self.maillon_gauche = self.maillon_gauche.droite
        self.maillon_gauche.gauche = None
        return élément

    def extrait_droite(self):
        # cas : 0 maillon
        if self.est_vide():
            raise ValueError("Liste vide")

        # cas : 1 seul maillon
        if self.maillon_droite == self.maillon_gauche:
            élément = self.maillon_droite.élément
            self.maillon_gauche = None
            self.maillon_droite = None
            return élément

        # cas : au moins deux maillons
        élément = self.maillon_droite.élément
        self.maillon_droite = self.maillon_droite.gauche
        self.maillon_droite.droite = None
        return élément

    def __str__(self):
        affichage = "Contenu : "
        maillon = self.maillon_gauche
        while maillon is not None:
            affichage += str(maillon) + "::"
            maillon = maillon.droite
        affichage += " fin."
        return affichage


if __name__ == '__main__':
    # tests
    test = Liste()

    # test est_vide
    assert test.est_vide()

    # test un ajout/extraction à droite
    test.ajout_droite(42)
    élément = test.extrait_droite()
    assert élément == 42
    assert test.est_vide()

    # test un ajout/extraction à gauche
    test.ajout_gauche(1337)
    élément = test.extrait_gauche()
    assert élément == 1337
    assert test.est_vide()

    # test plusieurs ajouts
    premiers = [2, 3, 5, 7, 11]

    for élément in premiers:
        test.ajout_gauche(élément)
    assert [test.extrait_droite()
            for _ in range(len(premiers))] == premiers
    assert test.est_vide()

    for élément in premiers:
        test.ajout_droite(élément)
    assert [test.extrait_gauche()
            for _ in range(len(premiers))] == premiers
    assert test.est_vide()

Pour tester avec France-IOI, on pourra essayer les problèmes

Pour lesquels vous avez déjà un corrigé avec plusieurs implémentations comparées de pile, de file ou de deque.

Illustration des méthodes⚓︎

ajout_gauche⚓︎

Cas 1, si la liste est vide⚓︎

Si la liste est vide, on crée un maillon qui sera le maillon gauche et aussi droite de la liste, il ne pointe nulle part, ni à droite, ni à gauche.

Exemple où on ajoute un premier maillon avec l'élément \(42\).

\[\text{Nil} \leftarrow \boxed{\text{vers le vide} ; 42 ; \text{vers le vide}} \rightarrow \text{Nil}\]
Cas 2, si la liste est non vide⚓︎

Si la liste est non vide, alors :

  • On crée un nouveau maillon, et ce maillon sera le nouveau maillon gauche de la liste.
  • À sa droite se trouvera l'ancien maillon gauche de la liste.
  • Cet ancien maillon gauche pointait avant à gauche sur le vide, désormais il pointera sur le nouveau maillon.

Exemple où le maillon gauche possède l'attribut élément à \(42\). On ajoute à gauche un maillon avec \(1337\).

  • Avant : \(\qquad\text{Nil} \leftarrow m_1: \boxed{\text{vers le vide} ; 42 ; \text{vers la suite}} \rightarrow ...\)

    • On crée le maillon \(m_0\) :
      • qui pointe à gauche sur le vide,
      • avec l'élément \(1337\),
      • qui pointe à droite sur \(m_1\).
    • On modifie \(m_1\), il pointera désormais à gauche vers \(m_0\).
  • Après : \(\qquad\text{Nil} \leftarrow m_0: \boxed{\text{vers le vide} ; 1337 ; \text{vers }m_1} \leftrightarrow m_1: \boxed{\text{vers }m_0 ; 42 ; \text{vers la suite}} \rightarrow ...\)

extrait_gauche⚓︎

Cas 1, la liste est vide⚓︎

On ne peut pas extraire, on lève une exception.

Cas 2, la liste ne contient qu'un élément⚓︎

Dans ce cas, le maillon de gauche existe, mais il pointe à sa droite sur le vide. En supprimant un maillon, la liste devient vide.

Cas 3, la liste contient plusieurs éléments⚓︎

Dans ce cas, le maillon de gauche existe et il pointe à sa droite sur un autre maillon ; ce maillon sera le nouveau maillon gauche.

Exemple où le maillon gauche possède l'attribut élément à \(1337\), et pointe vers un maillon avec \(42\).

  • Avant : \(\qquad\text{Nil} \leftarrow m_0: \boxed{\text{vers le vide} ; 1337 ; \text{vers }m_1} \leftrightarrow m_1: \boxed{\text{vers }m_0 ; 42 ; \text{vers la suite}} \rightarrow ...\)
    • On enregistre la valeur \(1337\), pour la renvoyer à la fin.
    • On établit que le maillon gauche de la liste est celui à droite de l'ancien maillon gauche. Ici, \(m_1\) devient le maillon gauche de la liste.
    • On modifie \(m_1\) afin qu'il pointe désormais à gauche sur le vide.
    • On renvoie \(1337\).
  • Après : \(\qquad\text{Nil} \leftarrow m_1: \boxed{\text{vers le vide} ; 42 ; \text{vers la suite}} \rightarrow ...\)

Complexité

On pose \(n\) la longueur de la chaine. La complexité des méthodes est la suivante :

  • ajout_gauche : \(\mathcal O(1)\) ; il suffit de modifier un maillon, et d'en ajouter un. Coût constant.
  • extrait_gauche : \(\mathcal O(1)\) ; il suffit de modifier un maillon. Coût constant.
  • ajout_droite : \(\mathcal O(1)\) ; il suffit de modifier un maillon, et d'en ajouter un. Coût constant.
  • extrait_droite : \(\mathcal O(1)\) ; il suffit de modifier un maillon. Coût constant.

Conclusion

Si on a besoin de construire une deque, la liste doublement chainée est intéressante, surtout si les éléments sont volumineux, mais peu nombreux. Cette construction est aussi pédagogique.

Avec Python, en dehors de l'aspect pédagogique, on utilisera la deque fournie dans collections.

Et ensuite⚓︎

Donnons maintenant une motivation à vouloir créer de nouvelles structures de données toujours plus efficaces.

  • On aimerait pouvoir insérer ou supprimer ailleurs qu'aux extrémités.
    • On devine qu'avec les maillons, il est facile d'insérer une valeur au milieu ou ailleurs dans une liste, il suffira de modifier quelques liens droite et gauche des maillons concernés. Mais pour accéder à ce maillon, il faut le rechercher...
  • Pour chercher un élément, il faut parcourir la liste, et dans le pire des cas, toute la liste.
    • On ne peut pas non plus avoir la notion d'indice comme dans un tableau. En effet, mettre à jour les indices à chaque ajout/suppression donne une mauvaise complexité ; il faudra parfois parcourir toute la liste.

Une structure pour chercher-insérer-supprimer

On aimerait une structure de données, où :

  • La recherche d'un élément est aussi rapide que possible.
  • L'insertion d'un élément est aussi rapide que possible.
  • La suppression d'un élément est aussi rapide que possible.

Les arbres binaires de recherche (ABR) seront un début de réponse à cette question.