Implémentation par des listes chaînées

Listes chaînées : description¶

Introduction¶

On rappelle que l'interface du type Liste est la suivante :

Fonction	Description
`creer_vide()`	Renvoie une liste vide
`est_vide(l)`	Renvoie `True` si et seulement si la liste est vide
`tete(l)`	Renvoie le premier élément de la liste \(l\) (l'élément dit de tête)
`queue(l)`	Renvoie la liste constituée de tous les éléments de \(l\) à l'exception du premier
`ajoute(l, e)`	Renvoie la liste constituée de l'élément \(e\), suivi des éléments de \(l\)
`affiche(l)`	Affiche la liste des éléments de \(l\) sur la sortie standard, séparés par le caractère `-`.
	La liste vide est représentée par `x`.

On se propose de donner une implémentation de cette interface via un objet nommé liste chaînée. En python, on peut représenter les listes de la manière suivante : chaque élément de la liste est associé à un objet, que nous appelerons un "maillon" (faisant partie d'une "chaîne" de maillons) qui comporte deux attributs :

un attribut valeur qui stocke la valeur de l'élément considéré ;
un attribut suivant qui permet de déterminer quel est le prochain maillon dans la chaîne.

On représente un maillon vide par la valeur spéciale None. Ainsi, on pourra instancier un objet m de type Maillon de trois façons distinctes :

m = None : le maillon est vide ;
m = Maillon(v, None) : le maillon est le seul dans sa chaîne ;
m = Maillon(v, m2) : le prochain maillon de la chaîne est le maillon m2 (supposé ici non vide).

Une chaîne de maillons ainsi constituée représente bien une liste d'éléments. La classe Liste possède donc un seul attribut : head une référence vers le premier maillon de la chaîne.

###

class Maillon:bksl-nl """ Un maillon d'une liste chainée. """bksl-nl def py-undpy-undinitpy-undpy-und(self, v, s):bksl-nl """ int, Maillon -> None """bksl-nl self.valeur = vbksl-nl self.suivant = sbksl-nlbksl-nlclass Liste:bksl-nl """ Une liste d'éléments. """bksl-nl def py-undpy-undinitpy-undpy-und(self, m):bksl-nl """ Maillon -> None """bksl-nl self.head = mbksl-nlbksl-nl

À l'aide de l'objet Maillon, on peut représenter la liste \(l = (3, 8, 42, 1)\). Pour chaque élément \(e\) de la liste, on créé un maillon qui contient la valeur de l'élément et le lien vers le maillon suivant.

maillon4 = Maillon(1, None)
maillon3 = Maillon(42, maillon4)
maillon2 = Maillon(8, maillon3)
maillon1 = Maillon(3, maillon2)

print(maillon2.valeur)
print(maillon2.suivant)
print(maillon2.suivant.valeur)

Créer des listes de cette façon est très fastidieux, en raison de l'utilisation de multiples variables. On peut condenser le code de la manière à n'utiliser qu'une seule variable :

m = Maillon(1, None)
m = Maillon(42, m)
m = Maillon(8, m)
m = Maillon(3, m)
# encore plus court :
# m = Maillon(3, Maillon(8, Maillon(42, Maillon(1, None))))

print(m.valeur)
print(m.suivant)
print(m.suivant.valeur)

3
<__main__.Maillon object at 0x7eb3b895c5c0>
8

Premier exemple¶

Écrire les instructions python permettant de stocker à l'aide d'objets de type Maillon, ou de la valeur spéciale None les listes \(l_1 = ()\), \(l_2 = (-1)\), \(l_3 = (5, 6, 9, -1)\), \(l_4 = (-5, 9, 13)\).

###

def testpy-undexemple():bksl-nl """ Tests pour la fonction exemple """bksl-nl print("Tests de exemple passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import exemplebksl-nl# testpy-undexemple()bksl-nlbksl-nl 5/5

maillon4 = Maillon(1, None)bksl-nlmaillon3 = Maillon(42, maillon4)bksl-nlmaillon2 = Maillon(8, maillon3)bksl-nlmaillon1 = Maillon(3, maillon2)bksl-nlbksl-nlprint(maillon2.valeur)bksl-nlprint(maillon2.suivant)bksl-nlprint(maillon2.suivant.valeur)bksl-nlbksl-nlm = Maillon(1, None)bksl-nlm = Maillon(42, m)bksl-nlm = Maillon(8, m)bksl-nlm = Maillon(3, m)bksl-nl# encore plus court :bksl-nl# m = Maillon(3, Maillon(8, Maillon(42, Maillon(1, None))))bksl-nl bksl-nlprint(m.valeur)bksl-nlprint(m.suivant)bksl-nlprint(m.suivant.valeur)bksl-nlbksl-nl# À compléterbksl-nl# m1 = ...bksl-nl# m2 = ...bksl-nl# m3 = ...bksl-nl# m4 = ...bksl-nlbksl-nl

Implémentation de l'interface de base des listes¶

Créer une liste vide¶

Écrire une fonction creer_vide qui renvoie, avec les conventions de l'énoncé, un maillon vide.

###

def testpy-undcreerpy-undvide():bksl-nl """ Tests pour la fonction creerpy-undvide """bksl-nl assert creerpy-undvide() is Nonebksl-nl print("Tests de creerpy-undvide passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import creerpy-undvidebksl-nltestpy-undcreerpy-undvide()bksl-nlbksl-nl 5/5

def creerpy-undvide():bksl-nl """ () -> Maillonbksl-nl Renvoie un maillon vide """bksl-nl passbksl-nlbksl-nl

Tester si un maillon est vide¶

Écrire une fonction est_vide étant donné un maillon m renvoie True si et seulement si celui-ci est vide.

###

def testpy-undestpy-undvide():bksl-nl """ Tests pour la fonction estpy-undvide """bksl-nl assert estpy-undvide(creerpy-undvide()) == Truebksl-nl assert estpy-undvide(Maillon(1, creerpy-undvide())) == Falsebksl-nl print("Tests de estpy-undvide passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import estpy-undvidebksl-nltestpy-undestpy-undvide()bksl-nlbksl-nl 5/5

def estpy-undvide(m):bksl-nl """ Maillon -> boolbksl-nl Renvoie True si et seulement si le maillon m est le maillon vide """bksl-nl passbksl-nlbksl-nl

Élément de tête¶

Écrire une fonction tete qui étant donné un maillon non vide m, renvoie la valeur stockée dans ce maillon.

###

def testpy-undtete():bksl-nl """ Tests pour la fonction tete """bksl-nl assert tete(Maillon(1, None)) == 1bksl-nl assert tete(Maillon(2, Maillon(1, None))) == 2bksl-nl print("Tests de tete passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import tetebksl-nltestpy-undtete()bksl-nlbksl-nl 5/5

def tete(m):bksl-nl """ Maillon -> intbksl-nl m est non videbksl-nl Renvoie l'attribut valeur du maillon m """bksl-nl passbksl-nlbksl-nl

Élément de queue¶

Écrire une fonction queue qui étant donné un maillon non-vide m, renvoie le maillon suivant de la chaîne de maillons.

###

def testpy-undqueue():bksl-nl """ Tests pour la fonction queue """bksl-nl m0 = Maillon(1, None)bksl-nl m1 = Maillon(2, m0)bksl-nl m2 = Maillon(3, m1)bksl-nl assert queue(m1) is m0bksl-nl assert queue(m2) is m1bksl-nl print("Tests de queue passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import queuebksl-nltestpy-undqueue()bksl-nlbksl-nl 5/5

def queue(m):bksl-nl """ Maillon -> Maillonbksl-nl m est non videbksl-nl Renvoie le maillon suivant dans la chaine de maillon de tête m. """bksl-nl passbksl-nlbksl-nl

Selon vous, quel est l'effet de l'instruction a is b ?

Ajout d'un maillon¶

Écrire une fonction ajoute qui étant donné un maillon m et un élément e renvoie le maillon m' dont l'attribut valeur est e et dont l'attribut suivant est m.

###

def testpy-undajoute():bksl-nl """ Tests pour la fonction ajoute """bksl-nl assert ajoute(None, 3).valeur == 3bksl-nl assert ajoute(None, 3).suivant == Nonebksl-nl print("Tests de ajoute passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ajoutebksl-nltestpy-undajoute()bksl-nlbksl-nl 5/5

def ajoute(m, e):bksl-nl """ Maillon, int -> Maillonbksl-nl Renvoie le maillon dont l'attribut valeur est e et l'attribut suivant est m """bksl-nl passbksl-nlbksl-nl

Affichage d'une liste chaînée¶

Pour afficher une liste chaînée, il faut parcourir tous les maillons la composant. Pour cela, deux approches sont possibles : une méthode récursive et méthode itérative.

Méthode récursive¶

Si le maillon est vide alors on affiche un symbole indiquant qu'il s'agit du maillon vide. Sinon, on affiche la valeur contenue dans le maillon, puis on affiche les maillons suivants de la chaîne.

###

def affichepy-undrec(m):bksl-nl """ Maillon -> Nonebksl-nl Affiche les valeurs de la chaîne dont le premier maillon est m. """bksl-nl if estpy-undvide(m):bksl-nl print("x")bksl-nl else:bksl-nl print(tete(m), end = " - ")bksl-nl affichepy-undrec(queue(m))bksl-nlbksl-nlaffichepy-undrec(m3)bksl-nlbksl-nl

5 - 6 - 9 - -1 - x

Que se passe-t-il si on échange les lignes 7 et 8 du code de la fonction affiche_rec ?
À quoi sert l'argument nommé end de la fonction print ? Modifier le code de la fonction précédente afin que l'affichage effectué par l'instruction affiche_rec(m3) soit :
```
5 | 6 | 9 | -1 | x
```

Méthode itérative¶

On initialise une variable maillon_courant qui stocke le maillon courant du parcours de la liste. Tant que le maillon courant n'est pas vide (ce qui veut dire que l'on n'est pas encore au bout de la chaîne), on affiche la valeur du maillon courant puis le maillon courant devient le maillon suivant dans la chaîne. Lorsque l'on atteint la fin de la chaîne, on affiche un symbole indiquant qu'il s'agit du maillon vide.

###

def affichepy-undi(m):bksl-nl """ Maillon -> Nonebksl-nl Affiche les valeurs de la chaîne dont le premier maillon est m """bksl-nl maillonpy-undcourant = mbksl-nl while not estpy-undvide(maillonpy-undcourant):bksl-nl print(tete(maillonpy-undcourant), end=' - ')bksl-nl maillonpy-undcourant = queue(maillonpy-undcourant)bksl-nl print("x")bksl-nlbksl-nlaffichepy-undi(m3)bksl-nlaffiche = affichepy-undibksl-nlbksl-nl

On utilisera dans la suite simplement l'instruction affiche pour afficher une chaîne de maillons.

Parcours d'une liste chaînée¶

Longueur d'une chaîne¶

On appelle longueur d'une chaîne de maillons le nombres de maillons non vide qui la composent.

Écrire une fonction itérative longueur qui étant donné un maillon m, détermine la longueur de la chaîne de maillons dont le premier maillon est m.

###

def message(input, output, expected):bksl-nl return f"Erreur :\n Entrée : {input}\n Sortie : {output}\n Attendu : {expected}"bksl-nlbksl-nldef tab2maillon(tab):bksl-nl maillon = Nonebksl-nl for i in range(len(tab) - 1, -1, -1):bksl-nl maillon = Maillon(tab[i], maillon)bksl-nl return maillonbksl-nlbksl-nldef égaux(m1, m2):bksl-nl if estpy-undvide(m1) and estpy-undvide(m2):bksl-nl return Truebksl-nl elif estpy-undvide(m1) ^ estpy-undvide(m2):bksl-nl return Falsebksl-nl return tete(m1) == tete(m2) and égaux(queue(m1), queue(m2))bksl-nlbksl-nldef testpy-undlongueur():bksl-nl """ Tests pour la fonction longueur """bksl-nl inputs = [tab2maillon([i for i in range(n)]) for n in range(10)]bksl-nl outputspy-undi = [longueurpy-undi(m) for m in inputs]bksl-nl outputspy-undr = [longueurpy-undr(m) for m in inputs]bksl-nl expecteds = [n for n in range(10)]bksl-nl for i in range(10):bksl-nl assert outputspy-undi[i] == expecteds[i], message(inputs[i], outputs[i], expecteds[i])bksl-nl assert outputspy-undr[i] == expecteds[i], message(inputs[i], outputs[i], expecteds[i])bksl-nl print("Tests de longueur passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import longueurbksl-nltestpy-undlongueur()bksl-nlbksl-nl 5/5

def longueur(m):bksl-nl """ Maillon -> intbksl-nl Compte le nombre de maillons présents dans la chaîne dont le premier maillon est m """bksl-nl # version itérativebksl-nl passbksl-nlbksl-nl

Élément d'indice i¶

On dit qu'un entier \(i\) est compatible avec la longueur d'une liste l constituée de \(n\) éléments si \(i < n\). Écrire une fonction itérative element qui étant donné un maillon m, et un entier i, supposé compatible avec la longueur de la chaîne, renvoie la valeur stockée dans le maillon d'indice \(i\) de la chaine dont le premier maillon est m.

###

def testpy-undelement():bksl-nl """ Tests pour la fonction element """bksl-nl inputs = tab2maillon([i for i in range(10)])bksl-nl outputspy-undi = [elementpy-undi(inputs, i) for i in range(10)]bksl-nl outputspy-undr = [elementpy-undr(inputs, i) for i in range(10)]bksl-nl expecteds = [i for i in range(10)]bksl-nl for i in range(10):bksl-nl assert outputspy-undi[i] == expecteds[i], message(inputs, outputs[i], expecteds[i])bksl-nl assert outputspy-undr[i] == expecteds[i], message(inputs, outputs[i], expecteds[i])bksl-nl print("Tests de element passés avec succès.")bksl-nl return Truebksl-nl# from tp import elementbksl-nltestpy-undelement()bksl-nlbksl-nl 5/5

def element(m, i):bksl-nl """ Maillon, int -> intbksl-nl m est non vide, 0 <= i < longueur(m)bksl-nl Renvoie l'élément d'indice i de la chaîne de maillons dont le premier est m """bksl-nl passbksl-nlbksl-nl

Remplacer l'élément d'indice i¶

Écrire une fonction itérative remplace qui étant donné un maillon m non vide, un entier i, supposé compatible avec la longueur de la chaîne, et un élément e, modifie la valeur du maillon d'indice i par e. Ainsi, après l'exécution de remplace(m, i, e) :

le premier maillon de la chaîne est toujours le maillon m ;
l'attribut valeur du maillon d'indice i de la chaine a été remplacé par e ;
les autres maillons de la chaîne sont inchangés.

###

def testpy-undremplace():bksl-nl """ Tests pour la fonction remplace """bksl-nl print("Tests de remplace passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import remplacebksl-nl# testpy-undremplace()bksl-nlbksl-nl 5/5

def remplace(m, i, e):bksl-nl """ Maillon, int, int -> Nonebksl-nl m est non vide, 0 <= i < longueur(m)bksl-nl Remplace par e la valeur du i-ème maillon de la chaine commençant par m """bksl-nl passbksl-nlbksl-nl

Écrire une fonction récursive remplace_rnm (récursive non mutable) qui étant donné un maillon m non vide, un entier i, supposé compatible avec la longueur de la chaîne, et un élément e, renvoie le premier maillon de la chaîne où la valeur du maillon d'indice i a été remplacée par e, sans modifier de maillon.
1 2 3 4 5 6
affiche(m4) affiche(remplace_rnm(m4, 0, 54)) affiche(m4) affiche(m3) affiche(remplace_rnm(m3, 2, 24)) affiche(m3)
```
24 - 9 - 13 - x
54 - 9 - 13 - x
24 - 9 - 13 - x
5 - 6 - 42 - -1 - x
5 - 6 - 24 - -1 - x
5 - 6 - 42 - -1 - x
```
Écrire une version itérative de la fonction remplace qui ne modifie aucun maillon.

Ajouter un élément à l'indice i¶

Écrire une fonction itérative ajoute_position qui étant donné un maillon m, un entier i, supposé compatible avec la longueur de la chaîne, et un élément e, ajoute un maillon à la chaine de telle sorte que :

le premier maillon de la chaîne soit toujours le maillon m ;
le maillon d'indice i de la chaîne ait pour valeur e ;
l'ordre d'apparition des valeurs des autres maillons de la chaîne est inchangé.

###

def testpy-undajoutepy-undposition():bksl-nl """ Tests pour la fonction ajoutepy-undposition """bksl-nl print("Tests de ajoutepy-undposition passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ajoutepy-undpositionbksl-nl# testpy-undajoutepy-undposition()bksl-nlbksl-nl 5/5

def ajoutepy-undposition(m, e, i):bksl-nl """ Maillon, int, int -> Nonebksl-nl Ajoute l'élément e en i-ième position de la chaine dont le premier maillon est m """bksl-nl passbksl-nlbksl-nl

Pour cela, on parcourera tous les maillons de la chaîne jusqu'à ce que le maillon_courant ait pour indice i (insertion en milieu de liste) ou que le maillon suivant de la chaîne soit vide (insertion en fin de liste).

Dans le cas où on insère en milieu de liste : on créé alors un nouveau maillon que l'on insère entre le maillon_courant et le maillon suivant de la chaîne comme sur le schéma ci-dessous.

On s'assure que les attributs valeur des maillons ont été correctement modifiés : l'attribut valeur du maillon d'indice i doit être e, l'attribut valeur du nouveau maillon doit être l'ancienne valeur du maillon d'indice i.
Dans le cas où on insère en fin de liste (cela veut dire que i vaut longueur(m)) : il suffit juste de créer un nouveau maillon et de le relier au dernier maillon de la liste.

Écrire une fonction récursive ajoute_position_rnm qui étant donné un maillon m non vide, un entier i, supposé compatible avec la longueur de la chaîne, et un élément e, renvoie le premier maillon de la chaîne où on a inséré à l'indice i un maillon de valeur e sans modifier de maillon.
1 2 3 4 5
affiche(m4) affiche(ajoute_position_rnm(m4, 0, 123)) affiche(m4) affiche(ajoute_position_rnm(m4, 3, 321)) affiche(m4)
```
24 - 9 - 13 - x
123 - 24 - 9 - 13 - x
24 - 9 - 13 - x
24 - 9 - 13 - 321 - x
24 - 9 - 13 - x
```
Écrire une version itérative de la fonction ajoute_position qui ne modifie aucun maillon.