en décembre 2025 alors qu’avec la promo de T NSI on a essayé de créer une classe Maillon pour gérer les listes chainées on a rencontré un paquet de petites déconvenues. En voulant aller trop vite on (je) ne s’est pas posé toutes les questions nécessaires pour progressivement toutes les fonctions sur des bases solides.
Avant de se lancer il faut toujours se demander comment on va gérer les cas limites. Par exemple :
- quel est l’élément neutre ? Comment va-t-on le gérer ?
- si je veux retirer le premier élément à une chaine, que va-t-il se passer quand notre paramètre est une chaine ne contenant qu’un seul maillon ? si une chaine de ce type n’est pas l’élément neutre, alors que va-t-il se passer quand on va tenter d’appliquer la fonction retirer à l’élément neutre ?
Quand les consignes ne sont pas hyper claires, le programmeur arrive avec son imagination et ses habitudes et va avoir tendance à intérpréter la consigne à sa sauce, et à progressivement s’éloigner de la vision directrice de l’exercice telle qu’elle était envisagée par le client / concepteur de l’exercice. Dans le cadre d’exercices au niveau terminale à faire à la maison , en classe et en évaluation. Le professeur joue le rôle du client et c’est à lui d’être le plus clair possible quant à ses attentes, il doit s’assurer que ce qui est évident pour lui, l’est aussi pour les élèves. Il doit donc généralement se montrer le plus explicite possible.
En décembre 2025, voulant donner une chance aux élèves de pouvoir se confronter aux difficultés de la création d’une classe faite pour gérer les liste chainées, j’ai voulu proposer une alternative à la proposition de mon site. En surfant sur le web j’ai trouvé le site d’un collègue et décidé d’utiliser sa trame d’un collègue, sans me rendre compte qu’on pensait pas du tout de la même manière. Sans doute largement étoffées à l’oral ses consignes écrites étaient trop succinctes, et je me suis fourré dans bien des impasses et des différences irréconciliables avec l’esprit de l’exercice tel qu’il l’envisageait.
class Maillon :
def __init__(self,v=None):
self.val = v
self.suiv = None
def est_vide(self):
"""renvoie True si la liste chainée définie par le maillon de tête self est vide"""
la documentation de la méthode est_vide() gagnerait à être plus claire, surtout que beaucoup de choses vont prendre appuis sur la convention implicite qui en découle.
Au début j’avais adopté la convention qui me semblait la plus logique : une liste est vide si le maillon est vide, c’est à dire que non seulement il ne pointe vers rien mais qu’en plus sa valeur est elle aussi None. Ce n’était pas l’avis du concepteur original de l’exercice donc j’ai fait demandé aux élèves d’adopter sa convention : tout maillon non enchainé est considéré comme vide, autrement dit M est vide si M.suiv is None.
Après réflexion je n’aurai jamais dû adopter la convention de mon collègue. Même si elle peut faciliter les choses par endroit elle ne me convient pas.
cherchez de quoi compléter la méthode.
une fois que ça sera fait vous pourrez compléter aussi les autres méthodes et fonctions :
def tailleListe(self):
"""renvoyer le nombre de Maillon de la liste"""
def get_maillon_indice(M,i):
"""renvoie le Maillon d'indice i dans la liste de tête M
vu qu'on copie les listes habituelles, le premier indice sera 0"""
def affiche(M):
"""affiche le contenu de la liste M sous la forme [val1,val2,val3...]
en cas de liste chainée vide on affichera []"""
# vérifications :
M1=Maillon(4)
M2=Maillon(5)
M3=Maillon(7)
M4=Maillon(None)
M1.suiv=M2
M2.suiv=M3
affiche(M1) #affichera [4,5,7]
affiche(M4) #affichera []
assert M1.est_vide() == False
assert M4.est_vide() == True
remarque : ici affiche est une fonction, on pourrait aussi la proposer sous la forme de méthode.
Corrections
class Maillon :
def __init__(self,v=None):
self.val = v
self.suiv = None
def est_vide(self):
"""renvoie True si la liste chainée
définie par le maillon de tête self est vide"""
return self.val is None
# complexité O(1)
def tailleListe(self):
"""renvoyer le nombre de Maillon de la liste"""
liste = self
if liste.est_vide() : return 0
compteur = 1
while not liste.suiv is None:
compteur+=1
liste = liste.suiv
return compteur
def get_maillon_indice(M,i):
"""renvoie le Maillon d'indice i dans la liste de tête M"""
if i> M.tailleListe() - 1 : raise IndexError("indice invalide")
j=0
maillonTemp = M
while j < i :
j+=1
maillonTemp=maillonTemp.suiv
return maillonTemp
def affiche(M):
"""affiche le contenu de la liste M sous la forme [val1,val2,val3...]
en cas ou M est vide on affichera []"""
j=0
if M.val is None :
print("[]")
return
taille = M.tailleListe()
maillonTemp = M
affichage="["
while j < taille :
affichage=affichage+str(maillonTemp.val)+","
j+=1
maillonTemp=maillonTemp.suiv
print(affichage[:len(affichage)-1]+"]")
M1=Maillon(4)
M2=Maillon(5)
M3=Maillon(7)
M4=Maillon(None)
M1.suiv=M2
M2.suiv=M3
affiche(M1) #affichera [4,5,7]
affiche(M4) #affichera []
assert M1.est_vide() == False
assert M4.est_vide() == True
si on a envie d’avoir afficher en tant que méthode et non fonction , dans le code il faudra écrire à l’intérieur de la classe Maillon :
def affiche(self):
"""affiche le contenu de la liste sous la forme [val1,val2,val3...]
en cas où la liste est vide on affichera []"""
j=0
M = self
if M.val is None :
print("[]")
return
taille = M.tailleListe()
maillonTemp = M
affichage="["
while j < taille :
affichage=affichage+str(maillonTemp.val)+","
j+=1
maillonTemp=maillonTemp.suiv
print(affichage[:len(affichage)-1]+"]")
bien évidemment il faudra faire attention à l’indentation (on est décalé par rapport à la version fonction).
on va maintenant créer d’autres fonctions :
def ajouter_debut(M,nM):
"""ajouter le maillon nM en tête de la liste de tête M"""
def ajouter_fin(M,nM):
"""ajouter le maillon nM en fin de la liste de tête M"""
def ajouter_apres(M0,nM) :
"""inserer nM juste après M0 et le reste est décalé"""
def supprimer_debut(M):
"""supprime le 1er maillon de la liste M et le renvoie"""
def supprimer_fin(M):
"""supprime le dernier maillon de la liste M et le renvoie"""
M1,M2,M3=Maillon(4),Maillon(5),Maillon(7)
M4,M5,M6=Maillon(8),Maillon(-6),Maillon(-13)
M1.suiv=M2
M2.suiv=M3
affiche(M1) #affichera [4,5,7]
ajouter_debut(M1,M4)
affiche(M1) #affichera [4,5,7]
affiche(M4) #affichera [8,4,5,7]
ajouter_fin(M1,M5)
affiche(M1) #affichera [4,5,7,-6]
ajouter_apres(M2,M6)
affiche(M1) #affichera [4,5,-13,7,-6]
affiche(supprimer_debut(M1)) #affichera 4
affiche(M1) #affichera [5,-13,7,-6]
affiche(supprimer_fin(M1)) #affichera -6
affiche(M1) #affichera [5,-13,7]
correction
def ajouter_debut(M,nM):
"""ajouter le maillon nM en tête de la liste de tête M"""
nM.suiv=M
def ajouter_fin(M,nM):
"""ajouter le maillon nM en fin de la liste de tête M"""
m = M
while m.suiv is not None:
m = m.suiv
m.suiv=nM
def ajouter_apres(M0,nM) :
"""inserer nM juste après M0 et le reste est décalé"""
nM.suiv = M0.suiv
M0.suiv = nM
def supprimer_debut_best(M):
"""supprime le 1er maillon de la liste M et renvoie ce maillon et la nouvelle chaine obtenue
si la liste M ne contient qu'un seul maillon alors après execution M vaudra None"""
temp = M.suiv #ça sert de stockage temporaire pour la partie de M que l'on gardera
tete = Maillon(M.val)
if temp is not None :
sortie= Maillon(temp.val)
sortie.suiv = temp.suiv
else :
sortie = None
return tete, sortie
def supprimer_debut(M):
"""supprime le 1er maillon de la liste M et le renvoie"""
Maillon_tete=Maillon(M.val) #je récupère la tête qui sera renvoyée
if M.suiv is not None :
Mtemp=Maillon(M.suiv.val)
Mtemp.suiv=M.suiv.suiv
M.val,M.suiv = Mtemp.val, Mtemp.suiv #copie de Mtemp vers M
else :
M.val,M.suiv = None,None
return Maillon_tete
def supprimer_fin(M):
"""supprime le dernier maillon de la liste M et le renvoie"""
if M.tailleListe() ==0 : raise IndexError("rien à supprimer")
if M.tailleListe() == 1 :
Maillon_queue = Maillon(M.val)
M.val,M.suiv = None,None
return Maillon_queue
m = M
while m.suiv.suiv is not None:
m = m.suiv
Maillon_queue=m.suiv
m.suiv=None
return Maillon_queue
XXXXXXXXXXXXXXXXXXXXXX
création d’une fonction pour renverser une liste chainée
def renverser(M) :
"""renvois le renversement de la liste chaînée de maillon de tête M"""
M1,M2,M3=Maillon(4),Maillon(5),Maillon(7)
M4,M5,M6=Maillon(8),Maillon(-6),Maillon(-13)
M1.suiv=M2
M2.suiv=M3
M3.suiv=M4
affiche(M1) #affichera [4,5,7,8]
affiche(renverser(M1)) #affichera [8,7,5,4]
suite version qui ne marche pas
def renverser(M) :
"""renvois le renversement de la liste chaînée de maillon de tête M"""
renverse = Maillon(M.val)
temp = Maillon(0)
next=M.suiv
while not next is None :
temp.val = next.val
temp.suiv = renverse
renverse = temp
next = next.suiv
return renverse
à votre avis quel est le problème ???
indice : injecter dans la boucle while juste avant la dernière ligne la commande :
print(id(temp))
ça permet de voir que l’objet temp est bidouillé encore et encore mais ça reste du début à la fin le même objet… et qu’à force on finit par le définir en fonction de lui même, un autoréférencement très problématique qui génère le crash (boucle infinie observée)
version qui marche
def renverser(M) :
"""renvois le renversement de la liste chaînée de maillon de tête M"""
renverse = Maillon(M.val)
next=M.suiv
while not next is None :
temp=Maillon(next.val)
temp.suiv = renverse
renverse = temp
print(id(temp)) #ligne qui sera enlevé une fois le problème d'auto référencement bien compris
next = next.suiv
return renverse
non seulement ça marche mais en plus on voit bien , qu’à chaque tour de boucle on a un objet temp différent. Le nom est le même mais c’est écrasé encore et encore.
concaténation
créer la fonction suivante :
def concatener(M1, M2) :
"""retourne une nouvelle liste, résultat de la concaténation des listes de maillons de tête M1 et M2."""
M1,M2,M3=Maillon(4),Maillon(5),Maillon(7)
M4,M5,M6=Maillon(8),Maillon(-6),Maillon(-13)
M1.suiv=M2
M2.suiv=M3
M4.suiv=M5
M5.suiv=M6
affiche(M1) #affichera [4,5,7]
affiche(M4) #affichera [8,-6,-13]
affiche(concatener(M1, M4)) #affichera [4,5,7,8,-6,-13]
Remarque : concatener(M1, M2) ne modifiera aucune des deux listes chainées passées en paramètres mais renverra leur concaténation.
Solution :
def concatener(M1, M2) :
"""retourne une nouvelle liste, résultat de la concaténation des listes de maillons de tête M1 et M2."""
M = Maillon(M1.val)
M.suiv = M1.suiv
ajouter_fin(M,M2)
return M