Liste chaînée mutable (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
- le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
- la ressource Eduscol sur les types de données
- le cours de mon collègue Pierre Duclosson
🔖 Synthèse de ce qu'il faut retenir pour le bac
Structures de données mutables ou immuables⚓︎
Point de cours 5
- Une structure de données est immuable si on ne peut la modifier une fois qu'elle est construite. Évidemment on peut toujours accéder aux données en lecture
- Une structure de données est mutable si on peut la modifier une fois qu'elle est construite.
- Cette distinction entre types immuable et mutable n'a de sens que pour des types structurés, les types simples comme les entiers, les flottants, les booléens sont immuables (1 reste égal à 1 !).
Exemple 4 types natifs mutables et immuables en Python
En Python, pour représenter une séquence de données on peut utiliser le type list des tableaux dynamiques qui est mutable ou le type tuple qui est immuable.
>>> tup = (14, 10)
>>> tup[0]
14
>>> tup[0] = 11
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> tad = [14, 10]
>>> tad[0]
14
>>> tad[0] = 11
Quel est l'intérêt d'un type immuable ? Dans certains cas on a besoin de fixer certaines valeurs par exemple lorsqu'elles servent de clefs dans un dictionnaire implémenté par une table de hachage. Une fonction de hachage calcule à partir de la clef l'index de la case du tableau où est stockée la valeur donc la clef ne doit pas être modifiée pour que son image par la fonction de hachage reste inchangée. Ainsi un type mutable ne peut servir de clef dans un dictionnaire.
>>> dico = dict()
>>> dico[tup] = 1
>>> dico
{(14, 10): 1}
>>> dico[tad] = 0
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
Si dans l'implémentation d'une liste chaînée, une cellule est implémentée par un tuple, la liste chaînée est donc immuable.
Exemple 6 listes chaînées immuables avec des tuples
Avec l'implémentation du type abstrait Liste par des cellules implémentées à l'aide de tuple, les opérations queue et inserer renvoient une nouvelle liste. Le type tuple étant immuable en Python, ces listes chaînées sont immuables.
On a également présenté une implémentation à l'aide d'une classe Cellule qui devrait donc permettre de construire des listes chaînées mutables, il nous manquait juste la possibilité de représenter une liste vide.
Listes chaînées mutables⚓︎
Méthode 4 : listes chaînées mutables
Pour construire des listes chaînées mutables, il est naturel d'utiliser le paradigme objet (POO). On reprend l'implémentation avec une classe Cellule mais on intègre cette fois toutes les opérations du type abstrait Liste comme méthodes d'une classe Liste. Cette classe possède un seul attribut tete_liste qui pointe soit vers None (liste vide) ou vers la première cellule de la liste chaînée.
Exercice 7
💻 Saisir ses réponses sur Capytale
Complétez les méthodes longueur, modifier_tete, renverse_liste_iter et renverse_liste_rec de la classe Liste ci-dessous implémentant une liste chaînée mutable.
class Cellule:
def __init__(self, elt, suivant):
self.element = elt
self.suivant = suivant
class Liste:
def __init__(self):
self.tete_liste = None
def liste_vide(self):
return self.tete_liste is None
def inserer(self, elt):
self.tete_liste = Cellule(elt, self.tete_liste)
def tete(self):
assert not self.liste_vide()
return self.tete_liste.element
def queue(self):
assert not self.liste_vide()
liste_queue = Liste()
liste_queue.tete_liste = self.tete_liste.suivant
return liste_queue
def __str__(self):
if self.liste_vide():
return 'None'
return f"({str(self.tete_liste.element)}, {str(self.queue())})"
def longueur(self):
if self.est_vide():
return 0
queue = self.queue()
return 1 + queue.longueur()
def modifier_tete(self, elt):
assert not self.liste_vide()
self.tete_liste.element = elt
def renverse_liste_iter(self):
tmp = Liste()
lis = self
while not lis.liste_vide():
tmp.inserer(lis.tete())
lis = lis.queue()
self.tete_liste = tmp.tete_liste
def renverse_liste_rec(self, lis):
if self.liste_vide():
return
lis.inserer(self.tete())
self.queue().renverse_liste_rec(lis)
self.tete_liste = lis.tete_liste
Effets de bord avec listes chaînées mutables⚓︎
Effets de bord
Les listes chaînées mutables peuvent être modifiées après leur construction. Si deux listes chaînées mutables partagent les mêmes cellules, modifier une liste modifie l'autre par effet de bord, ce qui n'est pas toujours souhaitable.
Exemple 5
On crée une liste mutable liste1 puis on associe la queue de liste1 à une variable liste2. Si on modifie l'élément de la cellule en tête de liste2 c'est aussi la cellule suivante de la tête de liste1qui est donc modifiée par effet de bord.
>>> liste1 = Liste()
>>> liste1.inserer('P')
>>> liste1.inserer('T')
>>> liste1.inserer('T')
>>> liste1.inserer('H')
>>> print(liste1)
(H, (T, (T, (P, None))))
>>> liste2 = liste1.queue()
>>> print(liste2)
(T, (T, (P, None)))
>>> liste2.modifier_tete('F')
>>> >>> print(liste2)
(T, (T, (P, None)))
>>> print(liste1)
(H, (F, (T, (P, None))))
Avant la modification de liste2 :
Après la modification de liste2 :
