Exercices : listes chaînées

B. Dans une liste simplement chaînée, chaque nœud contient une valeur (element) et une référence vers le nœud suivant (suivant). A est incomplet (il manque la référence). C décrit une liste doublement chaînée, ce qui n’est pas la structure étudiée ici. D décrit un tableau indexé, pas une liste chaînée.

C. La classe ListeChainee gère le cas de la liste vide grâce à son attribut premier qui vaut None. A et B créent un nœud, donc une liste à un élément. D utilise le type list de Python (tableau dynamique), pas une liste chaînée.

B. L’ajout en tête se fait en temps constant : on crée un nouveau nœud, on le fait pointer vers l’ancien premier, et on met à jour self.premier. Il n’y a pas de décalage (A est le cas d’un tableau), pas de parcours (C est faux : la tête est directement accessible via self.premier), et la dichotomie (D) ne s’applique pas ici.

C. Le premier nœud contient 5, premier.suivant contient 3, premier.suivant.suivant contient 8. A donne 5 (premier élément). B donne 3 (deuxième élément). D provoque une erreur car les indices vont de 0 à 2 (il n’y a pas d’indice 3).

B. Les insertions et suppressions en tête sont en \(O(1)\) pour une liste chaînée, contre \(O(n)\) pour un tableau dynamique (qui doit décaler tous les éléments). L’accès par indice (A) est en \(O(1)\) pour un tableau contre \(O(n)\) pour une liste chaînée. La recherche (C) et le calcul de longueur (D) sont en \(O(n)\) dans les deux cas.

1. Après chaque instruction :

   • ajout_en_tete(7) : [7] → None
   • ajout_en_tete(3) : [3] → [7] → None
   • ajout_en_tete(9) : [9] → [3] → [7] → None

   L’ajout en tête place le nouvel élément avant l’ancien premier. L’ordre final est donc l’inverse de l’ordre d’insertion.

2. ma_liste.premier.element vaut 9 (le dernier élément ajouté en tête).

3. ma_liste.premier est le nœud contenant 9, .suivant est le nœud contenant 3, .suivant est le nœud contenant 7. Donc la valeur est 7.

4. Après ajout_en_tete(1) : [1] → [9] → [3] → [7] → None.

a)

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

Le parcours suit le schéma classique : on part du premier nœud, on avance de nœud en nœud avec courant = courant.suivant, et on s’arrête quand courant vaut None (fin de la chaîne).

b)

def __repr__(self):
    elements = []
    courant = self.premier
    while courant is not None:
        elements.append(str(courant.element))   # la valeur est dans courant.element
        courant = courant.suivant                # passer au suivant
    return " → ".join(elements)

On collecte les valeurs dans une liste Python puis on les joint avec la flèche.

c)

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

Si on atteint la fin de la chaîne sans avoir trouvé l’élément, c’est qu’il est absent.

def supprime_en_tete(self):
    if self.premier is None:
        raise ValueError("liste vide")
    element = self.premier.element
    self.premier = self.premier.suivant
    return element

Principe : on sauvegarde la valeur du premier nœud, puis on fait pointer self.premier vers le deuxième nœud (le suivant du premier). L’ancien premier nœud n’est plus référencé et sera récupéré par le ramasse-miettes de Python.

• Premier appel : renvoie 9, la liste devient 3 → 7.
• Deuxième appel : renvoie 3, la liste devient 7.
• Troisième appel : renvoie 7, la liste est maintenant vide (premier = None).
• Quatrième appel : lève ValueError("liste vide") car self.premier vaut None.

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
        nouveau = Noeud(element)
        nouveau.suivant = courant.suivant
        courant.suivant = nouveau

Explication pas à pas pour inserer(1, 2) sur la liste 5 → 9 → 3 → 7 :

1. i = 2, donc on ne passe pas par ajout_en_tete.
2. On avance d’un pas (i - 1 = 1) : courant pointe sur le nœud contenant 9 (position 1).
3. On crée un nouveau nœud contenant 1.
4. On fait pointer nouveau.suivant vers courant.suivant, c’est-à-dire le nœud contenant 3.
5. On fait pointer courant.suivant vers le nouveau nœud.
6. Résultat : 5 → 9 → 1 → 3 → 7.

Vérification : l’ajout en position 0 redonne bien ajout_en_tete, et l’ajout en dernière position (i = longueur) revient à un ajout en queue.

Conclusion : la liste chaînée est particulièrement adaptée lorsque les opérations se concentrent en tête de la structure (ce qui en fait une brique idéale pour les piles). Le tableau dynamique est plus polyvalent grâce à l’accès direct par indice.

1. enfiler correspond à ajout_en_queue (ajout à la fin) et defiler correspond à supprime_en_tete (retrait au début). C’est bien le comportement FIFO : le premier entré (en queue) est le premier à sortir (en tête).

class File:
    def __init__(self):
        self.contenu = ListeChainee()

    def enfiler(self, element):
        self.contenu.ajout_en_queue(element)

    def defiler(self):
        if self.est_vide():
            raise ValueError("file vide")
        return self.contenu.supprime_en_tete()

    def est_vide(self):
        return self.contenu.premier is None

    def __repr__(self):
        elements = []
        courant = self.contenu.premier
        while courant is not None:
            elements.append(str(courant.element))
            courant = courant.suivant
        return " ← ".join(elements) if elements else "(file vide)"

f = File()
f.enfiler("Alice")    # Alice
f.enfiler("Bob")      # Alice ← Bob
f.enfiler("Charlie")  # Alice ← Bob ← Charlie
f.defiler()           # renvoie "Alice" → Bob ← Charlie
f.defiler()           # renvoie "Bob"   → Charlie
f.enfiler("Diana")    # Charlie ← Diana

4. Avec cette implémentation, defiler est en \(O(1)\) (suppression en tête) mais enfiler est en \(O(n)\) (parcours jusqu’en queue).

   Amélioration : ajouter un attribut dernier dans la classe ListeChainee (ou dans File) qui pointe toujours vers le dernier nœud. Lors de l’ajout en queue, on accède directement au dernier nœud sans parcourir la liste. L’ajout en queue devient alors \(O(1)\).

   def enfiler(self, element):
       nouveau = Noeud(element)
       if self.dernier is not None:
           self.dernier.suivant = nouveau
       else:
           self.contenu.premier = nouveau
       self.dernier = nouveau
   

   Il faut aussi remettre dernier à None quand la file se vide, sinon le prochain enfiler accroche le nouveau nœud à un nœud déjà retiré de la liste :

   def defiler(self):
       element = self.contenu.supprime_en_tete()
       if self.contenu.premier is None:
           self.dernier = None
       return element