Partie 2 : Structures linéaires - listes, piles et files

Programme officiel (B.O.)

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Listes, piles, files : structures linéaires. Dictionnaires, index et clé.	Distinguer des structures par le jeu des méthodes qui les caractérisent. Choisir une structure de données adaptée à la situation à modéliser. Distinguer la recherche d'une valeur dans une liste et dans un dictionnaire.	On distingue les listes chaînées des tableaux (listes Python). Les listes chaînées sont traitées en tant que structures de données récursives.

---

1. Listes chaînées

1.1 Principe

Une liste chaînée est une suite d'éléments où chaque élément (appelé maillon ou nœud) contient :

• une valeur ;
• une référence vers le maillon suivant (ou None si c'est le dernier).

┌───┬───┐   ┌───┬───┐   ┌───┬───┐
│ 5 │ ──┼──>│ 8 │ ──┼──>│ 3 │ / │
└───┴───┘   └───┴───┘   └───┴───┘
  tête                     queue

C'est une structure récursive : une liste chaînée est soit vide, soit un maillon suivi d'une liste chaînée.

1.2 Comparaison avec les tableaux Python

Opération	Tableau (list)	Liste chaînée
Accès par index	O(1) - direct	O(n) - il faut parcourir
Insertion en tête	O(n) - décalage de tous les éléments	O(1) - rapide
Insertion en fin	O(1) amorti	O(n) sauf si on garde une référence vers la queue
Recherche d'une valeur	O(n) - parcours	O(n) - parcours

1.3 Implémentation en Python

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

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

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

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

    def longueur(self):
        compteur = 0
        courant = self.tete
        while courant is not None:
            compteur += 1
            courant = courant.suivant
        return compteur

    def contient(self, valeur):
        courant = self.tete
        while courant is not None:
            if courant.valeur == valeur:
                return True
            courant = courant.suivant
        return False

    def __str__(self):
        elements = []
        courant = self.tete
        while courant is not None:
            elements.append(str(courant.valeur))
            courant = courant.suivant
        return " → ".join(elements)

lst = ListeChainee()
lst.ajouter_en_tete(3)
lst.ajouter_en_tete(8)
lst.ajouter_en_tete(5)
print(lst)              # 5 → 8 → 3
print(lst.longueur())   # 3
print(lst.contient(8))  # True

1.4 Version récursive

La nature récursive de la liste chaînée se prête bien à des fonctions récursives :

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

def contient_rec(maillon, valeur):
    if maillon is None:
        return False
    if maillon.valeur == valeur:
        return True
    return contient_rec(maillon.suivant, valeur)

---

2. Piles

2.1 Interface

Une pile (stack) suit le principe LIFO (Last In, First Out) : le dernier élément ajouté est le premier retiré. Comme une pile d'assiettes.

Opération	Description
empiler(x)	Ajouter x au sommet
depiler()	Retirer et renvoyer l'élément du sommet
est_vide()	Tester si la pile est vide
sommet()	Consulter l'élément du sommet sans le retirer

2.2 Implémentation avec un tableau

class Pile:
    def __init__(self):
        self.elements = []

    def empiler(self, x):
        self.elements.append(x)

    def depiler(self):
        assert not self.est_vide(), "Pile vide"
        return self.elements.pop()

    def est_vide(self):
        return len(self.elements) == 0

    def sommet(self):
        assert not self.est_vide(), "Pile vide"
        return self.elements[-1]

    def __str__(self):
        return str(self.elements)

p = Pile()
p.empiler(10)
p.empiler(20)
p.empiler(30)
print(p.sommet())   # 30
print(p.depiler())  # 30 (le dernier ajouté)
print(p.depiler())  # 20

2.3 Implémentation avec une liste chaînée

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

    def empiler(self, x):
        self.tete = Maillon(x, self.tete)

    def depiler(self):
        assert self.tete is not None, "Pile vide"
        valeur = self.tete.valeur
        self.tete = self.tete.suivant
        return valeur

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

    def sommet(self):
        assert self.tete is not None, "Pile vide"
        return self.tete.valeur

Deux implémentations différentes, même interface : c'est la distinction interface/implémentation en action.

2.4 Applications des piles

• Historique de navigation : le bouton « retour » dépile la dernière page visitée ;
• Annulation (Ctrl+Z) : chaque action est empilée, annuler = dépiler ;
• Évaluation d'expressions avec parenthèses ;
• Appels de fonctions : chaque appel est empilé, le retour dépile.

---

3. Files

3.1 Interface

Une file (queue) suit le principe FIFO (First In, First Out) : le premier élément ajouté est le premier retiré. Comme une file d'attente.

Opération	Description
enfiler(x)	Ajouter x à la fin
defiler()	Retirer et renvoyer l'élément du début
est_vide()	Tester si la file est vide

3.2 Implémentation avec un tableau

class FileTableau:
    def __init__(self):
        self.elements = []

    def enfiler(self, x):
        self.elements.append(x)

    def defiler(self):
        assert not self.est_vide(), "File vide"
        return self.elements.pop(0)

    def est_vide(self):
        return len(self.elements) == 0

Attention

pop(0) est en O(n) car il faut décaler tous les éléments. Pour de meilleures performances, on utilise collections.deque ou l'implémentation avec deux piles.

3.3 Implémentation avec deux piles

Une file peut être réalisée avec deux piles, ce qui donne un coût amorti en O(1) par opération :

class File:
    def __init__(self):
        self.entree = Pile()
        self.sortie = Pile()

    def enfiler(self, x):
        self.entree.empiler(x)

    def defiler(self):
        if self.sortie.est_vide():
            while not self.entree.est_vide():
                self.sortie.empiler(self.entree.depiler())
        return self.sortie.depiler()

    def est_vide(self):
        return self.entree.est_vide() and self.sortie.est_vide()

Le transfert inverse l'ordre : le premier entré se retrouve au sommet de la pile de sortie.

3.4 Applications des files

• File d'impression : les documents s'impriment dans l'ordre d'envoi ;
• Gestion de processus par le système d'exploitation (ordonnancement) ;
• Parcours en largeur d'un graphe ou d'un arbre ;
• Mémoire tampon (buffer) : données traitées dans l'ordre d'arrivée.

---

4. Dictionnaires

4.1 Principe

Un dictionnaire associe des clés à des valeurs. Chaque clé est unique et permet d'accéder directement à la valeur associée.

eleve = {
    "nom": "Dupont",
    "prenom": "Alice",
    "age": 17,
    "classe": "Terminale"
}

print(eleve["prenom"])      # "Alice"
eleve["moyenne"] = 15.5     # ajout d'une entrée
del eleve["age"]            # suppression

4.2 Interface

Opération	Description	Complexité moyenne
d[cle]	Accéder à la valeur associée à cle	O(1)
d[cle] = val	Ajouter ou modifier une entrée	O(1)
del d[cle]	Supprimer une entrée	O(1)
cle in d	Tester la présence d'une clé	O(1)

4.3 Comparaison avec les listes

Opération	Liste	Dictionnaire
Recherche par valeur	O(n) - parcours séquentiel	O(1) - par la clé
Accès par position	O(1) - par index	Non applicable
Ordre des éléments	Par position (index)	Par insertion (Python 3.7+)

Quand utiliser un dictionnaire ?

Quand on veut retrouver rapidement une information à partir d'un identifiant unique (nom, code, clé). Quand on veut associer des données de nature différente à un même objet.

---

5. Choisir la bonne structure

Situation	Structure adaptée	Raison
Historique / annulation	Pile (LIFO)	On revient à l'action la plus récente
File d'attente / impression	File (FIFO)	On traite dans l'ordre d'arrivée
Insertions/suppressions en tête fréquentes	Liste chaînée	O(1) en tête
Accès rapide par identifiant	Dictionnaire	O(1) par clé
Accès rapide par position	Tableau (list)	O(1) par index

---

À retenir

Structure	Principe	Opérations clés	Complexité
Liste chaînée	Maillons reliés par des références	Ajout en tête, parcours	O(1) en tête, O(n) accès
Pile	LIFO (dernier entré, premier sorti)	empiler, dépiler, sommet	O(1)
File	FIFO (premier entré, premier sorti)	enfiler, défiler	O(1) amorti
Dictionnaire	Paires clé-valeur	Accès, ajout, suppression	O(1) en moyenne