Liste chaînée

• Le diaporama du cours

Résumé du cours

Principe

Dans une liste chaînée, chaque élément :

• prend une place libre quelconque en mémoire.
• connaît l’emplacement de l’élément suivant.

Dans une liste chaînée, ajouter un élément se fait en temps constant. Par contre, pour lire l’élément de rang n, la complexité est linéaire en n.

Interface

L’interface d’une liste chaînée propose les fonctionnalités pour utiliser la structure :

• vérifier si la liste est vide,
• renvoyer la taille de la liste,
• renvoyer l’élément de rang n,
• insérer un élément.

Implémentation

La programmation orientée objet est un choix d’implémentation possible. Il n’est pas unique.

class Maillon:
    """
    Crée un maillon de la liste chaînée
    """

    def __init__(self, val: int, suiv: object):
        self.valeur = val
        self.suivant = suiv

class Liste:
    """
    Crée une liste chaînée
    """

    def __init__(self):
        # selt.tete référence un Maillon
        self.tete = None

Les méthodes ajoutées à l’objet Liste implémenteront l’interface proposée.

class Liste:
    """
    Crée une liste chaînée
    """

    def __init__(self):
        # selt.tete référence un Maillon
        self.tete = None

    def est_vide(self) -> bool:
        return self.tete is None

    def ajouter(self, val: int) -> None:
        self.tete = Maillon(val, self.tete)