Liste chaînée (Bac 🎯)

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.

Sources et crédits pour ce cours

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

• le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
• le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
• la ressource Eduscol sur les types de données
• le cours de mon collègue Pierre Duclosson

🔖 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")

Exercice 5

💻 Saisir ses réponses sur Capytale

Question 1

énoncésolution

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

🐍 Script Python

liste = creer_liste()
liste = inserer(liste, 3)
liste = inserer(liste, 2)
liste = inserer(liste, 1)

Question 2

énoncésolution

É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

énoncésolution

É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

énoncésolution

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.

###

Lancer Télécharger Téléverser Recharger Sauvegarder

def creerpy-undliste():bksl-nl return Nonebksl-nlbksl-nldef listepy-undvide(lis):bksl-nl return lis is Nonebksl-nlbksl-nldef inserer(lis, elt):bksl-nl """Insère elt en tête de lis et renvoie la liste créée"""bksl-nl # à compléterbksl-nl ...bksl-nlbksl-nlbksl-nldef tete(lis):bksl-nl """Renvoie l'élément en tête de la liste lis"""bksl-nl # à compléterbksl-nl ...bksl-nlbksl-nldef queue(lis):bksl-nl """Renvoie une liste qui est la queue de lis"""bksl-nl # à compléterbksl-nl ...bksl-nlbksl-nldef test():bksl-nl lis = creerpy-undliste()bksl-nl assert listepy-undvide(lis)bksl-nl for k in range(0, 3):bksl-nl lis = inserer(lis, k)bksl-nl assert lis == (2, (1, (0, None)))bksl-nl print("Tests réussis")bksl-nl

🐍 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.

énoncésolution

🐍 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

énoncésolution

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.

###

Lancer Télécharger Téléverser Recharger Sauvegarder

class Cellule:bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self, elt, suivant):bksl-nl self.element = eltbksl-nl self.suivant = suivantbksl-nl bksl-nldef creerpy-undliste():bksl-nl return Nonebksl-nlbksl-nldef listepy-undvide(lis):bksl-nl return lis is Nonebksl-nlbksl-nldef inserer(lis, elt):bksl-nl """Insère elt en tête de lis et renvoie la liste créée"""bksl-nl # à compléterbksl-nl ...bksl-nlbksl-nlbksl-nldef tete(lis):bksl-nl """Renvoie l'élement en tête de la liste lis"""bksl-nl # à compléterbksl-nl ...bksl-nlbksl-nldef queue(lis):bksl-nl """Renvoie une liste qui est la queue de lis"""bksl-nl # à compléterbksl-nl ...bksl-nlbksl-nlbksl-nldef test():bksl-nl lis = None bksl-nl assert listepy-undvide(lis)bksl-nl for k in range(0, 3):bksl-nl lis = inserer(lis, k)bksl-nl assert lis.element == 2bksl-nl lis = lis.suivantbksl-nl assert lis.element == 1bksl-nl lis = lis.suivantbksl-nl assert lis.element == 0bksl-nl print("Tests réussis")bksl-nl bksl-nl

🐍 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