Listes chaînées : exercices corrigés de Terminale NSI

Schéma : $4 \to 8 \to 15 \to 16 \to$ None. La dernière cellule ne pointe vers rien.

Avant la boucle : total = 0 et courante désigne la cellule de valeur 4.

Tour 1 : total vaut 4, puis courante passe sur 8. Tour 2 : total vaut 12. Tour 3 : total vaut 27. Tour 4 : total vaut 43, puis courante vaut None.

La condition courante is not None est fausse : la boucle s'arrête et la fonction renvoie 43.

Pour somme(None) : courante vaut None dès le départ, la boucle ne s'exécute pas et la fonction renvoie 0.

Liste simplement chaînée : chaque cellule porte un seul pointeur, vers le suivant ³. Avec 7 cellules : 7 pointeurs.

Liste doublement chaînée : chaque cellule porte 2 pointeurs ³. Avec 7 cellules : $2 \times 7 = 14$ pointeurs.

Conséquence : la structure doublement chaînée est plus coûteuse en mémoire, car elle demande un pointeur supplémentaire par élément ².

Version itérative : on part de courante = tete et n = 0, on boucle tant que courante is not None en ajoutant 1 à n et en avançant.

def longueur(tete):
    n = 0
    courante = tete
    while courante is not None:
        n = n + 1
        courante = courante.suivant
    return n

Assertions : assert longueur(None) == 0, assert longueur(Cellule(5)) == 1, assert longueur(Cellule(1, Cellule(2, Cellule(3)))) == 3.

Version récursive : le cas de base est la liste vide, le cas général s'appuie sur la sous-liste qui suit.

def longueur_rec(tete):
    if tete is None:
        return 0
    return 1 + longueur_rec(tete.suivant)

Les deux versions visitent chaque cellule une fois : le nombre d'opérations est proportionnel à la longueur de la liste.

Insertion de n après c dans une liste simple : n.suivant = c.suivant (la nouvelle cellule pointe vers la suite), puis c.suivant = n (la précédente pointe vers la nouvelle). Deux affectations.

Liste doublement chaînée : 4 copies par insertion. Pour 5 insertions : $5 \times 4 = 20$ copies.

Liste simplement chaînée : 2 copies par insertion. Pour 5 insertions : $5 \times 2 = 10$ copies.

Insertion en tête : la nouvelle cellule pointe vers l'ancienne tête, et elle devient la nouvelle tête.

def inserer_tete(tete, v):
    return Cellule(v, tete)

Insertion après c : on garde d'abord la suite en la faisant pointer par la nouvelle cellule, puis on rattache.

def inserer_apres(c, v):
    c.suivant = Cellule(v, c.suivant)

Analyse du code de l'élève : après c.suivant = n, la valeur d'origine de c.suivant est perdue. La dernière ligne devient n.suivant = n car c.suivant désigne maintenant n.

Résultat : la nouvelle cellule pointe vers elle-même. Elle forme une boucle infinie, et toute la fin de la liste d'origine est inaccessible.

Cas particuliers : liste vide, suppression de la tête, valeur absente.

Écriture :

def supprimer(tete, v):
    if tete is None:
        return None
    if tete.valeur == v:
        return tete.suivant
    courante = tete
    while courante.suivant is not None and courante.suivant.valeur != v:
        courante = courante.suivant
    if courante.suivant is not None:
        courante.suivant = courante.suivant.suivant
    return tete

v = 7 : la tête vaut 3, ce n'est pas elle qu'on supprime. Dès le départ, courante.suivant a pour valeur 7 : la boucle ne fait aucun tour, et on fait pointer courante (3) vers 9. Résultat : $3 \to 9 \to 7$. Seule la première occurrence disparaît.

v = 3 : la tête est la cellule à supprimer, la fonction renvoie tete.suivant. Résultat : $7 \to 9 \to 7$.

v = 5 : la boucle atteint la dernière cellule, courante.suivant vaut None, aucune modification. La liste est inchangée.

Variables : precedent (initialisé à None), courante (initialisée à tete), et une variable temporaire suivante pour ne pas perdre la suite.

Écriture :

def inverser(tete):
    precedent = None
    courante = tete
    while courante is not None:
        suivante = courante.suivant
        courante.suivant = precedent
        precedent = courante
        courante = suivante
    return precedent

Tour 1 : la cellule 1 pointe vers None, precedent devient la cellule 1, courante passe sur la cellule 2.

Tour 2 : la cellule 2 pointe vers la cellule 1. Tour 3 : la cellule 3 pointe vers la cellule 2.

À la sortie, courante vaut None et precedent désigne la cellule 3. La liste est $3 \to 2 \to 1$, et on renvoie precedent.

Écriture :

def acces(tete, k):
    courante = tete
    i = 0
    while courante is not None and i < k:
        courante = courante.suivant
        i = i + 1
    if courante is None:
        return None
    return courante.valeur

Pour atteindre l'indice 12, il faut partir de l'indice 0 (la tête) et avancer jusqu'à l'indice 12 : 12 déplacements, donc 13 cellules visitées en comptant la tête.

Interprétation : l'accès à l'indice $k$ demande $k$ déplacements. Dans un tableau, on calcule directement l'emplacement.

Choix de la structure : on recommande souvent une liste chaînée quand l'ordre des éléments compte et que l'on insère ou supprime des éléments n'importe où plus souvent qu'on n'y accède ². Si l'on accède surtout à des positions arbitraires, un tableau convient mieux.

Avec longueur(a) : la condition courante is not None ne devient jamais fausse, car aucune cellule ne pointe vers None. La boucle ne s'arrête pas.

Écriture de est_cyclique :

def est_cyclique(tete):
    vues = []
    courante = tete
    while courante is not None:
        if courante in vues:
            return True
        vues.append(courante)
        courante = courante.suivant
    return False

Déroulé sur a : on visite a, puis b, puis c (trois ajouts à vues). Puis courante redevient a, déjà dans vues : la fonction renvoie True.

Le nombre de cellules distinctes visitées est donc 3.