Structure de liste

Avant de parler de l'implémentation, nous allons parler d'abstraction. Une structure est une implémentation à partir du moment où toutes les fonctions nécessaires au bon fonctionnement ont été réalisées dans un langage de programmation. Sinon, on parle de Type Abstrait de Données (TAD), et c'est ici que nous définissons les actions pour modifier notre structure.

Étape 1 : Concevoir le cahier des charges (TAD)

Nous devons définir la structure en indiquant ce qu'elle fait et comment elle fonctionne. Pour cela, nous utiliserons une structure de liste abstraite. Il s'agit d'un ensemble de règles qui ne vont pas dépendre de l'implémentation.

DéfinitionL'intérêt de la liste

Une liste est un type abstrait de données contenant un ensemble d'éléments qui sont tous accessibles.

Nous nommons notre structure de liste avec le nom Liste.

MéthodeLes Primitives

Une primitive est une fonction de base qui définit un concept simple permettant de modifier notre structure (ici la liste).

On distingue deux types de primitives :

Les primitives de base :

  • creerListeVide() : Liste - Crée et renvoie une liste vide

  • estVide() : Liste -> Booléen - Renvoie Vrai si la liste est vide, Faux sinon

  • ajouterTete() : Liste, Élément -> Liste - Modifie la liste en ajoutant un élément en tête de liste

  • retirerTete() : Liste -> Liste, Élément - Supprime l'élément de tête et renvoie sa valeur

  • ajouterQueue() : Liste, Élément -> Liste - Modifie la liste en ajoutant un élément en queue de liste

  • retirerQueue() : Liste -> Liste, Élément - Supprime l'élément de queue et renvoie sa valeur

Les primitives auxiliaires :

  • inserer() : Liste, Élément, Entier -> Liste - Insère l'élément à la position indiquée dans la liste

  • supprimer() : Liste, Entier -> Liste - Supprime l'élément situé à la position indiquée dans la liste

SimulationExemple d'utilisation

Étudions le code Python ci-dessous en donnant l'état de la liste à chaque appel de méthode :

1
l = Liste()
2
l.ajouterTete(3)
3
l.ajouterTete(8)
4
l.ajouterQueue(9)
5
l.estVide()
6
l.retirerTete()
7
l.ajouterTete(7)
8
l.retirerQueue()
9
l.estVide()
10
l.ajouterTete(4)
11
l.retirerQueue()
12
l.estVide()

Voyons maintenant l'état de la liste et des résultats de fonctions à chaque ligne.

1
l = Liste()
2
l.estVide()       # True
3
l.ajouterTete(3)  # 3
4
l.ajouterTete(8)  # 8 3
5
l.ajouterQueue(9) # 8 3 9
6
l.estVide()       # False
7
l.retirerTete()   # 3 9    - Retourne 8
8
l.ajouterTete(7)  # 7 3 9
9
l.retirerQueue()  # 7 3    - Retourne 9
10
l.estVide()       # False
11
l.ajouterTete(4)  # 4 7 3
12
l.retirerQueue()  # 4 7    - Retourne 3
13
l.estVide()       # False

Étape 2 : Proposer une implémentation

DéfinitionListe Chaînée (Simple)

Une Liste Chaînée (Simple), ou tout simplement une Liste, est une implémentation d'une liste dans laquelle :

  • Tous les éléments sont appelés des Cellules 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)

Linked list structureInformations[1]

https://www.cs-ib.net/sections/05-05-linked-lists.html

RemarqueTaquet vers le haut

Le symbole ⊥ appelé « Taquet vers le haut » permet de représenter la fin de la liste (la queue) et indique donc qu'il n'y a pas de cellule suivante après le dernier élément la queue.

En Python, on utilise souvent None pour implémenter ce concept.

ComplémentVariantes des listes chaînées

Il existe plusieurs variantes de listes chaînées, notamment deux que nous aurons l'occasion d'étudier :

  • La liste cyclique où le dernier élément est lié au premier

  • La liste doublement chaînée où chaque élément possède un lien vers l'élément précédent en plus de l'élément suivant

Exo : Représenter ces deux variantes avec un schéma sur la liste [1, 2, 3]

RemarqueHomogénéité

Dans le cas où tous les éléments de la liste sont du même type, on parle de liste homogène. Il est recommandé d'avoir des listes homogènes, même si Python autorise l'usage de listes non homogènes.

Implémentation par une classe Cellule

La cellule va nous permettre de représenter nos différents chaînons pour notre liste.

1
class Cellule:
2
    """Représente un élément de notre liste"""
3
4
    def __init__(self, v, s=None):
5
        """Crée une liste (presque) vide"""
6
        self.valeur = v
7
        self.suivante = s

Chaque objet de la classe Cellule contient deux attributs :

  • valeur qui représente la valeur de l'élément de notre liste ;

  • suivante qui représente l'élément suivant dans la liste ou None le cas échéant.

La variable lst ci-dessous correspond donc à une liste contenant les valeurs [1, 2, 3].

Cellule
Cellule
1
1

Cellule
Cellule
2
2

Cellule
Cellule
3
3
⊥
⊥
valeur
valeur
suivante
suivante

lst
lstText is not SVG - cannot display
Représentation d'une liste de trois éléments
SimulationExercice : Implémentation d'une Liste Chaînée par une classe Cellule

  1. Implémenter une classe Cellule disposant :

    • d'attributs :

      • un attribut valeur contenant les valeurs de la liste (par exemple des entiers)

      • un pointeur/attribut suivante vers la Cellule suivante (initialisé à None pour une Cellule n'ayant pas de successeur)

    • des méthodes suivantes:

      • un getter get_valeur() qui renvoie la valeur de la Cellule courante

      • un getter get_suivante() qui renvoie le pointeur de la Cellule suivante

      • un setter set_suivante() qui modifie le pointeur de la Cellule suivante

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

    On peut alors implémenter une Liste Chaînée (Simple) 4 (tête) --> 2 --> 9 --> 5 (queue) par les instructions suivantes :

1
# Version 1 : Créer chaque Cellule puis les relier entre-elles
2
cell1 = Cellule(4)
3
cell2 = Cellule(2)
4
cell3 = Cellule(9)
5
cell4 = Cellule(5)
6
7
cell1.set_suivante(cell2)
8
cell2.set_suivante(cell3)
9
cell3.set_suivante(cell4)
10
11
liste_finale = cell1
12
13
# Version 2 : Créer les Cellules dans l'ordre décroissant
14
cell4 = Cellule(5)
15
cell3 = Cellule(9)
16
cell3.set_suivante(cell4)
17
cell2 = Cellule(2)
18
cell2.set_suivante(cell3)
19
cell1 = Cellule(4)
20
cell1.set_suivante(cell2)
21
22
liste_finale = cell1
23
24
# Version 3 : En utilisant le constructeur
25
liste_finale = Cellule(4, Cellule(2, Cellule(9, Cellule(5))))
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
Écrire le code de la méthode __len__() qui calcule et affiche la longueur de la liste courante, grâce à la syntaxe len(liste)
Écrire le code de la méthode __getitem__(i) qui renvoie la valeur de la i-ème cellule de la liste courante, grâce à la syntaxe : liste[i]
Implémentation par une classe Liste
Nous ne pouvons pas conserver notre liste comme une Cellule. En effet, on veut pouvoir conserver un accès vers la tête et vers la queue de notre liste. Pour cela, nous allons créer une classe Liste qui sera similaire à notre TAD (Type Abstrait de Données).
1
class Liste:
2
3
    def __init__(self):
4
        """Crée une liste vide (fonction abstraite creerListeVide())"""
5
        self.tete = None
SimulationExercice : Implémentation d'une Liste Chaînée par une classe Liste
On va utiliser la classe Cellule précédente (qu'il faudra peut-être adapter) pour implémenter une classe Liste.
  1. Implémenter une classe Liste, disposant :
    • de 1 attribut :
      • un attribut tete contenant la référence vers la Cellule en tête ou None si la liste est vide
    • des méthodes suivantes énoncées en TAD :
      • creerListeVide() : Liste - Crée et renvoie une liste vide
      • estVide() : Liste -> Booléen - Renvoie Vrai si la liste est vide, Faux sinon
      • ajouterTete() : Liste, Élément -> Liste - Modifie la liste en ajoutant un élément en tête de liste
      • retirerTete() : Liste -> Liste, Élément - Supprime l'élément de tête et renvoie sa valeur
      • ajouterQueue() : Liste, Élément -> Liste - Modifie la liste en ajoutant un élément en queue de liste
      • retirerQueue() : Liste -> Liste, Élément - Supprime l'élément de queue et renvoie sa valeur
Quel est l'intérêt d'une telle implémentation ? Elle cache la représentation de la structure à l'utilisateur : ainsi, en utilisant la classe Liste, l'utilisateur n'a plus à utiliser la classe Cellule.
Étape 3 : Améliorer son implémentation
On remarque quelques problèmes sur l'implémentation précédente :
  • L'ajout ou la suppression d'un élément en queue est long car il faut parcourir la liste en entier
  • De même pour le calcul de la longueur
DéfinitionListes Chaînées (Doubles)
Une Liste Chaînée Double (comprendre à Double Extrémité) 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)
  • vers le dernier élément (la queue) de la liste
1
class Liste:
2
3
    def __init__(self):
4
        """Crée une liste vide (fonction abstraite creerListeVide())"""
5
        self.tete = None
6
        self.queue = None