Schématisons la mémoire d'un ordinateur comme un ensemble de cases dans lesquelles sont stockées des valeurs. Chacune de ces cases a une adresse, grâce à laquelle on peut accéder au contenu de la case.

• Un tableau est un groupe de cases consécutives. La taille (nombre de cases) d'un tableau est fixe (du moins dans la plupart des langages). Ajouter des éléments à un tableau nécessite donc de réserver un nouvel espace mémoire plus grand et de copier tous les éléments du tableau initial en y ajoutant les éléments voulus, ce qui a un coût linéaire en la taille du tableau (idem pour la suppression d'un élément). En contrepartie, on connaît directement l'adresse de n'importe quel élément du tableau, et on peut donc accéder à cet élément pour un coût constant.



• En Python, le type abstrait liste est représenté par le "type concret" list. Un élément de type list est un tableau dynamique : sa taille peut varier. Toutefois ajouter un élément à un tableau peut être coûteux :
• insérer un élément à la fin du tableau avec append a un coût constant dans la plupart des cas,
• mais insérer un élément au début d'un tableau a un coût linéaire en la taille du tableau.
• Une liste chaînée est un ensemble de cases non consécutives. Pour chaque élément de la liste, on stocke deux choses : la valeur de l'élément, et l'adresse de l'élément suivant. Pour accéder à un élément de la liste, il faut donc visiter tous les éléments précédents (accéder à l'élément d'indice i coûte (i+1) accès mémoire). En contrepartie, ajouter un élément à une liste possède un coût constant, et la liste est extensible autant que l'on veut.

Remarque

La fin de la liste est marquée par une cellule particulière, dont la valeur est ici représentée par le symbole ⊥ (ce symbole s'appelle "bas", ou "bottom" en anglais). En Python, nous traduirons ce symbole par l'objet None.

Schéma :

Remarque.

Il existe des variantes des listes chaînées, notamment les listes doublement chaînées dans lesquelles chaque cellule contient l'adresse de la cellule suivante et de la cellule précédente.

La vidéo suivante, de 5 min 54s à 13 min 35s, montre une méthode d'implantation une liste chainée en langage python.

Lien vers la video sur Lumni

Remarque.

Dans ce qui suit, nous allons mettre en œuvre des listes chaînées d'entiers. Mais on pourrait remplacer les entiers par n'importe quel type.

Pour implémenter nos listes chaînées, nous allons créer une classe Cellule. Les objets de cette classe ont deux attributs :

• un attribut valeur qui est la valeur de la cellule de tête de la liste (le premier élément de la liste),
• un attribut suivant qui est un pointeur vers la suite de la liste (et qui sera donc de type Cellule).

class Cellule : # constructeur def __init__ (self , val =None , suiv = None ) : """ self ( Cellule ), int , Cellule -> void Précondition : aucune Initialise un objet de classe Cellule """ self.valeur = val # valeur de la cellule self.suivant = suiv # pointeur vers la cellule suivante ma_liste = Cellule(42 , Cellule(5 , Cellule(14 , Cellule()))) print(ma_liste,ma_liste.valeur,ma_liste.suivant.valeur,ma_liste.suivant.suivant.valeur)

Exécuter

Pour créer un objet de type Cellule, il suffit alors de faire un appel du constructeur par élément de la liste : ligne 12 du code ci-dessus

Exercice :

Compléter le code Python ci-dessus :

1. Trouver une autre manière de créer la liste chainée ma_liste en créant les cellules les unes après les autres en trois lignes de code,

2. afficher les trois valeurs de la liste chainée,
3. ajouter une ligne de code permettant de supprimer le deuxième élément de la liste chainée,
4. afficher toutes les valeurs de la liste chainée,
5. ajouter une seule ligne de code permettant de réinsérer la cellule supprimée au point n°3,
6. afficher toutes les valeurs de la liste chainée.

Remarque.

Pour représenter la liste vide, on donne la valeur None aux attributs valeur et suivant. Dans la ligne 4 du code ci-dessus, les paramètres val et suiv du constructeur ont pour valeur par défaut : None. De cette façon, le constructeur appelé sans paramètre produira une liste vide.

Le code suivant contient le début de l'implémentation de la classe Liste. En plus du constructeur, il contient la méthode __str__ qui permet d'utiliser print pour des objets de classe Liste, et une méthode est_vide qui retourne True si la liste est vide et False sinon.

class Cellule: def __init__(self, val=None, suiv=None): """self(Cellule), int, Cellule -> void Précondition : aucune Initialise un objet de classe Cellule""" self.valeur = val # valeur de la cellule self.suivant = suiv # pointeur vers la cellule suivante def est_vide(self): """self(Cellule) -> bool Précondition : aucune Retourne True si le paramètre est vide et False sinon""" return self.valeur == None def __str__(self): """self(Cellule) -> str Précondition : aucune Retourne la chaîne à afficher pour les objets de classe Cellule""" chaine = "| " while (not self.est_vide()): chaine += str(self.valeur) if not self.suivant.est_vide(): chaine += ", " self = self.suivant chaine += " |" return chaine

Exécuter

Compléter la classe Cellule en y ajoutant une méthode __len__ qui :

• prend en paramètre l'objet lui-même,
• retourne la longueur (nombre d'éléments) du paramètre.

La méthode __len__ permet d'utiliser la fonction len avec un objet de classe Cellule en paramètre. Par exemple len(liste) devra retourner 3.

Compléter la classe Cellule en y ajoutant une méthode __getitem__ qui :

• prend en paramètres l'objet lui-même et un entier i,
• retourne l'élément d'indice i de la liste passée en paramètre.

La méthode __getitem__ permet d'utiliser la notation avec des crochets pour un objet de classe Cellule. Par exemple liste[2] devra retourner 14.

Si l'indice i dépasse de la liste, on pourra générer une erreur grâce à l'instruction :

raise IndexError("Indice trop grand !")

Compléter la classe Cellule en y ajoutant une méthode inserer qui :

• prend en paramètres l'objet lui-même, un entier i et un entier valeur,
• insère un élément égal à valeur à l'indice i de self (effet de bord).

Par exemple après appel à liste.inserer(1, 200) la variable liste devra être égale à | 42, 200, 5, 14 |.

Compléter la classe Cellule en y ajoutant une méthode modifier qui :

• prend en paramètres l'objet lui-même, un entier i et un entier valeur,
• remplace l'élément d'indice i de self par l'entier valeur (effet de bord).

Par exemple après appel à liste.modifier(1, 100), la variable liste devra valoir | 42, 100, 14 |.

Compléter la classe Cellule en y ajoutant une méthode supprimer qui :

• prend en paramètres l'objet lui-même et un entier i,
• supprime l'élément d'indice i de self (effet de bord).

Par exemple après appel à liste.supprimer(1) la variable liste devra valoir | 42, 14 |.

Écrire en dehors de la classe une fonction nb_occurrences qui :

• prend en paramètre un objet de classe Cellule noté liste, et un entier valeur,
• retourne le nombre d'occurrences de valeur dans liste.

Par exemple nb_occurrences(liste, 42) devra retourner 1.

Écrire une fonction (en dehors de la classe) minimum qui :

• prend en paramètre un objet de classe Cellule noté liste,
• retourne le minimum de liste.

Par exemple minimum(liste) devra retourner 5

Attention, l'implémentation des listes chaînées proposée ici est un choix. Il en existe bien sûr de nombreuses variantes, et il faut être capable de s'adapter.