🚇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.
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.
>>> m_1 = Maillon(42, None)
>>> m_2 = Maillon(1337, m_1)
>>> m_3 = Maillon(2021, m_2)
Et le schéma associé :
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⚓︎
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
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.
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.
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
- Dates de péremption ; pour la pile.
- Distributeur automatique ; pour la file et la deque.
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\).
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\).
- On crée le maillon \(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.