Exercices : listes chaînées

Exercice 1 — QCM : vocabulaire des listes chaînées

Pour chaque question, une seule réponse est correcte.

1. Dans une liste chaînée, chaque nœud contient :

  • A. uniquement une valeur
  • B. une valeur et une référence vers le nœud suivant
  • C. une valeur, une référence vers le suivant et une référence vers le précédent
  • D. une valeur et son indice dans la liste

Correction publiée après la séance.

2. Pour représenter une liste vide, on utilise :

  • A. un nœud dont la valeur est 0
  • B. un nœud dont la valeur est None
  • C. un objet ListeChainee dont l’attribut premier vaut None
  • D. la valeur []

Correction publiée après la séance.

3. Quelle est la complexité de l’ajout en tête d’une liste chaînée ?

  • A. \(O(n)\) car il faut décaler tous les éléments
  • B. \(O(1)\) car on crée un nœud et on met à jour une référence
  • C. \(O(n)\) car il faut parcourir la liste pour trouver la tête
  • D. \(O(\log n)\) car on utilise une recherche dichotomique

Correction publiée après la séance.

4. On considère la liste chaînée 5 → 3 → 8 → None. Quelle expression Python permet d’accéder à la valeur 8 ?

  • A. ma_liste.premier.element
  • B. ma_liste.premier.suivant.element
  • C. ma_liste.premier.suivant.suivant.element
  • D. ma_liste.ieme_element(3)

Correction publiée après la séance.

5. Par rapport au type list de Python (tableau dynamique), la liste chaînée est plus performante pour :

  • A. l’accès à un élément par son indice
  • B. les insertions et suppressions en tête
  • C. la recherche d’un élément
  • D. le calcul de la longueur

Correction publiée après la séance.

Exercice 2 — Exercice guidé : manipuler une liste chaînée pas à pas

On rappelle les classes vues en cours :

class Noeud:
    def __init__(self, element, suivant=None):
        self.element = element
        self.suivant = suivant

class ListeChainee:
    def __init__(self):
        self.premier = None

    def ajout_en_tete(self, element):
        nouveau = Noeud(element)
        nouveau.suivant = self.premier
        self.premier = nouveau

    def ajout_en_queue(self, element):
        """Insère element en queue de liste"""
        if self.premier == None:
            self.ajout_en_tete(element)
        else:
            courant = self.premier
            while courant.suivant != None:
                courant = courant.suivant
            dernier = Noeud(element)
            courant.suivant = dernier

On exécute les instructions suivantes :

ma_liste = ListeChainee()
ma_liste.ajout_en_tete(7)
ma_liste.ajout_en_tete(3)
ma_liste.ajout_en_tete(9)

  1. Dessiner l’état de la liste chaînée après chaque instruction ajout_en_tete. On représentera chaque nœud par une case contenant la valeur et une flèche vers le suivant.

    Indice

    ajout_en_tete crée un nœud dont le suivant est l’ancien premier nœud, puis en fait le nouveau premier : chaque nouvelle valeur se place devant les autres.

  2. Quelle est la valeur de ma_liste.premier.element ?

    Indice

    premier désigne le nœud de tête, celui du dernier ajout en tête.

  3. Quelle est la valeur de ma_liste.premier.suivant.suivant.element ?

    Indice

    Chaque .suivant avance d’un nœud : partir de la tête du dessin et avancer deux fois.

  4. On ajoute maintenant ma_liste.ajout_en_tete(1). Dessiner le nouvel état de la liste.

Correction publiée après la séance.

Exercice 3 — Exercice guidé : compléter des méthodes à trous

On reprend les classes Noeud et ListeChainee. Compléter les méthodes suivantes en remplaçant les ... par le code approprié.

a) Méthode __len__ qui renvoie le nombre d’éléments de la liste :

def __len__(self):
    courant = ...          # partir du premier nœud
    cpt = 0
    while courant:
        courant = ...      # passer au nœud suivant
        cpt += 1
    return ...             # renvoyer le compteur
Indice

self.premier est le premier nœud et courant.suivant le nœud qui suit courant. La boucle s’arrête quand courant vaut None, c’est-à-dire après le dernier nœud.

b) Méthode __repr__ qui renvoie une représentation sous la forme "9 → 3 → 7" :

def __repr__(self):
    elements = []
    courant = self.premier
    while courant:
        elements.append(str(...))     # ajouter la valeur du nœud
        courant = ...                  # passer au suivant
    return " → ".join(elements)
Indice

La valeur d’un nœud est son attribut element ; on avance de nœud en nœud comme dans __len__.

c) Méthode contient qui renvoie True si element est dans la liste, False sinon :

def contient(self, element):
    courant = self.premier
    while courant:
        if ... == element:   # comparer avec la valeur du nœud
            return True
        courant = ...        # passer au suivant
    return ...               # élément non trouvé
Indice

Comparer courant.element à element. Si la boucle se termine sans l’avoir trouvé, l’élément n’est pas dans la liste.

Correction publiée après la séance.

Exercice 4 — Accès et suppression en tête

  1. Écrire la méthode supprime_en_tete(self) qui supprime le premier élément de la liste et renvoie sa valeur. Si la liste est vide, la méthode doit lever une exception ValueError("liste vide").

    Indice

    Si self.premier vaut None, la liste est vide : lever l’exception avec raise ValueError("liste vide"). Sinon, garder la valeur du premier nœud, faire du nœud suivant la nouvelle tête, puis renvoyer la valeur gardée.

    Code à copier puis compléter
        def supprime_en_tete(self):
        if self.premier == None:
            raise ValueError("liste vide")
        valeur = self.premier.element
        self.premier = ...
        return ...

  2. Tester votre méthode sur la liste 9 → 3 → 7 :

    • appeler supprime_en_tete() une première fois : quelle valeur est renvoyée ? Quel est l’état de la liste ?
    • appeler supprime_en_tete() deux fois de plus : quelles valeurs sont renvoyées ?
    • un dernier appel : que se passe-t-il ?
    Indice

    Construire la liste avec trois appels à ajout_en_tete, en ajoutant 7, puis 3, puis 9, et afficher la liste après chaque suppression. Le dernier appel porte sur une liste vide : relire ce que la méthode doit faire dans ce cas.

Correction publiée après la séance.

Exercice 5 — Insertion en position quelconque

Écrire la méthode inserer(self, element, i) qui insère element en position i dans la liste (les positions sont comptées à partir de 0).

Indications :

  • si i == 0, il suffit d’utiliser ajout_en_tete ;
  • sinon, parcourir la liste jusqu’au nœud de position i - 1 (le futur prédécesseur) ;
  • créer un nouveau nœud dont le suivant est l’ancien nœud en position i ;
  • mettre à jour le suivant du nœud en position i - 1.

Tester avec la liste 9 → 3 → 7 :

  • inserer(5, 0) doit donner 5 → 9 → 3 → 7 ;
  • inserer(1, 2) doit donner 5 → 9 → 1 → 3 → 7.
Indice

Les indications donnent la marche à suivre. Pour atteindre le nœud de position i - 1, partir de self.premier et avancer i - 1 fois avec courant = courant.suivant.

Code à copier puis compléter
    def inserer(self, element, i):
        if i == 0:
            self.ajout_en_tete(element)
        else:
            courant = self.premier
            for _ in range(i - 1):
                courant = ...
            courant.suivant = Noeud(element, ...)

Correction publiée après la séance.

Exercice 6 — Comparaison de complexité

Compléter le tableau suivant en indiquant la complexité de chaque opération pour les deux structures :

Opérationlist Python (tableau)Liste chaînée
Accès à l’élément d’indice i
Ajout en tête
Ajout en queue
Suppression en tête
Suppression en queue
Recherche d’un élément
Indice

Le tableau Python accède directement à la case d’indice i, mais doit décaler tous les éléments quand on insère ou supprime au début. La liste chaînée n’accède directement qu’à son premier nœud : atteindre un autre nœud demande de parcourir la liste depuis la tête.

Correction publiée après la séance.

Exercice 7 — Synthèse : ajouter en queue en temps constant

Dans la classe ListeChainee de l’exercice 2, la méthode ajout_en_queue parcourt toute la liste pour atteindre le dernier nœud. On écrit une nouvelle classe, ListeAvecDernier, qui garde en plus une référence dernier vers le dernier nœud. Quand la liste est vide, premier et dernier valent tous les deux None.

a) Quelle est la complexité de la méthode ajout_en_queue de la classe ListeChainee ? Pourquoi ?

Indice

Que fait la boucle while avant d’accrocher le nouveau nœud ? Combien de tours fait-elle pour une liste de \(n\) éléments ?

b) Compléter les méthodes de la classe ListeAvecDernier, pour que ajout_en_queue s’exécute en temps constant et que dernier désigne toujours le dernier nœud :

class ListeAvecDernier:
    def __init__(self):
        self.premier = None
        self.dernier = None

    def ajout_en_queue(self, element):
        nouveau = Noeud(element)
        if self.dernier == None:
            self.premier = ...
        else:
            self.dernier.suivant = ...
        self.dernier = ...

    def ajout_en_tete(self, element):
        nouveau = Noeud(element, self.premier)
        self.premier = nouveau
        if ...:
            self.dernier = ...

    def supprime_en_tete(self):
        """Retire le premier nœud d'une liste non vide et renvoie son élément."""
        element = self.premier.element
        self.premier = ...
        if ...:
            self.dernier = ...
        return element
Indice

Si la liste n’a pas de dernier nœud, elle est vide : un nœud ajouté, en tête comme en queue, est alors à la fois le premier et le dernier. Après une suppression en tête, la liste est devenue vide quand premier vaut None : il n’y a plus de dernier nœud non plus.

c) Dans supprime_en_tete, que se passerait-il si l’on ne remettait pas dernier à None quand la liste devient vide ? Dérouler la suite d’opérations suivante.

l = ListeAvecDernier()
l.ajout_en_queue(5)
l.supprime_en_tete()
l.ajout_en_queue(8)
Indice

Après la suppression du seul nœud, premier vaut None. Vers quel nœud dernier pointe-t-il encore ? Que fait alors ajout_en_queue(8) ?

d) Garder une référence vers le dernier nœud ne rend pas la suppression en queue plus rapide. Pourquoi ?

Indice

Pour retirer le dernier nœud, quel nœud faut-il modifier ? Peut-on l’atteindre depuis dernier ?

Correction publiée après la séance.

Chapitres liés