Qu'est-ce qu'une liste chaînée en NSI ?

Une liste chaînée est une structure de données linéaire composée de nœuds. Chaque nœud contient une valeur et un pointeur vers le nœud suivant. Elle permet des insertions et suppressions en tête en temps constant O(1).

Quelle est la différence entre une liste chaînée et un tableau ?

Un tableau stocke les éléments dans des cases contiguës en mémoire, ce qui permet un accès direct en O(1) mais des insertions/suppressions coûteuses en O(n). Une liste chaînée stocke les éléments de manière dispersée, avec un accès séquentiel O(n) mais des insertions/suppressions en tête en O(1).

Comment implémenter une liste chaînée en Python ?

On crée une classe Noeud avec attributs 'valeur' et 'suivant', puis une classe ListeChainee avec un attribut 'tete'. Les méthodes courantes sont ajouter_en_tete, supprimer_en_tete, est_vide, et afficher.

Quels sont les cas d'usage des listes chaînées au bac NSI ?

Elles servent à implémenter des piles et des files, à gérer des listes d'attente, ou à modéliser des parcours de graphes (liste d'adjacence). L'épreuve pratique peut demander d'écrire des fonctions comme inverser une liste ou supprimer un élément.

Comment réviser les listes chaînées pour le bac NSI ?

Entraîne-toi à coder les opérations de base (ajout, suppression, recherche, parcours) sur papier et en Python. Révise les complexités temporelles et spatiales. Utilise des fiches et exercices disponibles sur nsi-lycee.fr.

Quelle est la complexité de l'ajout en queue d'une liste chaînée ?

Sans pointeur de queue, l'ajout en queue nécessite de parcourir toute la liste jusqu'au dernier nœud, soit O(n). Avec un pointeur de queue, on peut le faire en O(1).

NSI : tout savoir sur les listes chaînées

Les listes chaînées font partie des structures de données linéaires au programme de NSI en Terminale. Tu les croiseras souvent, que ce soit pour implémenter une file, une pile, ou pour comprendre le fonctionnement de la mémoire dynamique. Pas de panique : on va décortiquer ensemble ce concept, avec du code Python simple et des explications claires. Prêt·e ? C'est parti !

Qu'est-ce qu'une liste chaînée ?

Une liste chaînée est une structure de données linéaire dans laquelle chaque élément, appelé nœud, contient une valeur et un pointeur (ou référence) vers l'élément suivant. Contrairement à un tableau (list Python), les éléments ne sont pas stockés dans des cases contiguës en mémoire. Chaque nœud est un objet qui « pointe » vers le suivant, formant une chaîne.

Il existe plusieurs variantes :

Liste simplement chaînée : chaque nœud pointe vers le suivant.
Liste doublement chaînée : chaque nœud pointe vers le suivant et le précédent.
Liste circulaire : le dernier nœud pointe vers le premier.

En NSI, on se concentre surtout sur la version simplement chaînée.

Pourquoi utiliser une liste chaînée plutôt qu'un tableau ?

Les listes Python (tableaux dynamiques) sont très pratiques, mais elles ont des limitations :

Insérer ou supprimer un élément au début coûte O(n) car il faut décaler tous les éléments.
La mémoire est allouée par blocs contigus : si on ajoute beaucoup d'éléments, il peut y avoir un redimensionnement coûteux.

Avec une liste chaînée, l'insertion et la suppression en tête se font en O(1) : il suffit de modifier quelques pointeurs. En revanche, l'accès à un élément au milieu nécessite de parcourir la liste (O(n)). C'est un compromis classique.

Implémentation en Python

On va créer une classe Noeud et une classe ListeChainee. Voici le code de base :

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

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

    def est_vide(self):
        return self.tete is None

    def ajouter_en_tete(self, valeur):
        nouveau = Noeud(valeur)
        nouveau.suivant = self.tete
        self.tete = nouveau

    def supprimer_en_tete(self):
        if self.est_vide():
            return None
        valeur = self.tete.valeur
        self.tete = self.tete.suivant
        return valeur

    def afficher(self):
        courant = self.tete
        while courant is not None:
            print(courant.valeur, end=" -> ")
            courant = courant.suivant
        print("None")

Testons :

ma_liste = ListeChainee()
ma_liste.ajouter_en_tete(3)
ma_liste.ajouter_en_tete(2)
ma_liste.ajouter_en_tete(1)
ma_liste.afficher()  # 1 -> 2 -> 3 -> None
v = ma_liste.supprimer_en_tete()
print(v)  # 1
ma_liste.afficher()  # 2 -> 3 -> None

Remarque : chaque insertion se fait en O(1) car on ne fait que créer un nœud et modifier le pointeur de tête.

Opérations courantes et complexité

Voici les opérations typiques qu'on te demandera de coder au bac :

ajouter_en_tete : O(1)
supprimer_en_tete : O(1)
ajouter_en_queue : O(n) si on n'a pas de pointeur de queue (sinon O(1))
rechercher une valeur : O(n) dans le pire cas
insérer au milieu : O(n) pour trouver la position, puis O(1) pour insérer

Il est important de savoir justifier ces complexités : l'accès à un élément nécessite de parcourir la liste depuis la tête.

Cas d'usage concrets

Les listes chaînées sont utilisées dans :

Files et piles : en Python, on utilise souvent collections.deque qui est implémentée avec une liste doublement chaînée.
Gestion de la mémoire : les allocateurs mémoire (malloc) utilisent des listes chaînées de blocs libres.
Applications temps réel : insertion/suppression fréquentes en tête.

En NSI, tu peux les utiliser pour implémenter une file d'attente (FIFO) ou une pile (LIFO). Par exemple, une file avec deux listes chaînées (une pour l'entrée, une pour la sortie) est une astuce classique.

Conseils pour le bac NSI

Lors de l'épreuve pratique, on te demandera souvent d'écrire ou de compléter des fonctions manipulant des listes chaînées. Voici quelques conseils :

Dessine toujours la liste sur un brouillon : cela t'aide à visualiser les pointeurs.
Attention aux cas particuliers : liste vide, un seul élément, dernier élément.
Entraîne-toi à implémenter : ajout en queue, suppression d'une valeur donnée, inversion de liste, etc.
Révise les complexités : on te demandera souvent de justifier le coût d'une opération.

Tu trouveras des exercices types sur notre page d'exercices et des fiches récapitulatives sur les fiches. N'hésite pas à consulter aussi le cours complet sur les structures de données.

Pour approfondir, tu peux aussi jeter un œil aux ressources de Allo Lycée qui propose des exercices interactifs.

Conclusion

Les listes chaînées sont un outil fondamental en algorithmique. Elles te permettent de comprendre comment manipuler la mémoire dynamiquement et d'implémenter des structures plus complexes. Avec un peu de pratique, tu verras que c'est très logique. Continue à coder, à tester, et n'oublie pas : chaque nœud a une valeur et un suivant. Bon courage pour tes révisions !