Structures de données en prépa : listes, piles, files, arbres

Un même paquet de valeurs peut être rangé de mille façons en mémoire, et ce rangement décide de la vitesse de ton programme. Une structure de données, c'est exactement ça : une manière d'organiser l'information pour rendre rapides les opérations dont tu as vraiment besoin. Chercher un nom dans un annuaire trié ou dans un tas de fiches en vrac, c'est le même contenu, mais pas le même coût.

Cet article couvre les quatre structures au cœur de l'option informatique de prépa (MP2I en première année, MPI en seconde, et MPSI option info) : les listes Python et leurs opérations, les piles (LIFO), les files (FIFO), le principe des listes chaînées et les arbres binaires avec leur vocabulaire et leurs parcours. Tu y trouveras du code Python commenté qui implémente une pile et une file, un tableau de complexités exactes et trois exercices corrigés. Nos profs Hadamard, anciens de MP2I et de MPSI option info passés par l'X, l'ENS et CentraleSupélec, voient chaque année les mêmes confusions en TP : on les désamorce ici une à une.

Ce qu'est une structure de données

On distingue deux niveaux, et les confondre est la première source d'erreurs. Le type abstrait décrit ce que la structure fait : une pile promet « j'ajoute et je retire toujours du même côté ». L'implémentation décrit comment on le réalise concrètement : avec un tableau, une liste chaînée, un dictionnaire. Une même pile peut être implémentée de plusieurs manières ; ce qui compte pour l'utilisateur, c'est le contrat d'opérations, pas les coulisses.

Toute la question du chapitre tient en une phrase : quelles opérations mon programme fait-il le plus souvent, et quelle structure les rend les moins chères ? Ajouter en fin, retirer en tête, accéder au $i$-ème élément, chercher une valeur, parcourir dans l'ordre : chaque structure excelle sur certaines de ces opérations et se traîne sur d'autres. C'est ce compromis qu'on apprend à arbitrer, et il est indissociable de la notion de complexité algorithmique.

Les listes Python et leurs opérations

La list de Python n'est pas une liste chaînée malgré son nom : c'est un tableau dynamique, une zone contiguë de mémoire qui s'agrandit toute seule quand on la remplit. Cette structure interne explique tout son profil de coûts. Si tu débutes en Python, l'article les bases de Python en prépa pose les fondations manipulées ici.

Comme les éléments sont rangés côte à côte et repérés par leur position, accéder à tab[i] se fait en temps constant : on calcule directement l'adresse. En revanche, insérer ou supprimer ailleurs qu'à la fin oblige à décaler tous les éléments suivants.

Deux leçons pratiques. L'ajout en fin est dit « $O(1)$ amorti » : la plupart des append sont instantanés, seuls quelques-uns coûtent cher quand le tableau doit s'agrandir, mais la moyenne reste constante. Surtout, pop(0) est un piège : retirer le premier élément décale tout le reste, donc gérer une file avec une list et pop(0) est lent. C'est précisément là qu'interviennent les structures suivantes.

La pile, principe LIFO

Une pile (stack) suit le principe LIFO : Last In, First Out, le dernier entré est le premier sorti. L'image juste est une pile d'assiettes : on pose et on retire toujours celle du dessus. Deux opérations suffisent : empiler (ajouter au sommet) et dépiler (retirer le sommet), auxquelles on ajoute la consultation du sommet et le test de vacuité.

Comme on travaille toujours au même bout, une list Python fait une pile parfaite : append pour empiler et pop pour dépiler, deux opérations en $O(1)$. Voici une implémentation encapsulée dans une classe, telle qu'on l'attend en TP.

class Pile:
    """Pile LIFO : le dernier empile est le premier depile."""

    def __init__(self):
        self.elements = []              # liste Python utilisee comme support

    def est_vide(self):
        return self.elements == []      # True si la pile ne contient rien

    def empiler(self, x):
        self.elements.append(x)         # ajout au sommet (fin de liste) : O(1)

    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        return self.elements.pop()      # retrait du sommet (fin de liste) : O(1)

    def sommet(self):
        if self.est_vide():
            raise IndexError("sommet d'une pile vide")
        return self.elements[-1]        # consultation du sommet sans le retirer

    def taille(self):
        return len(self.elements)

La file, principe FIFO

Une file (queue) suit le principe FIFO : First In, First Out, le premier entré est le premier sorti, exactement comme une file d'attente à un guichet. On enfile à une extrémité et on défile à l'autre. La difficulté d'implémentation est là : contrairement à la pile, on travaille aux deux bouts, or retirer en tête d'une list coûte $O(n)$.

La solution standard en Python est le deque du module collections, une file à double extrémité qui autorise l'ajout et le retrait aux deux bouts en $O(1)$. On l'utilise comme support interne.

from collections import deque

class File:
    """File FIFO : le premier enfile est le premier defile."""

    def __init__(self):
        self.elements = deque()             # deque : ajout/retrait aux 2 bouts en O(1)

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

    def enfiler(self, x):
        self.elements.append(x)             # ajout a droite (queue) : O(1)

    def defiler(self):
        if self.est_vide():
            raise IndexError("defiler sur une file vide")
        return self.elements.popleft()      # retrait a gauche (tete) : O(1)

    def taille(self):
        return len(self.elements)

Les listes chaînées, le principe

Une liste chaînée range ses éléments autrement qu'un tableau : au lieu d'une zone contiguë de mémoire, chaque élément est une cellule qui contient une valeur et un lien (une référence) vers la cellule suivante. La dernière cellule pointe vers None. On ne connaît que l'adresse de la première cellule, la tête, et l'on suit les liens de proche en proche.

Ce choix inverse le profil de coûts par rapport au tableau. Insérer une valeur en tête est immédiat, en $O(1)$ : on crée une cellule et on la fait pointer vers l'ancienne tête, sans rien décaler. En revanche, atteindre le $i$-ème élément oblige à parcourir les liens un par un depuis la tête, donc en $O(n)$ : pas d'accès direct par indice.

En Python, on modélise une cellule par une petite classe portant une valeur et un attribut suivant. La liste chaînée est surtout la structure conceptuelle qui sous-tend piles et files, et c'est un support privilégié d'exercices récursifs, chaque cellule menant à une sous-liste plus courte.

Les arbres binaires, vocabulaire et parcours

Un arbre range l'information de façon hiérarchique plutôt que linéaire. Le vocabulaire est à connaître par cœur : un nœud contient une valeur ; la racine est le nœud du sommet, unique et sans parent ; une feuille est un nœud sans enfant ; les liens entre nœuds sont les arêtes. Chaque nœud sauf la racine a exactement un parent, et l'ensemble des descendants d'un nœud forme un sous-arbre.

Un arbre binaire est le cas où chaque nœud possède au plus deux enfants : un sous-arbre gauche et un sous-arbre droit. On le modélise naturellement en Python par une classe de nœud, où un sous-arbre absent vaut None.

class Noeud:
    """Noeud d'un arbre binaire : une valeur et deux sous-arbres."""

    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche            # sous-arbre gauche (Noeud ou None)
        self.droit = droit              # sous-arbre droit (Noeud ou None)

Parcourir un arbre, c'est visiter tous ses nœuds dans un ordre précis. On distingue les parcours en profondeur, naturellement récursifs, et le parcours en largeur, qui s'appuie sur une file.

• Préfixe (racine, gauche, droite) : on traite un nœud avant ses sous-arbres.
• Infixe (gauche, racine, droite) : sur un arbre binaire de recherche, il restitue les valeurs dans l'ordre croissant.
• Suffixe (gauche, droite, racine) : on traite un nœud après ses sous-arbres, utile pour libérer ou évaluer.
• En largeur : on visite niveau par niveau, de gauche à droite, à l'aide d'une file.

Le parcours infixe s'écrit en trois lignes, la récursivité épousant la structure de l'arbre :

def parcours_infixe(n):
    """Gauche - Racine - Droite. Sur un ABR, renvoie les valeurs triees."""
    if n is None:
        return []                       # cas de base : arbre vide
    return parcours_infixe(n.gauche) + [n.valeur] + parcours_infixe(n.droit)

Le parcours en largeur, lui, illustre parfaitement l'usage d'une file : on enfile la racine, puis tant que la file n'est pas vide, on défile un nœud, on le traite et on enfile ses enfants. L'ordre FIFO garantit qu'un niveau entier est visité avant le suivant.

from collections import deque

def parcours_largeur(racine):
    """Visite niveau par niveau, a l'aide d'une file (FIFO)."""
    if racine is None:
        return []
    resultat = []
    f = deque([racine])                 # on enfile la racine
    while f:
        n = f.popleft()                 # on defile le plus ancien noeud
        resultat.append(n.valeur)
        if n.gauche is not None:
            f.append(n.gauche)          # on enfile l'enfant gauche
        if n.droit is not None:
            f.append(n.droit)           # puis l'enfant droit
    return resultat

La complexité des opérations, récapitulatif

Ce tableau est la carte à mémoriser pour choisir vite en TP ou à l'oral. Il donne la complexité de l'opération la plus caractéristique de chaque structure. Toute la logique du choix découle de ces coûts.

Sur un ABR, retiens bien la nuance : les $O(\log n)$ ne valent que si l'arbre reste équilibré. Dans le pire cas (arbre dégénéré), on retombe à $O(n)$. C'est pourquoi les structures réelles utilisent des arbres auto-équilibrés, hors programme mais bon à citer à l'oral.

Le bon choix selon le problème

Face à un énoncé, la bonne réflexe n'est pas « quelle structure connais-je ? » mais « quelle est l'opération que mon programme répète le plus, et qui la rend gratuite ? ». Voici la grille de décision qui recouvre l'immense majorité des cas.

Ce raisonnement est exactement celui que le jury valorise au Grand Oral et en TP, et il prolonge naturellement le chapitre d'algorithmique et complexité : une bonne structure de données est souvent ce qui fait passer un algorithme de $O(n^2)$ à $O(n \log n)$.

Trois exercices corrigés

Les corrigés réutilisent les classes Pile, File et Noeud définies plus haut. Chaque exercice cible un réflexe attendu en option informatique.

Exercice 1, la pile pour le parenthésage

Énoncé. Écrire une fonction qui teste si les parenthèses d'une chaîne sont bien équilibrées : chaque parenthèse ouvrante doit être refermée, dans le bon ordre. Ainsi "(a(b)c)" est correct, mais "(a))" et "((" ne le sont pas.

Idée. C'est l'application reine de la pile. On lit la chaîne de gauche à droite : chaque ouvrante est empilée, chaque fermante doit correspondre à la dernière ouvrante non refermée, donc au sommet de la pile. À la fin, la pile doit être vide.

def bien_parenthesee(chaine):
    """True si les parentheses de la chaine sont bien equilibrees."""
    pile = Pile()
    for caractere in chaine:
        if caractere == "(":
            pile.empiler(caractere)         # une ouvrante de plus en attente
        elif caractere == ")":
            if pile.est_vide():
                return False                # fermante sans ouvrante : echec
            pile.depiler()                  # on referme la derniere ouverte
    return pile.est_vide()                  # vrai si rien ne reste en attente

Vérification. Sur "(a(b)c)" : on empile (, puis (, le ) dépile, le dernier ) dépile, la pile est vide, on renvoie True. Sur "(a))" : la deuxième fermante trouve la pile vide, on renvoie False. Sur "((" : la pile reste non vide à la fin, on renvoie False. La complexité est $O(n)$, un seul passage sur la chaîne.

Exercice 2, inverser une file avec une pile

Énoncé. On dispose d'une file. Écrire une fonction qui inverse l'ordre de ses éléments, sans utiliser d'autre structure qu'une pile. Après l'appel, ce qui était en tête doit se retrouver en queue.

Idée. C'est l'exercice qui fait sentir la différence LIFO / FIFO. On vide entièrement la file dans une pile : l'ordre s'inverse une première fois. Puis on vide la pile dans la file : comme la pile ressort ses éléments à l'envers, la file se retrouve inversée par rapport au départ.

def inverser_file(f):
    """Inverse l'ordre des elements d'une file a l'aide d'une pile."""
    pile = Pile()
    while not f.est_vide():
        pile.empiler(f.defiler())       # FIFO -> pile : on vide la file
    while not pile.est_vide():
        f.enfiler(pile.depiler())       # pile -> FIFO : la pile ressort a l'envers
    return f

Vérification. Partons d'une file contenant, de la tête vers la queue, 1, 2, 3. On défile 1 puis 2 puis 3 et on les empile : le sommet de la pile est 3. On dépile 3, 2, 1 et on les enfile : la file contient désormais 3, 2, 1, elle est bien inversée. Complexité $O(n)$, chaque élément est déplacé deux fois.

Exercice 3, hauteur et feuilles d'un arbre

Énoncé. Pour un arbre binaire donné par sa racine, écrire deux fonctions récursives : l'une renvoie sa hauteur (nombre d'arêtes du plus long chemin de la racine à une feuille, avec la convention hauteur $-1$ pour l'arbre vide et $0$ pour une feuille seule), l'autre compte son nombre de feuilles.

Idée. La structure récursive de l'arbre dicte le code. Pour la hauteur, un arbre non vide mesure $1$ plus la hauteur du plus haut de ses deux sous-arbres. Pour les feuilles, un nœud sans enfant compte pour $1$, sinon on additionne les feuilles des deux sous-arbres.

def hauteur(n):
    """Hauteur d'un arbre binaire. Vide : -1. Feuille seule : 0."""
    if n is None:
        return -1                                   # cas de base : arbre vide
    return 1 + max(hauteur(n.gauche), hauteur(n.droit))

def nb_feuilles(n):
    """Nombre de feuilles (noeuds sans enfant)."""
    if n is None:
        return 0
    if n.gauche is None and n.droit is None:
        return 1                                    # un noeud sans enfant : une feuille
    return nb_feuilles(n.gauche) + nb_feuilles(n.droit)

Vérification. Prenons l'arbre Noeud(1, Noeud(2), Noeud(3, Noeud(4))) : la racine 1, à gauche la feuille 2, à droite le nœud 3 qui porte à gauche la feuille 4. La branche la plus longue est 1 → 3 → 4, soit deux arêtes, donc hauteur renvoie 2. Les feuilles sont 2 et 4, donc nb_feuilles renvoie 2. Chaque fonction visite chaque nœud une fois, la complexité est $O(n)$.

Ce qu'il faut retenir

• La liste Python est un tableau dynamique : accès et ajout en fin en $O(1)$, mais insertion en tête et recherche en $O(n)$.
• La pile (LIFO) : empiler et dépiler au même bout, en $O(1)$. Pour tout ce qui revient en arrière, dont la récursivité.
• La file (FIFO) : enfiler et défiler aux deux bouts en $O(1)$ grâce au deque. Jamais avec pop(0) d'une liste.
• La liste chaînée : insertion en tête en $O(1)$, mais accès au $i$-ème élément en $O(n)$, le profil inverse du tableau.
• L'arbre binaire : racine, nœuds, feuilles, deux sous-arbres ; parcours préfixe, infixe, suffixe (récursifs) et en largeur (avec une file).
• L'ABR équilibré : recherche, insertion, suppression en $O(\log n)$ ; $O(n)$ s'il dégénère.
• Le choix se fait toujours en identifiant l'opération critique du programme et la structure qui la rend la moins chère.

Ces structures forment le socle de l'option informatique et reviennent partout : dans les algorithmes de tri et de recherche, dans les parcours de graphes, dans la récursivité. Elles sont indissociables de l'algorithmique et de la complexité, qui en mesurent l'efficacité.

Si tu hésites encore à prendre l'informatique en prépa, notre panorama de l'option info en MPSI détaille ce qu'on y fait vraiment et à quelles poursuites d'études elle mène.