Aller au contenu

Liste chaînée (Bac 🎯)⚓︎

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

🔖 Synthèse de ce qu'il faut retenir pour le bac

Définition⚓︎

Point de cours 4

On représente en général une liste comme une chaîne de cellules reliées par des flèches, on parle de liste chaînée.

Chaque cellule est un couple qui porte deux informations :

  • un élément
  • un lien vers la cellule suivante

On alors peut définir le type abstrait Liste récursivement. Une liste est :

  • soit vide
  • soit une cellule portant un élément appelée la tête de la liste, et un lien vers une autre liste appelée queue de la liste.

Exemple 3

On a représenté ci-dessous une liste avec une chaîne de trois cellules contenant les caractères "N", "S" et "I". Notez que l'élément en tête de liste est le dernier inséré. Par ailleurs, inserer(liste, element) ajoute element en tête de liste et renvoie la nouvelle liste obtenue.

🐍 Script Python
liste = creer_liste()
liste = inserer(liste, "I")
liste = inserer(liste, "S")
liste = inserer(liste, "N")

liste

Exercice 5

💻 Saisir ses réponses sur Capytale

Question 1

Comment créer une liste qui contient les éléments 1, 2, 3 dans cet ordre (en partant de la tête) ?

liste

🐍 Script Python
liste = creer_liste()
liste = inserer(liste, 3)
liste = inserer(liste, 2)
liste = inserer(liste, 1)

Question 2

Étendre l'interface du type abstrait Liste avec une fonction longueur(lis) qui renvoie la longueur de la liste passée en paramètre.

Écrire une version itérative et une version récursive.

Version récursive :

🐍 Script Python
def longueur(lis):
    if liste_vide(lis):
        return 0
    return 1 + longueur(queue(lis))

Version itérative :

🐍 Script Python
def longueur(lis):
    courant = lis
    while not liste_vide(courant):
        courant = queue(courant)
        n = n + 1
    return n

Question 3

Étendre l'interface du type abstrait Liste avec une fonction inverser(lis) qui renvoie une nouvelle liste où les éléments sont dans l'ordre inverse de celui de la liste lis passée en paramètre.

Version itérative :

🐍 Script Python
def inverser(lis):
    lis2 = creer_liste()
    courant = lis
    while not liste_vide(courant):
        lis2 = inserer(lis2, tete(courant))
        courant = queue(courant)
    return lis2

Version récursive avec un accumulateur.

🐍 Script Python
def inverser(lis):

    def auxiliaire(lis, acc):
        """Fonction récursive auxiliaire"""
        if liste_vide(lis):
            return acc
        acc = inserer(acc, tete(lis))
        return auxiliaire(queue(lis), acc)

    return auxiliaire(lis, creer_liste())

Implémentation⚓︎

Méthode 3

Pour implémenter une liste chaînée, il faut une structure de données permettant de représenter une cellule. Voici deux solutions :

Implémentation avec tuples

Une cellule est représentée par un tuple, la première composante porte l'élément et la seconde un lien vers une autre cellule. La dernière cellule porte un lien vers un objet représentant une cellule vide, par exemple None ou (). On implémente alors la liste chaînée de l'exemple 2 par lis = ("N", ("S", ("I", None))).

Implémentation avec une classe Cellule

Une cellule est représentée par un objet de la classe Cellule, qui possède deux attributs : element portant l'élément et suivant portant le lien vers la cellule suivante dans la liste chaînée. On implémente alors la liste chaînée de l'exemple 3 par :

🐍 Script Python
class Cellule:

    def __init__(self, elt, suivant):
        self.element = elt
        self.suivant = suivant


lis1 = Cellule("N", Cellule("S", Cellule("I", None)))

Attention

Une liste est définie par un lien vers la cellule en tête d'une chaîne de cellules. Cependant la classe Cellule ou le type tuple ne sont pas suffisants pour représenter le type abstrait Liste. En effet une liste peut être vide, mais pas une cellule qui porte toujours deux informations.

Complexité temporelle

Pour les deux implémentation de liste chaînée avec tuple ou classe Cellule, on a les mêmes complexités temporelles par rapport au nombre \(n\) d'éléments dans la liste. Le seul élément accessible directement est la tête, en temps constant. Le coût d'un parcours complet de la liste en suivant le chaînage est linéaire, proportionnel à la taille de la liste.

Opération Type complexité Notation de Landau
inserer, tete ou queue constante \(O(1)\)
parcours de toute la liste linéaire \(O(n)\)

Exercice 6

💻 Saisir ses réponses sur Capytale

Question 1

Complétez l'implémentation du type abstrait Liste avec une liste chaînée où les cellules sont représentées par des tuples et la liste vide par None.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞

🐍 Script Python
def creer_liste():
    return None

def liste_vide(lis):
    return lis is None

def inserer(lis, elt):
    return (elt, lis)

def tete(lis):
    return lis[0]

def queue(lis):
    return lis[1]

def test():
    lis = creer_liste()
    assert liste_vide(lis)
    for k in range(0, 3):
        lis = inserer(lis, k)
    assert lis == (2, (1, (0, None)))
    print("Tests réussis")

Question 2

On considère l'implémentation du type abstrait Liste avec une liste chaînée où les cellules sont des objets de la classe Cellule et la liste vide est représentée par None.

🐍 Script Python
class Cellule:

        def __init__(self, elt, suivant):
            self.element = elt
            self.suivant = suivant

On crée la liste chaînée suivante :

🐍 Script Python
lis = Cellule(8, Cellule(4, Cellule(3, None)))

Que vaut lis.element ? et lis.suivant ? et lis.suivant.element ?

Comment peut-on accéder à l'élément 3 ?

On crée la liste chaînée suivante :

🐍 Script Python
lis = Cellule(8, Cellule(4, Cellule(3, None)))
  • lis.element vaut 8
  • lis.suivant vaut Cellule(4, Cellule(3, None))
  • lis.suivant.element vaut 4
  • On accède à l'élément 3 par lis.suivant.suivant.element

Question 3

Complétez l'implémentation du type abstrait Liste avec une liste chaînée où les cellules sont des objets de la classe Cellule et la liste vide est représentée par None.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞

🐍 Script Python
class Cellule:

    def __init__(self, elt, suivant):
        self.element = elt
        self.suivant = suivant
    
    def __str__(self):
        if self.suivant is None:
            return f"({self.element},None)"
        return f"({self.element},{str(self.suivant)})"

def creer_liste():
    return None

def liste_vide(lis):
    return lis is None

def inserer(lis, elt):
    
    return Cellule(elt, lis)

def tete(lis):
    return lis.element

def queue(lis):
    return lis.suivant