Listes, piles, files, dictionnaires

Introduction

Une structure linéaire organise ses éléments dans un ordre : chaque élément a (au plus) un précédent et un suivant. Quatre structures dominent le programme de Terminale, qui se distinguent non par leur forme mais par leurs opérations autorisées. On retient une structure pour ce qu'elle permet, pas pour ce qu'elle contient.

Cet item [TA03] demande explicitement de distinguer les structures par le jeu des méthodes qui les caractérisent et de savoir choisir la bonne en fonction de la situation.

Vue d'ensemble

La pile (LIFO)

Une pile fonctionne comme une pile d'assiettes dans un placard : la dernière posée est la première reprise, et l'on n'accède qu'au sommet. Implémentation directe par liste Python : on opère toujours à la fin de la liste, ce qui est en $\mathcal{O}(1)$ amorti :

class Pile:
    def __init__(self):
        self._data = []
    def empiler(self, x):
        self._data.append(x)
    def depiler(self):
        if not self._data:
            raise IndexError("pile vide")
        return self._data.pop()
    def sommet(self):
        return self._data[-1]
    def est_vide(self):
        return not self._data
    def __len__(self):
        return len(self._data)       # permet d'écrire len(p)

Cas d'usage typiques : pile d'appels d'un programme récursif, retour-arrière (navigation web, undo), parcours en profondeur d'un graphe.

La file (FIFO)

Une file fonctionne comme une salle d'attente chez le médecin : on arrive par la fin, on passe par le début, dans l'ordre d'arrivée. On a vu au cours précédent deux implémentations (par liste, par deux piles). L'implémentation idiomatique en Python utilise collections.deque, qui offre le $\mathcal{O}(1)$ aux deux extrémités :

from collections import deque

class File:
    def __init__(self):
        self._data = deque()
    def enfiler(self, x):
        self._data.append(x)
    def defiler(self):
        if not self._data:
            raise IndexError("file vide")
        return self._data.popleft()
    def est_vide(self):
        return not self._data

Cas d'usage : file d'impression, parcours en largeur d'un graphe, gestion de tâches en attente.

Le dictionnaire

Un dictionnaire associe des clés à des valeurs, comme un annuaire téléphonique associe un nom à un numéro. On y accède par clé, pas par position. Les clés sont uniques. En Python, c'est le type dict.

notes = {"Alice": 14, "Bob": 11, "Camille": 16}
notes["Alice"]          # 14
notes["Dimitri"] = 9    # ajout
"Bob" in notes          # True
del notes["Bob"]

Recherche d'une valeur :

• Dans une liste, chercher si x est présent coûte $\mathcal{O}(n)$ en moyenne.
• Dans un dictionnaire, k in d coûte $\mathcal{O}(1)$ en moyenne grâce à une table de hachage interne. C'est l'un de ses principaux avantages.

Choisir la bonne structure

Pour aller plus loin

Le module collections contient deux variantes utiles : deque (file double) et OrderedDict (dictionnaire qui mémorise l'ordre d'insertion ; en pratique, les dict Python 3.7+ le font par défaut).