Représenter des collections dynamiques par des nœuds et des références

Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• définir un nœud, une donnée, une référence suivante et une tête de liste ;
• représenter une liste vide et identifier la fin d’une liste ;
• parcourir et rechercher un élément dans une liste simplement chaînée ;
• insérer un nœud en tête, en fin ou à une position donnée ;
• supprimer correctement un nœud en traitant les cas particuliers ;
• manipuler une liste doublement chaînée dans les deux directions ;
• expliquer le fonctionnement d’une liste circulaire et définir sa condition d’arrêt ;
• analyser la complexité des principales opérations ;
• comparer les listes chaînées aux tableaux ;
• choisir une variante de liste selon les besoins d’une application.

Prérequis

• types abstraits de données, interfaces et contrats ;
• enregistrements ou structures contenant plusieurs champs ;
• références, pointeurs ou liens logiques entre objets ;
• fonctions, procédures et passage par référence ;
• boucles, conditions et analyse élémentaire de complexité.

Plan du chapitre

Organisation pédagogique indicative

Introduction

Un tableau regroupe des éléments dans des cases contiguës et permet un accès direct par indice. Cette organisation est très efficace lorsque la taille est connue et que les accès aléatoires sont fréquents. Elle devient cependant moins adaptée lorsque la collection grandit ou rétrécit souvent, car les insertions et les suppressions peuvent imposer de nombreux décalages.

Une liste chaînée représente les éléments par des nœuds créés au besoin. Chaque nœud contient une donnée et une ou plusieurs références vers d’autres nœuds. Les nœuds ne doivent pas nécessairement être voisins en mémoire : leur ordre logique est déterminé par les références.

3.1 Principe

3.1.1 Le nœud

Le nœud est l’unité de base d’une liste chaînée. Il regroupe la valeur utile et les informations de liaison nécessaires pour atteindre un autre nœud. Dans une liste simplement chaînée, un nœud possède généralement deux champs : donnée et suivant.

Déclaration abstraite d’un nœud simple

Type Noeud<T>
    donnée : T
    suivant : Référence vers Noeud<T> ou NULL
FinType

3.1.2 La donnée

La donnée peut être simple ou structurée. Une liste d’entiers stocke directement un entier dans chaque nœud. Une liste d’étudiants stocke un enregistrement contenant par exemple le numéro d’inscription, le nom et la moyenne. La structure de la donnée ne modifie pas le principe du chaînage.

3.1.3 La référence vers le nœud suivant

La référence suivant permet de continuer le parcours. Elle ne contient pas nécessairement le nœud lui-même : elle permet de le retrouver. Dans un langage utilisant des pointeurs, il s’agit d’une adresse. Dans un langage à objets, il peut s’agir d’une référence vers une instance.

• si suivant désigne un nœud, le parcours peut continuer ;
• si suivant vaut NULL, le nœud courant est le dernier ;
• une référence incorrecte ou perdue peut rendre une partie de la liste inaccessible ;
• une modification des liens doit préserver l’ordre logique de la liste.

3.1.4 La tête de liste

La tête est la référence permettant d’atteindre le premier nœud. Toutes les opérations commencent généralement par cette référence. Une liste vide est représentée par une tête égale à NULL.

Représentation conceptuelle d’une liste simplement chaînée

Liste vide : tête = NULL

Perdre la référence tête revient à perdre l’accès à toute la liste, sauf si une autre référence vers un nœud a été conservée. Pour cette raison, les opérations qui peuvent modifier le premier élément doivent mettre à jour la tête avec soin.

3.1.5 La fin de liste

Dans une liste simplement chaînée classique, le champ suivant du dernier nœud vaut NULL. Ce marqueur permet d’arrêter le parcours. Certaines implémentations conservent aussi une référence fin vers le dernier nœud afin d’ajouter rapidement un élément en fin de liste.

3.1.6 Invariants fondamentaux

Une liste valide doit respecter des propriétés permanentes. Ces invariants permettent de raisonner sur la correction des opérations et de détecter des erreurs d’implémentation.

• si la liste est vide, tête vaut NULL et la taille vaut 0 ;
• si la liste n’est pas vide, tête désigne un nœud valide ;
• chaque nœud accessible appartient à la liste une seule fois, sauf dans une liste circulaire ;
• dans une liste simple non circulaire, le dernier nœud possède suivant = NULL ;
• le nombre de nœuds accessibles depuis tête est égal au champ taille, si ce champ est maintenu.

3.2 Liste simplement chaînée

Une liste simplement chaînée relie chaque nœud uniquement à son successeur. Le parcours naturel s’effectue donc de la tête vers la fin. Cette structure est légère et efficace pour les insertions ou suppressions lorsque le nœud précédent est connu.

3.2.1 Représentation du type Liste

Représentation possible

Type ListeSimple<T>
    tête : Référence vers Noeud<T> ou NULL
    fin : Référence vers Noeud<T> ou NULL      // facultatif
    taille : Entier                            // facultatif
FinType

Les champs fin et taille ne sont pas indispensables, mais ils accélèrent certaines opérations. Ils créent aussi des invariants supplémentaires qu’il faut mettre à jour après chaque modification.

3.2.2 Création

Créer une liste consiste à initialiser un état vide. Aucun nœud n’est nécessaire tant que le premier élément n’est pas ajouté.

Création d’une liste vide

Fonction CréerListe() → ListeSimple
    L.tête ← NULL
    L.fin ← NULL
    L.taille ← 0
    Retourner L
FinFonction

3.2.3 Parcours

Le parcours suit les références suivant à partir de la tête. Une variable courant conserve le nœud actuellement visité. Le parcours s’arrête lorsque courant vaut NULL.

Parcours complet

Procédure AfficherListe(L)
    courant ← L.tête
    TantQue courant ≠ NULL Faire
        Afficher(courant.donnée)
        courant ← courant.suivant
    FinTantQue
FinProcédure

3.2.4 Recherche

La recherche séquentielle compare la valeur recherchée à chaque donnée. Elle peut s’arrêter dès la première occurrence ou continuer pour compter toutes les occurrences.

Recherche de la première occurrence

Fonction Rechercher(L, valeur) → RéférenceOuNULL
    courant ← L.tête
    TantQue courant ≠ NULL ET courant.donnée ≠ valeur Faire
        courant ← courant.suivant
    FinTantQue
    Retourner courant
FinFonction

Si le résultat vaut NULL, la valeur est absente. Sinon, le résultat désigne le nœud trouvé. Le meilleur cas est O(1) lorsque la tête contient la valeur ; le pire cas est O(n).

3.2.5 Insertion en tête

L’insertion en tête ne nécessite aucun parcours. Le nouveau nœud doit d’abord pointer vers l’ancienne tête, puis la tête de la liste est remplacée par le nouveau nœud. L’ordre des affectations est essentiel.

Insertion en tête

Procédure InsérerTête(L, valeur)
    nouveau ← NouveauNoeud()
    nouveau.donnée ← valeur
    nouveau.suivant ← L.tête
    L.tête ← nouveau
    Si L.fin = NULL Alors
        L.fin ← nouveau
    FinSi
    L.taille ← L.taille + 1
FinProcédure

Après insertion de 5 en tête

3.2.6 Insertion en fin

Sans référence fin, il faut parcourir la liste jusqu’au dernier nœud. Avec une référence fin correctement maintenue, l’insertion devient constante.

Insertion en fin avec référence fin

Procédure InsérerFin(L, valeur)
    nouveau ← NouveauNoeud()
    nouveau.donnée ← valeur
    nouveau.suivant ← NULL

    Si L.tête = NULL Alors
        L.tête ← nouveau
        L.fin ← nouveau
    Sinon
        L.fin.suivant ← nouveau
        L.fin ← nouveau
    FinSi
    L.taille ← L.taille + 1
FinProcédure

3.2.7 Insertion à une position donnée

On suppose ici que les positions commencent à 0. Insérer à la position 0 revient à insérer en tête. Pour une autre position, il faut atteindre le nœud qui précède la position d’insertion.

Insertion à une position

Procédure InsérerÀ(L, position, valeur)
    Si position < 0 OU position > L.taille Alors
        Erreur("Position invalide")
    FinSi

    Si position = 0 Alors
        InsérerTête(L, valeur)
        Retourner
    FinSi

    précédent ← L.tête
    Pour i allant de 0 à position - 2 Faire
        précédent ← précédent.suivant
    FinPour

    nouveau ← NouveauNoeud()
    nouveau.donnée ← valeur
    nouveau.suivant ← précédent.suivant
    précédent.suivant ← nouveau

    Si nouveau.suivant = NULL Alors
        L.fin ← nouveau
    FinSi
    L.taille ← L.taille + 1
FinProcédure

3.2.8 Suppression en tête

Supprimer la tête consiste à mémoriser le premier nœud, déplacer la tête vers le suivant, puis libérer l’ancien nœud si le langage le demande. Si la liste devient vide, la référence fin doit aussi être remise à NULL.

Suppression en tête

Fonction SupprimerTête(L) → T
    Si L.tête = NULL Alors
        Erreur("Liste vide")
    FinSi

    ancien ← L.tête
    valeur ← ancien.donnée
    L.tête ← ancien.suivant
    L.taille ← L.taille - 1

    Si L.tête = NULL Alors
        L.fin ← NULL
    FinSi
    Libérer(ancien)
    Retourner valeur
FinFonction

3.2.9 Suppression d’une valeur

Pour supprimer la première occurrence d’une valeur, il faut conserver deux références : courant et précédent. Le cas où la valeur se trouve en tête doit être traité séparément, car aucun nœud précédent n’existe.

Suppression de la première occurrence

Fonction SupprimerValeur(L, valeur) → Booléen
    précédent ← NULL
    courant ← L.tête

    TantQue courant ≠ NULL ET courant.donnée ≠ valeur Faire
        précédent ← courant
        courant ← courant.suivant
    FinTantQue

    Si courant = NULL Alors
        Retourner Faux
    FinSi

    Si précédent = NULL Alors
        L.tête ← courant.suivant
    Sinon
        précédent.suivant ← courant.suivant
    FinSi

    Si courant = L.fin Alors
        L.fin ← précédent
    FinSi
    L.taille ← L.taille - 1
    Libérer(courant)
    Retourner Vrai
FinFonction

3.2.10 Suppression à une position

La suppression à une position valide suit le même principe que l’insertion : atteindre le nœud précédent, reconnecter le chaînage et actualiser fin si le dernier nœud est supprimé.

Suppression à une position

Fonction SupprimerÀ(L, position) → T
    Si position < 0 OU position ≥ L.taille Alors
        Erreur("Position invalide")
    FinSi
    Si position = 0 Alors
        Retourner SupprimerTête(L)
    FinSi

    précédent ← L.tête
    Pour i allant de 0 à position - 2 Faire
        précédent ← précédent.suivant
    FinPour

    cible ← précédent.suivant
    précédent.suivant ← cible.suivant
    Si cible = L.fin Alors
        L.fin ← précédent
    FinSi
    valeur ← cible.donnée
    L.taille ← L.taille - 1
    Libérer(cible)
    Retourner valeur
FinFonction

3.2.11 Complexité des opérations

3.3 Liste doublement chaînée

Dans une liste doublement chaînée, chaque nœud contient une référence vers son prédécesseur et une référence vers son successeur. Le parcours est possible dans les deux sens. Cette souplesse augmente toutefois la mémoire utilisée et le nombre de liens à maintenir.

Nœud d’une liste doublement chaînée

Type NoeudDouble<T>
    précédente : Référence vers NoeudDouble<T> ou NULL
    donnée : T
    suivante : Référence vers NoeudDouble<T> ou NULL
FinType

Chaînage bidirectionnel

3.3.1 Référence précédente

La référence précédente permet de revenir au nœud antérieur sans repartir de la tête. Pour le premier nœud, précédente vaut généralement NULL dans une liste non circulaire.

3.3.2 Référence suivante

La référence suivante joue le même rôle que dans une liste simplement chaînée. Pour le dernier nœud, elle vaut généralement NULL. La structure conserve souvent les références tête et fin afin de démarrer un parcours dans l’un ou l’autre sens.

3.3.3 Parcours dans les deux sens

Parcours avant et arrière

Procédure AfficherAvant(L)
    courant ← L.tête
    TantQue courant ≠ NULL Faire
        Afficher(courant.donnée)
        courant ← courant.suivante
    FinTantQue
FinProcédure

Procédure AfficherArrière(L)
    courant ← L.fin
    TantQue courant ≠ NULL Faire
        Afficher(courant.donnée)
        courant ← courant.précédente
    FinTantQue
FinProcédure

3.3.4 Insertion entre deux nœuds

Pour insérer nouveau entre gauche et droite, quatre liens doivent être cohérents. L’ordre des affectations doit éviter de perdre les références existantes.

Insertion au milieu

Procédure InsérerEntre(gauche, droite, nouveau)
    nouveau.précédente ← gauche
    nouveau.suivante ← droite
    gauche.suivante ← nouveau
    droite.précédente ← nouveau
FinProcédure

Les insertions en tête ou en fin sont des variantes dans lesquelles l’un des voisins est absent. L’utilisation de nœuds sentinelles peut réduire le nombre de cas particuliers.

3.3.5 Suppression d’un nœud connu

Lorsque la référence du nœud cible est déjà connue, sa suppression peut être effectuée en O(1), car ses deux voisins sont immédiatement accessibles.

Suppression dans une liste doublement chaînée

Procédure SupprimerNoeud(L, cible)
    Si cible.précédente ≠ NULL Alors
        cible.précédente.suivante ← cible.suivante
    Sinon
        L.tête ← cible.suivante
    FinSi

    Si cible.suivante ≠ NULL Alors
        cible.suivante.précédente ← cible.précédente
    Sinon
        L.fin ← cible.précédente
    FinSi

    L.taille ← L.taille - 1
    Libérer(cible)
FinProcédure

3.3.6 Nœuds sentinelles

Une sentinelle est un nœud spécial qui ne représente pas un élément utilisateur. Une sentinelle de début et une sentinelle de fin permettent d’éviter les références NULL au milieu des opérations et de traiter l’insertion de manière uniforme.

3.3.7 Coût et choix

3.4 Liste circulaire

Dans une liste circulaire, le dernier nœud ne pointe pas vers NULL : il pointe vers le premier nœud. La structure forme un cycle. Elle est adaptée aux traitements répétitifs dans lesquels, après le dernier élément, on revient naturellement au premier.

Liste circulaire simplement chaînée

3.4.1 Dernier élément relié au premier

Si la liste conserve une référence fin, la tête peut être obtenue par fin.suivant. Pour une liste circulaire non vide, fin.suivant ne vaut jamais NULL. Une liste circulaire vide reste représentée par fin = NULL ou tête = NULL selon l’implémentation.

Liste circulaire non vide : fin.suivant = tête

3.4.2 Parcours circulaire

Le parcours ne peut pas s’arrêter sur NULL. Il faut reconnaître le retour au point de départ. Une boucle Répéter…Jusqu’à est particulièrement adaptée, car le premier nœud doit être traité avant de tester le retour à la tête.

Parcours d’un tour complet

Procédure AfficherCirculaire(L)
    Si L.tête = NULL Alors
        Retourner
    FinSi

    courant ← L.tête
    Répéter
        Afficher(courant.donnée)
        courant ← courant.suivant
    Jusqu’à courant = L.tête
FinProcédure

3.4.3 Conditions d’arrêt

3.4.4 Insertion et suppression

L’insertion en tête doit aussi modifier le lien du dernier nœud afin qu’il pointe vers la nouvelle tête. Avec une référence fin, l’ajout en fin est très efficace : le nouveau nœud pointe vers la tête, l’ancienne fin pointe vers le nouveau nœud, puis fin est déplacée.

Ajout en fin dans une liste circulaire

Procédure InsérerFinCirculaire(L, valeur)
    nouveau ← NouveauNoeud()
    nouveau.donnée ← valeur

    Si L.fin = NULL Alors
        L.fin ← nouveau
        nouveau.suivant ← nouveau
    Sinon
        nouveau.suivant ← L.fin.suivant   // ancienne tête
        L.fin.suivant ← nouveau
        L.fin ← nouveau
    FinSi
    L.taille ← L.taille + 1
FinProcédure

3.4.5 Applications

• ordonnancement Round-Robin de processus ou de joueurs ;
• rotation équitable entre plusieurs ressources ;
• playlist répétée en boucle ;
• gestion d’un anneau logique dans un réseau ;
• simulation de problèmes comme l’élimination de Joseph.

3.5 Comparaison avec les tableaux

Les tableaux et les listes représentent tous deux des collections, mais leurs performances et leur organisation mémoire sont différentes. Le choix dépend des opérations dominantes et des contraintes de l’application.

3.5.1 Taille dynamique

Une liste peut ajouter un nœud à chaque nouvelle valeur, dans la limite de la mémoire disponible. Un tableau classique possède une capacité fixe. Un tableau dynamique peut s’agrandir, mais il doit parfois allouer un nouveau bloc et recopier les éléments.

3.5.2 Accès direct ou séquentiel

Le tableau permet d’atteindre T[i] en O(1) grâce au calcul d’adresse. Dans une liste, atteindre la position i impose de suivre i liens depuis la tête, soit O(i). Les listes ne conviennent donc pas aux accès aléatoires fréquents par indice.

3.5.3 Coût d’insertion et de suppression

Dans un tableau, insérer ou supprimer au milieu exige généralement de décaler les éléments suivants. Dans une liste, la modification des liens est constante lorsque la position ou le nœud précédent est déjà connu. Le coût de localisation reste toutefois O(n) si la position doit être recherchée.

3.5.4 Utilisation mémoire et localité

Chaque nœud consomme de la mémoire supplémentaire pour ses références et peut entraîner un coût d’allocation. Les éléments d’un tableau sont contigus, ce qui favorise la mémoire cache et rend les parcours souvent plus rapides en pratique, même lorsque les complexités asymptotiques sont identiques.

3.5.5 Guide de choix

Applications guidées

Application 1 — Gestion d’une liste d’étudiants

On souhaite conserver des étudiants dans l’ordre d’inscription. Chaque nœud contient un numéro, un nom et une moyenne. La liste doit permettre l’ajout en fin, la recherche par numéro, la modification d’une moyenne et la suppression d’un étudiant.

Structure des données

Type Étudiant
    numéro : Chaîne
    nom : Chaîne
    moyenne : Réel
FinType

Type NoeudÉtudiant
    donnée : Étudiant
    suivant : Référence vers NoeudÉtudiant ou NULL
FinType

Recherche d’un étudiant

Fonction RechercherParNuméro(L, numéro) → RéférenceOuNULL
    courant ← L.tête
    TantQue courant ≠ NULL Faire
        Si courant.donnée.numéro = numéro Alors
            Retourner courant
        FinSi
        courant ← courant.suivant
    FinTantQue
    Retourner NULL
FinFonction

• l’ajout en fin conserve l’ordre d’inscription ;
• la recherche est O(n) ;
• la modification d’une moyenne est O(n) pour localiser, puis O(1) pour modifier ;
• une table de hachage serait plus adaptée si les recherches par numéro deviennent très fréquentes.

Application 2 — Liste de lecture musicale

Une playlist doit permettre de passer au morceau suivant et précédent, d’insérer un morceau après le morceau courant et d’en supprimer un. Une liste doublement chaînée convient naturellement à la navigation bidirectionnelle.

Nœud de la playlist

Type Morceau
    titre : Chaîne
    artiste : Chaîne
    durée : Entier
FinType

Type NoeudMorceau
    précédente : Référence vers NoeudMorceau ou NULL
    donnée : Morceau
    suivante : Référence vers NoeudMorceau ou NULL
FinType

Application 3 — Historique de navigation

Un navigateur doit revenir vers la page précédente et avancer vers une page visitée après un retour. Une liste doublement chaînée représente les pages dans l’ordre. Lorsqu’une nouvelle page est visitée après un retour, la partie située après la page courante doit être supprimée.

Visite d’une nouvelle page

Procédure VisiterNouvellePage(H, url)
    // Supprimer l’historique situé après la page courante.
    SupprimerAprès(H.courant)

    nouveau ← CréerNoeud(url)
    InsérerAprès(H, H.courant, nouveau)
    H.courant ← nouveau
FinProcédure

Application 4 — Gestion d’un tour de jeu

Dans un jeu à plusieurs participants, le tour passe du joueur courant au suivant et revient au premier après le dernier. Une liste circulaire fournit ce comportement sans test spécial de fin.

Passage au joueur suivant

Procédure JouerUnTour(Partie)
    joueur ← Partie.courant
    EffectuerAction(joueur)

    Si joueur.estÉliminé Alors
        Partie.courant ← SupprimerEtRetournerSuivant(Partie, joueur)
    Sinon
        Partie.courant ← joueur.suivant
    FinSi
FinProcédure

La suppression doit traiter le cas où le joueur éliminé est le seul restant. Dans ce cas, la partie se termine et la liste devient vide ou conserve le gagnant selon les règles choisies.

Tests, validation et erreurs fréquentes

Jeux d’essai indispensables

Erreurs fréquentes

Vérification des invariants

Vérification simplifiée d’une liste simple

Fonction VérifierInvariant(L) → Booléen
    compteur ← 0
    courant ← L.tête
    dernier ← NULL

    TantQue courant ≠ NULL Faire
        compteur ← compteur + 1
        dernier ← courant
        courant ← courant.suivant
    FinTantQue

    Retourner compteur = L.taille ET dernier = L.fin
FinFonction

Cette fonction est destinée au débogage. Elle parcourt la liste en O(n) et ne doit pas nécessairement être exécutée après chaque opération dans une version optimisée.

Travaux dirigés

Exercice 1 — Lecture d’une représentation

Pour la liste 4 → 9 → 2 → NULL, indiquer la tête, le dernier nœud, le nombre de liens suivis pour atteindre 2 et l’état après suppression de 9.

Exercice 2 — Traçage d’une insertion

Tracer pas à pas l’insertion de 6 en tête de la liste 10 → 20 → NULL. Indiquer la valeur de nouveau.suivant avant et après la mise à jour de tête.

Exercice 3 — Insertion en fin sans référence fin

Écrire le pseudo-code d’un ajout en fin lorsque la liste ne conserve que la tête. Préciser le cas de la liste vide et analyser la complexité.

Exercice 4 — Compter les occurrences

Écrire une fonction qui compte le nombre d’occurrences d’une valeur dans une liste simplement chaînée.

Exercice 5 — Supprimer toutes les occurrences

Concevoir une procédure qui supprime toutes les occurrences d’une valeur, y compris plusieurs occurrences consécutives en tête.

Exercice 6 — Inverser une liste

Écrire un algorithme itératif qui inverse les liens d’une liste simplement chaînée sans créer de nouveaux nœuds.

Exercice 7 — Liste doublement chaînée

Écrire l’insertion d’un nouveau nœud juste avant un nœud cible connu. Traiter le cas où la cible est la tête.

Exercice 8 — Détection d’un cycle

Proposer une méthode utilisant deux références, l’une avançant d’un nœud et l’autre de deux nœuds, pour détecter un cycle dans une liste.

Exercice 9 — Tour de jeu circulaire

Simuler deux tours complets d’une liste circulaire contenant A, B et C. Puis supprimer B et poursuivre un tour.

Exercice 10 — Choix de structure

Pour chaque situation suivante, choisir tableau, liste simple, liste double ou liste circulaire : accès par indice intensif, historique précédent/suivant, file de joueurs, insertions fréquentes en tête.

Corrigés indicatifs des travaux dirigés

Correction 1 — Lecture d’une représentation

• la tête désigne le nœud contenant 4 ;
• le dernier nœud contient 2 et son champ suivant vaut NULL ;
• deux liens sont suivis pour passer de 4 à 9 puis de 9 à 2 ;
• après suppression de 9, le lien du nœud 4 désigne directement le nœud 2 : 4 → 2 → NULL.

Correction 2 — Traçage d’une insertion

Correction 3 — Insertion en fin sans référence fin

Procédure InsérerFinSansFin(L, valeur)
    nouveau ← CréerNoeud(valeur)
    nouveau.suivant ← NULL

    Si L.tête = NULL Alors
        L.tête ← nouveau
        Retourner
    FinSi

    courant ← L.tête
    TantQue courant.suivant ≠ NULL Faire
        courant ← courant.suivant
    FinTantQue
    courant.suivant ← nouveau
FinProcédure

Le cas vide est O(1). Dans le cas général, le parcours atteint le dernier nœud : la complexité est O(n).

Correction 4 — Compter les occurrences

Fonction CompterOccurrences(L, valeur) → Entier
    compteur ← 0
    courant ← L.tête
    TantQue courant ≠ NULL Faire
        Si courant.donnée = valeur Alors
            compteur ← compteur + 1
        FinSi
        courant ← courant.suivant
    FinTantQue
    Retourner compteur
FinFonction

Correction 5 — Supprimer toutes les occurrences

Procédure SupprimerToutes(L, valeur)
    TantQue L.tête ≠ NULL ET L.tête.donnée = valeur Faire
        SupprimerTête(L)
    FinTantQue

    Si L.tête = NULL Alors
        Retourner
    FinSi

    précédent ← L.tête
    courant ← L.tête.suivant
    TantQue courant ≠ NULL Faire
        Si courant.donnée = valeur Alors
            précédent.suivant ← courant.suivant
            Si courant = L.fin Alors
                L.fin ← précédent
            FinSi
            àLibérer ← courant
            courant ← courant.suivant
            L.taille ← L.taille - 1
            Libérer(àLibérer)
        Sinon
            précédent ← courant
            courant ← courant.suivant
        FinSi
    FinTantQue
FinProcédure

Correction 6 — Inverser une liste

Procédure Inverser(L)
    ancienneTête ← L.tête
    précédent ← NULL
    courant ← L.tête

    TantQue courant ≠ NULL Faire
        suivantTemp ← courant.suivant
        courant.suivant ← précédent
        précédent ← courant
        courant ← suivantTemp
    FinTantQue

    L.tête ← précédent
    L.fin ← ancienneTête
FinProcédure

Chaque lien est inversé une seule fois. La complexité est O(n) et la mémoire auxiliaire est O(1).

Correction 7 — Insertion avant une cible

Procédure InsérerAvant(L, cible, valeur)
    nouveau ← CréerNoeudDouble(valeur)
    nouveau.suivante ← cible
    nouveau.précédente ← cible.précédente

    Si cible.précédente ≠ NULL Alors
        cible.précédente.suivante ← nouveau
    Sinon
        L.tête ← nouveau
    FinSi
    cible.précédente ← nouveau
    L.taille ← L.taille + 1
FinProcédure

Correction 8 — Détection d’un cycle

Fonction ContientCycle(L) → Booléen
    lent ← L.tête
    rapide ← L.tête

    TantQue rapide ≠ NULL ET rapide.suivant ≠ NULL Faire
        lent ← lent.suivant
        rapide ← rapide.suivant.suivant
        Si lent = rapide Alors
            Retourner Vrai
        FinSi
    FinTantQue
    Retourner Faux
FinFonction

Si un cycle existe, la référence rapide finit par rattraper la référence lente. Sans cycle, rapide atteint NULL.

Correction 9 — Tour de jeu circulaire

Deux tours donnent : A, B, C, A, B, C. Après suppression de B, le cycle devient A → C → A. Le tour suivant donne A, C puis retour à A.

Correction 10 — Choix de structure

Travail pratique — Gestion d’une liste d’étudiants

Objectif

Implémenter une liste simplement chaînée d’étudiants, valider ses invariants et mesurer le coût des principales opérations.

Fonctionnalités demandées

1. Créer une liste vide et vérifier EstVide.

2. Ajouter un étudiant en tête et en fin.

3. Afficher les étudiants dans l’ordre de la liste.

4. Rechercher un étudiant par numéro d’inscription.

5. Modifier la moyenne d’un étudiant.

6. Supprimer un étudiant par numéro.

7. Calculer la moyenne générale de la liste.

8. Afficher les étudiants admis, définis par moyenne ≥ 10.

9. Inverser la liste sans créer de nouveaux nœuds.

10. Libérer ou vider complètement la liste.

Structure suggérée

Type Étudiant
    numéro : Chaîne
    nom : Chaîne
    moyenne : Réel
FinType

Type Noeud
    donnée : Étudiant
    suivant : Référence vers Noeud ou NULL
FinType

Type ListeÉtudiants
    tête : Référence vers Noeud ou NULL
    fin : Référence vers Noeud ou NULL
    taille : Entier
FinType

Jeux d’essai minimaux

Correction architecturale indicative

La solution peut être organisée autour des opérations suivantes :

CréerListe() → ListeÉtudiants
AjouterTête(L, étudiant)
AjouterFin(L, étudiant)
Afficher(L)
RechercherNuméro(L, numéro) → RéférenceOuNULL
ModifierMoyenne(L, numéro, nouvelleMoyenne) → Booléen
SupprimerNuméro(L, numéro) → Booléen
MoyenneGénérale(L) → RéelOuErreur
AfficherAdmis(L)
Inverser(L)
Vider(L)
VérifierInvariant(L) → Booléen

Grille d’évaluation indicative

Synthèse du chapitre

Glossaire

Auto-évaluation