TNSI : TD Listes

Introduction

La Structure de Données Tableau, lorsqu'elle est implémentée par des Cellules contiguës, par exemple le type list de Python, permet :

• d'insérer (avec append()) et/ou de supprimer (avec pop() ) efficacement des éléments en fin de Tableau. Dans d'autres langages que Python, où les Tableaux ne sont même pas redimensionnables, mêmes les opérations append() et pop() ne sont pas simples.
• MAIS, la Structure de Tableau se prête mal à l'insertion et/ou suppression d'un élément à une autre position (par exemple en début ou au milieu de Tableau)

Dans ce TD, nous étudions une Structure de Données Liste (plus précisément une Liste Chaînée, à ne pas confondre avec le type de Données list de Python), proposant une meilleure solution au problème de l'insertion et/ou suppression au début (/milieu) de la Structure. L'importance de la liste comme structure de données est telle qu'elle est à la base du langage de programmation Lisp (de l'anglais List Processing).

Représenter Graphiquement une Liste

Représentation Horizontale

Représentation Verticale

Utilisation de l'Interface d'une Liste

Ex

On suppose ici connue seulement l'interface de la classe Liste(), c'est-à-dire le nom des méthodes sus-citées et ce qu'elles font. Néanmoins, on ne suppose pas connue précisément l'implémentation concrète de la classe Liste(), aucun besoin pour communiquer avec la classe Liste() via son interface.

On considère l'enchaînement d'opérations ci-dessous.

1°) Écrire à chaque étape l'état de la liste l et la valeur éventuellement renvoyée.

Etat de la listeCorrection

# On suppose que la classe Liste est déjà implémentée :
>>> l = Liste()
>>> l.ajouter_tete(4)       # ou l.unshift(4)
>>> l.ajouter_tete(7)
>>> l.est_vide()
>>> l.ajouter_queue(3)      # ou l.push(3)  ou l.enqueue(3)
>>> l.ajouter_queue(5)
>>> l.retirer_queue()       # ou l.pop()    ou l.dequeue()
>>> l.retirer_tete()
>>> l.ajouter_tete(6)
>>> l.ajouter_tete(9)
>>> l.ajouter_tete(2)
>>> l.retirer_tete()        # ou l.shift()
>>> l.retirer_queue()
>>> l.retirer_tete()
>>> l.retirer_queue()
>>> l.est_vide()

>>> l = Liste()
>>> l.ajouter_tete(4)   # 4
>>> l.ajouter_tete(7)   # 7 4
>>> l.est_vide()        # False
>>> l.ajouter_queue(3)  # 7 4 3
>>> l.ajouter_queue(5)  # 7 4 3 5
>>> l.retirer_queue()   # 7 4 3       --> renvoie 5
>>> l.retirer_tete()    # 4 3         --> renvoie 7
>>> l.ajouter_tete(6)   # 6 4 3
>>> l.ajouter_tete(9)   # 9 6 4 3
>>> l.ajouter_tete(2)   # 2 9 6 4 3
>>> l.retirer_tete()    # 9 6 4 3     --> renvoie 2
>>> l.retirer_queue()   # 9 6 4       --> renvoie 3
>>> l.retirer_tete()    # 6 4         --> renvoie 9
>>> l.retirer_queue()   # 6           --> renvoie 4
>>> l.est_vide()        # False

2°) Quelle méthode pourrait-ton taper pour que la liste soit vide?

Implémentation d'une Liste par un Tableau

Dans cette partie, un Tableau sera implémenté par le type de données list de Python

Implémentation d'une Liste par un Tableau

Implémenter une classe Liste, disposant des méthodes suivantes :

• Liste() : crée une liste vide.
• est_vide()-> bool : indique si la liste est vide (True), ou pas (False)
• ajouter_tete() : insère un élément en tête de liste.
• retirer_tete() : renvoie la valeur de l'élément en tête de liste ET le supprime de la liste.
• ajouter_queue() : insère un élément en queue de liste.
• retirer_queue() : renvoie la valeur de l'élément en queue de liste ET le supprime de la liste.
• renverser() : renvoie la Liste renversée (éléments écrits dans l'ordre contraire)
• concatener() : renvoie la concaténation de deux listes.

Implémentation d'une Liste avec une Liste Chaînée

Listes Simplement Chaînées

Lorsque l'implémentation de la liste fait apparaître une chaîne d'éléments, chacune pointant vers le suivant, on dit que la liste est une Liste Chaînée (Simple).

Def

Une Liste Chaînée (Simple), ou Liste Simplement Chaînée, ou tout simplement une Liste, est une implémentation d'une liste dans laquelle : * Tous les éléments sont appelés des Cellules , ou Maillons , ou Noeuds , ou Nodes , et se composent de deux choses : * une valeur * un lien, en fait un pointeur/référence, vers l'élément suivant / successeur * On suppose également connue la référence vers la première Cellule appelée Tête (et seulement cette référence)

Queue de la Liste On utilise le symbole ⟂ \(\,\) dont le nom officiel est "taquet vers le haut", pour représenter la fin de la liste (Queue), c'est-à-dire pour indiquer qu'il n'existe pas de Cellule suivante, après le dernier élément (Queue). En Python, on utilise souvent None pour implémenter ce concept.

Implémentation d'une Liste Chaînée -Simple- par une Classe Cellule

1. Implémenter une classe Cellule disposant :
   • d'attributs :
     • un attribut (public) valeur contenant les valeurs de la liste (par exemple des entiers)
     • un pointeur/attribut (public) suivante vers la Cellule suivante (initialisé à None pour une Cellule n'ayant pas de successeur)
   • des méthodes suivantes:
     • un accesseur / getter get_valeur() qui renvoie la valeur de la Cellule courante
     • un accesseur / getter get_suivante() qui renvoie le pointeur de la Cellule suivante
     • un mutateur / setter set_suivante() qui modifie le pointeur de la Cellule suivante
     • une méthode magique __repr__() qui affiche l'information valeur de la Cellule courante, lorsque :
       • l'on tape >>> cellule ou >>> print(cellule) dans un interpréteur Python
       • l'on utilise l'instruction print(cellule) dans un Script Python Exemple d'affichage souhaité : |•|3|8|5|7|⟂| où |•| désigne une référence vers la tête, et |⟂| désigne l'inexistance du suivant de la queue

2. Implémentation d'une Liste Chaînée par cette classe Cellule :

   On peut alors implémenter une Liste Chaînée (Simple) 3 (tête) --> 8 --> 5 --> 7 (queue) dans le Terminal, par l'instruction :

   >>> liste = Cellule(3, Cellule(8, Cellule(5, Cellule(7, None))))
   

   Une Liste Chaînée (Simple) peut donc être implémentée par:

   • soit la valeur None
   • soit un objet de classe Cellule contenant:
     • un attribut valeur contenant la valeur de la Cellule
     • un attribut suivante renvoyant vers une Liste (Simplement) Chaînée suivante

   Ceci mène à une définition récursive de la notion de Liste Chaînée

   2.1. Modifier la méthode magique __repr__() de la classe Cellule pour qu'elle affiche l'information | • | v1 (tête) | v2 | v3 | ... | vn (queue) | ⟂ | de la liste courante, lorsque :

   • l'on tape >>> liste ou >>> print(liste) dans un interpréteur Python
   • l'on utilise l'instruction print(liste) dans un Script Python

   2.2. Créer :

   • un accesseur / getter get_queue() de la classe Cellule, qui renvoie le pointeur vers la dernière Cellule (queue)
   • une méthode magique __len__() qui calcule et affiche la longueur de la liste courante, grâce à la syntaxe len(liste) dans un interpréteur Python
   • une méthode magique __getitem__(i:int) qui renvoie la valeur de la \(i\)-ème cellule de la liste courante, qui permettra l'utilisation via la syntaxe Python : liste[i]

3. Étudier les complexités en temps de chaque méthode de la classe Cellule

Implémentation d'une Liste Chaînée -Simple- par une classe 'Liste'

On souhaite maintenant encapsuler une Liste Chaînée dans un objet : Pour cela, on va utiliser la classe Cellule précédente (qu'il faudra peut-être adapter) pour implémenter une classe Liste (on aurait pu choisir le synonyme ListeChainee).

1. Implémenter une classe Liste, disposant :

   • de 2 attributs :

     • un attribut public tete contenant la référence vers la Cellule en tête

   • des méthodes suivantes :

     • Liste() : crée une liste vide (la liste vide pourra être implémentée par valeur = None et suivante = None)
     • est_vide()-> bool : indique si la liste est vide (True), ou pas (False)
     • ajouter_tete() : insère un élément en tête de liste.
     • retirer_tete() : supprime la tête de la liste.
     • un getter get_tete() qui renvoie la tête de la liste courante
     • ajouter_queue() : insère un élément en queue de liste.
     • retirer_queue() : retire l'élément en queue de la liste
     • un getter get_queue() qui renvoie la queue de la liste courante
     • une méthode magique __repr__() qui affiche l'information | • | v1 (tête) | v2 | v3 | ... | vn (queue) | ⟂ | de la liste courante, lorsque :
       • l'on tape >>> liste ou >>> print(liste) dans un interpréteur Python
       • l'on utilise l'instruction print(liste) dans un Script Python
     • une méthode magique __len__() qui calcule et affiche la longueur de la liste courante, grâce à la syntaxe len(liste) dans un interpréteur Python
     • une méthode magique __getitem__(i:int) qui renvoie la i-ème cellule de la liste courante, via la syntaxe Python : liste[i]
     • une méthode insert(i,valeur) : insère une Cellule contenant la valeur à l'indice i On veillera à ce que cette méthode ait exactement le même comportement que la méthode insert du type list de Python
     • renverser() : renvoie une Liste renversée (éléments dans l'ordre contraire)
     • concatener() : renvoie la concaténation de deux listes.

2. Quel intérêt une telle encapsulation peut-elle présenter?

• D'une part, il cache la représentation de la structure à l'utilisateur : ainsi, celui qui utilise notre classe Liste n'a plus à utiliser explicitement la classe Cellule :
  • Mieux encore, l'utilisateur peut complètement ignorer l'existence de la Classe Cellule.
  • De même, il ignore que la liste vide est représentée par None. En particulier, la réalisation de la classe Liste pourrait être modifiée sans pour autant que le code qui l'utilise (l'interface de la classe Liste) n'ait besoin d'être modifié à sont tour
• D'autre part, l'utilisation de classes et de méthodes (plutôt que de simples fonctions) nous permet de donner le même nom à toutes les méthodes qui sont de même nature :
  • Ainsi, on peut avoir plusieurs classes avec des méthodes est_vide(), ajouter_tete(), etc...
  • l'utilisation de simples fonctions nous aurait imposé de les nommer : liste_est_vide(), pile_est_vide(), ensemble_est_vide(), etc...

3. Étudier les complexités en temps de chaque méthode de la classe Liste

Listes Chaînées Doubles

Def

Une Liste Chaînée Double (comprendre à Double Extrémité) , ou Double Ended Queue , est une Liste Chaînée (Simple) contenant une référence :

• vers le premier élément (la tête) de la liste (comme d'habitude)
• et aussi, vers le dernier élément (la queue) de la liste

Implémentation des Listes Chaînées Doubles par une classe 'Liste'

On souhaite maintenant encapsuler une Liste Chaînée Double dans un objet : Pour cela, on va utiliser la classe Cellule précédente pour implémenter une (deuxième) classe Liste (à placer dans un autre fichier, ou bien on pourrait choisir le synonyme ListeChaineeDouble).

1. Implémenter une classe Liste, disposant :

2. de 2 attributs :

   • un attribut public tete contenant la référence vers la Cellule en tête
   • un attribut public queue contenant la référence vers la Cellule en queue

3. des méthodes suivantes :

   • Liste() : crée une liste vide (la liste vide pourra être implémentée par valeur = None et suivante = None)
   • est_vide()-> bool : indique si la liste est vide (True), ou pas (False)
   • ajouter_tete() : insère un élément en tête de liste.
   • retirer_tete() : supprime la tête de la liste.
   • un getter get_tete() qui renvoie la tête de la liste courante
   • ajouter_queue() : insère un élément en queue de liste.
   • retirer_queue() : retire l'élément en queue de la liste
   • un getter get_queue() qui renvoie la queue de la liste courante
   • insert(i,valeur) : insère une Cellule contenant la valeur à l'indice i

   • une méthode magique __repr__() qui affiche l'information | • | v1 (tête) | v1 | v3 | ... | vn (queue) | ⟂ | de la liste courante, lorsque :

     • l'on tape >>> liste ou >>> print(liste) dans un interpréteur Python
     • l'on utilise l'instruction print(liste) dans un Script Python

   • une méthode magique __len__() qui calcule et affiche la longueur de la liste courante, grâce à la syntaxe len(liste) dans un interpréteur Python

   • une méthode magique __getitem__(i:int) qui renvoie la i-ème cellule de la liste courante, via la syntaxe Python : liste[i]
   • renverser() : renvoie une Liste renversée (éléments dans l'ordre contraire)
   • concatener() : renvoie la concaténation de deux listes.

4. Quel intérêt une telle encapsulation peut-elle présenter?

• D'une part, il cache la représentation de la structure à l'utilisateur : ainsi, celui qui utilise notre classe Liste n'a plus à utiliser explicitement la classe Cellule :
  • Mieux encore, l'utilisateur peut complètement ignorer l'existence de la Classe Cellule.
  • De même, il ignore que la liste vide est représentée par None. En particulier, la réalisation de la classe Liste pourrait être modifiée sans pour autant que le code qui l'utilise (l'interface de la classe Liste) n'ait besoin d'être modifié à sont tour
• D'autre part, l'utilisation de classes et de méthodes (plutôt que de simples fonctions) nous permet de donner le même nom à toutes les méthodes qui sont de même nature :
  • Ainsi, on peut avoir plusieurs classes avec des méthodes est_vide(), ajouter_tete(), etc...
  • l'utilisation de simples fonctions nous aurait imposé de les nommer : liste_est_vide(), pile_est_vide(), ensemble_est_vide(), etc...

1. Étudier les complexités en temps de chaque méthode de cette (deuxième) classe Liste.
2. Quel.s avantage.s/Inconvénient.s la classe Liste Chaînée Double présente t-elle par rapport à la classe Liste Simplement Chaînée?

Aller Plus loin : Listes Doublement Chaînées, etc..

Il existe d'autres types d'implémentation des Listes

Listes Doublement Chaînées

Chaque élément est relié au précédent et au suivant

ATTENTION Une Liste Doublement Chaînée n'est PAS le même concept qu'une Liste Chaînée Double (comprendre à Double Extrémité, ou Double Ended Queue)

Listes Cycliques

Le dernier élément (queue) est relié (par une référence) au premier élément (tête)

Listes Cycliques Doublement Chaînées Combine les deux variantes prédentes

Implémentation par Listes Doublement Chaînées

• Modifier (après sauvegarde...) votre classe Cellule de l'exercice 3, pour que chaque Cellule dispose de 3 données:
  • la valeur
  • un pointeur vers la cellule suivante
  • un pointeur vers la cellule precedente
• Adapter si besoin la classe Liste, afin d'améliorer les complexités en temps lorsque/si cela est possible