Aller au contenu principal
Physique, Chimie et Informatique > Terminales Spé. NSI

Listes chaînées

Au programme

Contenus Capacités attendues Commentaires
- Listes. - Distinguer des structures par le jeu des méthodes qui les caractérisent.
- Choisir une structure de données adaptée à la situation à modéliser.
- Les listes n’existent pas de façon native en Python.

Documents

13 oct. 2020

Sous-sections de Listes chaînées

Physique, Chimie et Informatique > Terminales Spé. NSI > Listes chaînées

Listes Chaînées, présentation

Tableaux

À retenir
  • Un tableau est une structure de données dans laquelle les éléments, tous de même type, occupent des positions contiguës en mémoire.
  • Le nombre d’éléments qu’un tableau peut contenir est déterminé à la création d’un tableau.
Type Python Type Opération Exemple Complexité
N’existe pas Tableau Accès à un élément tab[i] O(1)O(1)
Modification d’un élément tab[i] = x O(1)O(1)
Effacement d’un élément retire(tab, i) O(n)O(n)
Insertion d’un élément insere(tab, x, i) O(n)O(n)
Recherche d’un élément est_dans(tab, x) O(n)O(n)
Info
  • La structure de données appelée « liste » dans le langage Python est implémentée à l’aide de tableaux dynamiques.

Remarque : Dans la suite de ce document, on va considérer que la liste Python tab, créé par l’instruction tab = [i for i in range(20)] est de longueur fixe. Elle se comporte alors comme un tableau.

Pourquoi la recherche d’un élément dans un tableau quelconque (non trié donc) est en O(N)O(N) ?

  1. Écrire le prédicat est_dans de spécification :
def est_dans(tab: List[int], n: int) -> bool:
    """
    Recherche si la valeur n est présente au moins une fois
    dans le tableau tab.
    Algorithme itératif.
    """
  1. Écrire un jeu de tests.

  2. (Facultatif) Écrire le prédicat est_dans_rec de spécification :

def est_dans_rec(tab: List[int], n: int, i: int = 0) -> bool:
    """
    Recherche si la valeur n est présente au moins une fois
    dans le tableau tab.
    Algorithme récursif, i est l'indice de recherche.
    """
  1. Quelle est la complexité des algorithmes précédents en fonction de NN, la taille du tableau ?
    Réponse
    • Dans l’algorithme itératif, dans le pire des cas (valeur absente du tableau) NN tours de boucle sont effectués.
    • Dans l’algorithme récursif, NN appels récursifs sont effectués.

    L’algorithme est donc en O(N)O(N).

Pourquoi l’insertion d’un élément dans un tableau est en O(N)O(N) ?

Dans cette partie, on imagine que le tableau a cette allure :

1 1 2 3 4 5 vide vide vide

Si on introduit, en position 1, la valeur 7. Le tableau est alors :

7 1 1 2 3 4 5 vide vide
Avertissement

Cette opération n’est possible, sans crainte de perdre des données, que si toutes les cellules du tableau ne contiennent pas des données. Toute fonction permettant l’insertion de valeurs doit donc avertir un utilisateur dans le cas contraire.

Remarque : Dans le code ci-dessous, les cellules seront considérées vides si elles contiennent la valeur None.

  1. Écrire la fonction insere dont la spécification est :
def insere(tab: List[int], n: int, i: int) -> None:
    """
    Insère la valeur n à l'indice i du tableau tab.
    Algorithm itératif et en place.

    Lève une exception si le tableau est déjà plein.

    HYPOTHÈSE : la gestion des "trous" n'est pas assurée,
    l'algorithme se contente de décaler les valeurs vers
    la droite.
    """
  1. (Facultatif) Écrire la fonction insere_rec dont la spécification est :
def insere_rec(tab: List[int], n: int, i: int, k: int) -> None:
    """
    Insère la valeur n à l'indice i du tableau tab.
    Algorithm récursif et en place. k est l'indice de recherche. Sa première valeur doit être len(tab) - 1.

    Lève une exception si le tableau est déjà plein.

    HYPOTHÈSE : la gestion des "trous" n'est pas assurée,
    l'algorithme se contente de décaler les valeurs vers
    la droite.
    """
  1. Quelle est la complexité des algorithmes précédents en fonction de NN, la taille du tableau ?
    Réponse
    • Dans le pire des cas (insertion à la première place du tableau), on déplace N−1N-1 valeurs.

    L’algorithme est donc en O(N)O(N).

Structure de liste chaînée

À retenir

Les listes chaînées constituent une structure de données :

  • de longueur modifiable ;
  • plus efficace que les tableaux lorsqu’il s’agit d’ajouter ou de retirer un élément (il n’est pas nécessaire de faire de la place en déplaçant les éléments) ;
  • qui servira de brique à l’élaboration d’autres structures de données.
À retenir

Une liste chaînée permet de représenter une liste ; chaque élément de cette liste est une cellule contenant :

  • la valeur de l’élément à stocker ;
  • l’adresse mémoire de la cellule représentant l’élément suivant.

Remarque : le symbole ⊥\perp marque la fin de la liste dans les schémas.

Comment implémenter une cellule ?

En langage Python, on peut implémenter une cellule à l’aide d’une classe, de listes ou de tuples.

  1. Définir la classe Cellule dont la spécification est :
class Cellule:
    """
    Implémentation d'une cellule de liste chaînée
    de nombres entiers.

    Attributs
    ---------
    valeur : int
        Valeur à stocker dans la liste
    suivante : Cellule
        Addresse de la cellule suivante (chaînée)
    """
Info

La dernière cellule d’une liste chaînée devra pointer vers l’objet None qui représente donc une cellule vide.

  1. Instancier 3 objets c1, c2, c3, de type Cellule, dont les valeurs sont 1, 2, 3. Tous ces objets sont pour l’instant isolés (ils ne pointent vers aucune autre cellule si ce n’est la cellule vide None).

  2. Créer la liste lst à l’aide de ces trois objets.

  3. Comment aurait-on pu créer la liste lst en une seule instruction ?

Les listes chaînées sont des structures fondamentalement récursives

À retenir

Une liste chaînée est :

  • soit la liste vide (objet None) ;
  • soit constituée de son premier élément (objet de type Cellule) et du reste des éléments qui forment aussi une liste. Une liste chaînée est donc une structure récursive.

Une liste chaînée est-elle forcément homogène

Tout au long de ce document nous allons uniquement envisager des listes chaînées de nombres entiers. Rien n’impose, cependant, à l’attribut valeur de la classe Cellule d’être un entier. Chaque cellule peut même posséder des attributs valeur de type différent. Les listes chaînées peuvent donc être hétérogènes.

Quelques opérations sur les listes chaînées

Avertissement

Le point de vue envisagé dans la suite de ce document est celui de la programmation impérative : nous allons définir des fonctions qui vont modifier la liste chaînée.
Nous créerons une classe enveloppe dans un prochain document, de façon à ce notre liste chaînée ait la même interface qu’une liste Python.

Longueur d’une liste chaînée

  1. Écrire la fonction longueur dont la spécification est :
def longueur(lst: Cellule) -> int:
    """
    Détermine la longueur de la liste lst.

    Algorithme récursif.
    """
  1. Écrire la fonction longueur_iter dont la spécification est :
def longueur_iter(lst: Cellule) -> int:
    """
    Détermine la longueur de la liste lst.

    Algorithme itératif.
    """
  1. Déterminer la complexité du calcul de la longueur d’une liste.
    Réponse

    On réalise autant d’appels récursifs (ou de tours de boucles qu’il y a d’éléments dans la liste).
    La complexité est donc en O(N)O(N).

Affichage de tous les éléments d’une liste

  1. Écrire la fonction affichage_elements_liste dont la spécification est :
def affichage_elements_liste(lst: Cellule) -> None:
    """
    Affiche tous les éléments de la liste lst.
    Chaque élément est séparé par une tabulation "\t"
    """
  1. Définir la fonction list_to_str dont la spécification est :
def list_to_str(lst: Cellule, premier: bool = True) -> str:
    """
    Retourne une chaîne de caractères constituée de toutes
    les valeurs, sous la forme : "[valeur1, valeur2, ...]".

    premier est positionné à True si la valeur est la première
    de la liste et à False pour toutes les autres valeurs.
    """

Valeur du n-ième élément d’une liste

  1. Écrire la fonction n_ieme_element dont la spécification est :
def n_ieme_element(lst: Cellule, i: int) -> int:
    """
    Retourne le n-ième élément de la liste. La convention
    suivie est celle de Python, le premier élément ayant
    l'indice i = 0.

    Algorithme récursif.

    Lève une exception si l'indice de la liste est trop grand.
    """
  1. Écrire la fonction n_ieme_element_iter dont la spécification est :
def n_ieme_element_iter(lst: Cellule, i: int) -> int:
    """
    Retourne le n-ième élément de la liste. La convention
    suivie est celle de Python, le premier élément ayant
    l'indice i = 0.

    Algorithme itératif.

    Lève une exception si l'indice de la liste est trop grand.
    """
  1. Déterminer la complexité de la recherche du n-ième élément d’une liste.
    Réponse
    • Si l’élément dont on cherche la valeur est le dernier de la liste il est nécessaire de faire NN appels récursifs (ou tours de boucles).
    • Si l’indice est hors des limites, il est ici aussi nécessaire de parcourir toute la liste avant de s’en rendre compte. L’algorithm est donc en O(N)O(N).

Modification de la valeur d’une cellule sans modifier la structure de la liste

  1. Écrire la fonction modifier_n_ieme_element dont la spécification est :
def modifier_n_ieme_element(lst: Cellule, i: int, valeur: int) -> None:
    """
    Modifie le n-ième élément de la liste. La convention
    suivie est celle de Python, le premier élément ayant
    l'indice i = 0.

    Algorithme récursif.

    Lève une exception si l'indice de la liste est trop grand.
    """

Ajout d’une valeur à la fin de la liste

  1. Écrire la fonction ajout_fin_liste dont la spécification est :
def ajout_fin_liste(lst: Cellule, valeur: int) -> None:
    """
    Ajout de valeur à la fin de la liste.
    La liste lst est modifiée.

    Algorithme récursif.
    """
  1. Quelle est la complexité de la fonction ajout_fin_liste ?
    Réponse

    On doit parcourir toute la liste pour ajouter un élément à la fin. La complexité est donc linéaire.

Ajout d’une valeur au début de la liste

  1. Écrire la fonction ajout_debut_liste dont la spécification est :
def ajout_debut_liste(lst: Cellule, valeur: int) -> Cellule:
    """
    Ajout de valeur au début de la liste.

    La nouvelle adresse de la tête de liste doit être
    retournée.
    """
  1. Quelle est la complexité de cette fonction ?
    Réponse

    O(1)O(1)

Retrait du dernier élément d’une liste

  1. Écrire la fonction retrait_dernier_element dont la spécification est :
def retrait_dernier_element(lst: Cellule) -> int:
    """
    Retire le dernier élément de la liste et le retourne.

    Algorithme récursif.
    """
  1. Quelle est la complexité de cette fonction ?
    Réponse

    Il faut parcourir la liste, donc O(N)O(N).

Retrait du premier élément d’une liste

  1. Écrire la fonction retrait_premier_element dont la spécification est :
def retrait_premier_element(lst: Cellule) -> tuple[int, Cellule]:
    """
    Retire le premier élément de la liste et le retourne.

    La nouvelle adresse de la tête de liste doit être
    retournée.
    """
  1. Quelle est la complexité de cette fonction ?
    Réponse

    O(1)O(1).

Retrait du n-ième élément d’une liste

  1. Écrire la fonction retrait_n_ieme_element dont la spécification est :
def retrait_n_ieme_element(lst: Maillon, i: int) -> int:
    """
    Retire le n-ième élément de la liste lst. La convention
    suivie est celle de Python, le premier élément ayant
    l'indice i = 0.
    
    Algorithme récursif.
    
    Lève une exception si l'indice de la liste est trop grand,
    ne prend pas en charge le retrait du premier élément.
    """
  1. Quelle est la complexité de cette fonction ?
    Réponse

    Le retrait en lui-même est en O(1)O(1) mais il faut arriver jusqu’à la valeur. L’ensemble est donc en O(N)O(N).

Concaténation de deux listes

À retenir

On appelle concaténation de deux listes l’opération consistant à mettre bout à bout les deux listes.

  1. Écrire la fonction concatener dont la spécification est :
def concatener(lst1: Cellule, lst2: Cellule) -> Cellule:
    """
    Concatène les listes lst1 et lst2. Une nouvelle liste est
    créée et retournée.
    Les éléments de la première liste sont copiés alors que ceux
    de la deuxième sont insérés. lst1 et lst2 ne sont donc pas modifiées.

    ATTENTION : tout élément de lst partagé avec lst2 modifié l'est aussi
    dans lst2.

    Algorithme récursif.
    """
  1. Écrire la fonction copie dont la spécification est :
def copie(lst: Cellule) -> Cellule:
    """
    Réalise une nouvelle copie de la liste lst.

    Algorithme récursif.
    """
  1. Se servir de la fonction copie pour écrire la fonction concatener_avec_copie_integrale dont la spécification est :
def concatener_avec_copie_integrale(lst1: Cellule, lst2: Cellule) -> Cellule:
    """
    Concatène les listes lst1 et lst2. Les éléments des listes lst1 et lst2
    sont recopiés pour former une nouvelle liste.
    
    Algorithme récursif.
    """
  1. Quelle est la complexité de la fonction concatener ? Même question pour la fonction concatener_avec_copie_integrale.
    Réponse
    • Dans le premier cas, il est nécessaire de recopier tous les éléments de lst1. La complexité est donc linéaire et dépend du nombre d’élements de lst1.
    • Dans le second cas, on recopie tous les éléments de lst1 et de lst2. La complexité est donc linéaire et est la somme du nombre d’éléments de lst1 et de lst2.

Renverser une liste

  1. Écrire la fonction renverser dont la spécification est :
def renverser(lst: Cellule) -> Cellule:
    """
    Retourne une nouvelle liste formée des éléments de lst à l'envers.
    Les éléments peuvent avoir été recopiés ou pas.

    Algorithme récursif.
    """

Remarque. Cette fonction doit s’appuyer sur les fonctions concatener ou concatener_avec_copie_integrale.

Remarque. Cet algorithme est particulièrement inefficace.

Conclusion

À retenir
  • Une liste chaînée est une structure de données utile pour représenter une séquence finie d’éléments.
  • Chaque élément est contenu dans une cellule, qui fournit, en plus de la valeur, un moyen pour accéder à la cellule suivante.
  • Les éléments d’une liste chaînée ne sont pas situés dans des emplacements contigüs en mémoire.
  • Les opérations sur les listes chaînées se programment sous la forme de parcours qui suivent ces liaisons, en utilisant la récursivité ou des boucles.
À retenir

Une liste chaînée est un type abstrait de données qui doit, au minimum, fournir les fonctions suivantes :

  • insère : insère un élément dans la liste ;
  • supprime : supprime et renvoie l’élément de position spécifié de la liste ;
  • longueur : renvoie le nombre d’éléments de la liste ;
  • est_vide : détermine si la liste est vide ou pas ;
  • nième_élément : retourne la valeur du nième élément depuis le début.
Action Liste chaînée Tableau Tableau dynamique
Accès à un élément O(n)O(n) O(1)O(1) O(1)O(1)
Insertion/suppression du 1er élément O(1)O(1) O(n)O(n) (si place) O(n)O(n)
Insertion à la fin O(n)O(n) O(1)O(1) (si place) O(1)O(1) (si place)
O(n)O(n) (si pas de place)
Suppression du dernier élément O(n)O(n) O(1)O(1) O(1)O(1)
Insertion/suppression au milieu O(n)O(n) O(n)O(n) (si place) O(n)O(n)

Quelques exemples d’utilisation des listes chaînées

  • Les logiciels de visualisation d’images utilisent parfois une liste chaînée pour afficher les images précédentes et suivantes à l’aide des boutons « précédent » et « suivant ».

  • Des navigateurs Web peuvent utiliser une liste chaînée pour accéder aux pages à l’aide des boutons « précédent » et « suivant ».

  • Les boutons « précédent » et « suivant » des lecteurs de musique peuvent utiliser une liste chaînée doublement/circulaire.

  • Les tracés et les formes sur le canevas, de MS-Paint sont connectés via une liste chaînée.

  • Le balayage « gauche/droite » sur Tinder utilise une liste doublement chaînée.

  • On peut garder la trace des tours dans un jeu multi-joueurs à l’aide d’une liste chaînée circulaire.

  • Les lignes de code dans un IDE peuvent être enregistrées dans une liste doublement chaînée.

Annexe : Tests possibles pour les fonctions codées

if __name__ == "__main__":
    # c1 = Cellule(1, None)
    # c2 = Cellule(2, None)
    # c3 = Cellule(3, None)
    # lst = c1
    # lst.suivante = c2
    # c2.suivante = c3

    lst = Cellule(1, Cellule(2, Cellule(3, Cellule(4, None))))
    affichage_elements_liste(lst)

    assert longueur(lst) == 4
    assert longueur_iter(lst) == 4

    assert n_ieme_element(lst, 0) == 1
    assert n_ieme_element(lst, 3) == 4
    # print(n_ieme_element(lst, 4))

    assert n_ieme_element_iter(lst, 0) == 1
    assert n_ieme_element_iter(lst, 3) == 4
    # print(n_ieme_element_iter(lst, 4))

    lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, None))))
    lst2 = Cellule(5, Cellule(6, Cellule(7, None)))
    lst3 = concatener_avec_copie_integrale(lst1, lst2)
    print(lst3)
    print(list_to_str(lst3))

    # Modification de la liste
    modifier_n_ieme_element(lst, 0, 12)
    assert n_ieme_element_iter(lst, 0) == 12

    # Ajout en fin de liste
    ajout_fin_liste(lst, Cellule(25, None))
    affichage_elements_liste(lst)
    print(list_to_str(lst))

    # Ajout en début de liste
    lst = ajout_debut_liste(lst, Cellule(34, None))
    affichage_elements_liste(lst)

    # Retrait dernier élément
    dernier = retrait_dernier_element(lst)
    print(dernier)
    affichage_elements_liste(lst)
Physique, Chimie et Informatique > Terminales Spé. NSI > Listes chaînées

Implémentation du type abstrait Liste Chaînée à l'aide de listes Python

Reprendre toutes les fonctions des sections 2 et 3 du document 1 de ce chapitre, en implémentant cette fois le type abstrait « Liste chaînée » à l’aide de tuples (à la place de la classe).

Réponse
def est_dans(tab: list[int], val: int) -> bool:
    """
    Recherche la présence de val dans tab.
    """
    trouve = False

    i = 0
    while i < len(tab) and not trouve:
        if val == tab[i]:
            trouve = True
        i += 1

    return trouve


def est_dans_rec(tab: list[int], n: int, i: int = 0) -> bool:
    """
    Recherche si la valeur n est présente au moins une fois
    dans le tableau tab.
    Algorithme récursif, i est l'indice de recherche.
    """
    if i == len(tab):
        return False
    elif tab[i] == n:
        return True
    else:
        return est_dans_rec(tab, n, i + 1)


def insere(tab: list[int], n: int, i: int) -> None:
    """
    Insère la valeur n à l'indice i du tableau tab.
    Algorithm itératif et en place.

    Lève une exception si le tableau est déjà plein.

    HYPOTHÈSE : la gestion des "trous" n'est pas assurée,
    l'algorithme se contente de décaler les valeurs vers
    la droite.
    """
    dernier_indice = len(tab) - 1

    if tab[dernier_indice] != None:
        raise Exception("Tableau plein !")

    k = dernier_indice
    while k > i:
        tab[k] = tab[k - 1]
        k -= 1

    # for k in range(dernier_indice, i, -1):
    #    tab[k] = tab[k - 1]

    tab[i] = n


def insere_rec(tab: list[int], n: int, i: int, k: int) -> None:
    """
    Insère la valeur n à l'indice i du tableau tab.
    Algorithm récursif et en place. k est l'indice de
    recherche.
    Sa première valeur doit être len(tab) - 1.

    Lève une exception si le tableau est déjà plein.

    HYPOTHÈSE : la gestion des "trous" n'est pas
    assurée, l'algorithme se contente de décaler
    les valeurs vers la droite.
    """
    dernier_indice = len(tab) - 1

    if tab[dernier_indice] != None and k == dernier_indice:
        raise Exception("Tableau plein !")
    elif k == i:
        tab[i] = n
        return None
    else:
        tab[k] = tab[k - 1]
        return insere_rec(tab, n, i, k - 1)


if __name__ == "__main__":
    tab = [i for i in range(20)]

    assert est_dans(tab, 12) == True
    assert est_dans(tab, 0) == True
    assert est_dans(tab, 20) == False

    assert est_dans_rec(tab, 12) == True
    assert est_dans_rec(tab, 0) == True
    assert est_dans_rec(tab, 20) == False

    print("Insertion itérative")
    tab = [1, 1, 2, 3, 4, 5, None, None, None]
    print(tab)
    insere(tab, 7, 0)
    print(tab)
    insere(tab, 7, 0)
    print(tab)
    insere(tab, 7, 0)
    print(tab)
    # insere(tab, 7, 0)
    # print(tab)
    print()
    print("Insertion récursive")
    tab = [1, 1, 2, 3, 4, 5, None, None, None]
    print(tab)
    insere_rec(tab, 7, 0, len(tab) - 1)
    print(tab)
    insere_rec(tab, 7, 0, len(tab) - 1)
    print(tab)
    insere_rec(tab, 7, 0, len(tab))
    print(tab)
Physique, Chimie et Informatique > Terminales Spé. NSI > Listes chaînées

Réalisation d'une classe Liste Chainee

Par transformation des fonctions du document 1 dans ce chapitre en méthodes, écrire le code de la classe Liste qui définit le type abstrait « Liste chaînée ».

Réponse
from __future__ import annotations


class Maillon:
    """
    Un maillon de la liste.
    """

    def __init__(self: Maillon, valeur: int, suivant: Maillon = None) -> None:
        self.valeur = valeur
        self.suivant = suivant


class Liste:
    """
    Implémentation de la classe liste.
    """

    def __init__(self: Liste, valeur: int = None) -> None:
        """
        Initialisation de l'objet. Il est possible de créer une liste
        vide ou une liste contenant un élément.

        Il est possible de créer directemnt une liste contenant plusieurs
        éléments il faut utiliser une fonctionnalité de Python que vous
        ne connaissez pas forcément et qui n'est pas au programme.
        """
        if valeur is None:
            self.maillons = None
        else:
            self.maillons = Maillon(valeur)

    def est_vide(self: Liste) -> bool:
        """Détermine si la liste est vide."""
        return self.maillons is None

    def __len__(self: Liste) -> int:
        """Retourne le nombre d'éléments dans la liste."""
        if self.est_vide():
            return 0
        else:
            nbre = 0
            maillon = self.maillons
            while maillon is not None:
                nbre += 1
                maillon = maillon.suivant
            return nbre

    def append(self: Liste, valeur: int) -> None:
        """
        Ajoute valeur à la fin de la liste.
        """
        if self.est_vide():
            self.maillons = Maillon(valeur)
        else:
            maillon = self.maillons
            while maillon.suivant is not None:
                maillon = maillon.suivant

            maillon.suivant = Maillon(valeur)

    def append_first(self: Liste, valeur: int) -> None:
        """
        Ajoute valeur au début de la liste.
        """
        maillon = Maillon(valeur)
        maillon.suivant = self.maillons
        self.maillons = maillon

    def pop(self: Liste) -> int:
        """
        Retire le dernier élément de la liste et le retourne.

        Lève une erreur si la liste est vide.
        """
        if self.est_vide():  # Liste vide
            raise Exception("La liste est vide !")

        maillon = self.maillons
        if maillon.suivant is None:  # Cas d'une liste à un élément
            valeur = maillon.valeur
            self.maillons = None
            return valeur
        else:
            while maillon.suivant.suivant is not None:  # Cas général
                maillon = maillon.suivant
            valeur = maillon.suivant.valeur
            maillon.suivant = None
            return valeur

    def pop_first(self: Liste) -> int:
        """
        Retire le premier élément de la liste et le retourne.

        Lève une erreur si la liste est vide.
        """
        if self.est_vide():  # Liste vide
            raise Exception("La liste est vide !")

        valeur = self.maillons.valeur
        self.maillons = self.maillons.suivant
        return valeur

    def __getitem__(self: Liste, i: int) -> int:
        """
        Redéfinition de la fonction d'accès à l'élément d'indice i.
        """
        if self.est_vide():
            raise Exception("La liste est vide !")

        maillon = self.maillons
        j = 0
        while j < i:
            if maillon is None:
                raise IndexError("Indice hors des limites !")
            maillon = maillon.suivant
            j += 1
        return maillon.valeur

    def __str__(self: Liste) -> str:
        """
        Représentation de la liste sous-forme d'une chaîne de caractères.
        """
        rep = "["

        maillon = self.maillons
        while maillon is not None:
            rep += str(maillon.valeur)
            if maillon.suivant is not None:
                rep += ", "
            maillon = maillon.suivant

        rep += "]"
        return rep