Algorithmique : structures de données

Tableaux, piles, files, listes chaînées, tables de hachage

Claire Borrelli

2023-12-11

Plan

Interface vs implémentation
Le tableau (liste Python)
La pile (LIFO)
La file (FIFO)
La liste chaînée
La table de hachage
Bilan comparatif

1. Interface vs implémentation

Deux notions à distinguer

Interface : ce que la structure propose à l’utilisateur (les opérations disponibles) — ce qu’on voit
Implémentation : comment ces opérations sont réalisées en mémoire — ce qu’on ne voit pas

Exemple — un distributeur de billets : l’interface, c’est l’écran et les boutons ; l’implémentation, c’est tout le mécanisme interne. On peut changer l’implémentation sans changer l’interface, et inversement.

On étudie ici quatre structures classiques, chacune avec ses forces et ses coûts.

2. Le tableau (liste Python)

Principe

Un tableau stocke des éléments dans des cases mémoire contiguës et numérotées. Connaître l’indice suffit pour accéder directement à un élément.

notes = [12, 15, 9, 17, 14]
notes[2]  # accès direct, O(1)

Coût des opérations

Opération	Complexité
Lire `notes[i]`	\(O(1)\)
Ajouter à la fin (`append`)	\(O(1)\) en moyenne
Insérer au milieu / au début	\(O(n)\)
Supprimer au milieu / au début	\(O(n)\)

Insérer ou supprimer ailleurs qu’à la fin coûte cher : il faut décaler tous les éléments suivants.

Vérification empirique

import time
import matplotlib.pyplot as plt

tailles = [1000, 5000, 10000, 20000, 40000]
temps_append, temps_insert_debut = [], []

for n in tailles:
    liste = list(range(n))
    debut = time.perf_counter()
    liste.append(0)
    temps_append.append(time.perf_counter() - debut)

    liste = list(range(n))
    debut = time.perf_counter()
    liste.insert(0, 0)  # insertion au début : décale tout
    temps_insert_debut.append(time.perf_counter() - debut)

plt.figure(figsize=(7, 4.5))
plt.plot(tailles, temps_append, marker="o", label="append (fin)")
plt.plot(tailles, temps_insert_debut, marker="o", label="insert(0, ...) (début)")
plt.xlabel("Taille de la liste"); plt.ylabel("Temps (s)")
plt.title("append vs insert(0, ...) selon la taille")
plt.legend(); plt.tight_layout(); plt.show()

3. La pile (LIFO)

Dernier arrivé, premier sorti

Une pile (stack) ne permet d’accéder qu’à son élément le plus récent — comme une pile d’assiettes : on ne peut retirer que celle du dessus.

empiler (push) : ajouter un élément au sommet — \(O(1)\)
dépiler (pop) : retirer l’élément au sommet — \(O(1)\)
sommet (peek) : lire l’élément au sommet sans le retirer — \(O(1)\)

Implémentation en Python

Une liste Python fait très bien l’affaire : append = empiler, pop() = dépiler.

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

    def empiler(self, element):
        self._donnees.append(element)

    def depiler(self):
        return self._donnees.pop() if self._donnees else None

    def sommet(self):
        return self._donnees[-1] if self._donnees else None

historique = Pile()
historique.empiler("page A")
historique.empiler("page B")
historique.empiler("page C")
historique.depiler()  # on revient en arrière : "page C" est retirée
historique.sommet()   # "page B"

'page B'

Cas d’usage typique : l’historique de navigation d’un navigateur, ou l’annulation (Ctrl+Z) dans un éditeur.

4. La file (FIFO)

Premier arrivé, premier servi

Une file (queue) fonctionne comme une file d’attente : le premier élément ajouté est le premier retiré.

enfiler (enqueue) : ajouter à la fin — \(O(1)\)
défiler (dequeue) : retirer le premier élément — \(O(1)\) (avec la bonne implémentation)

Le piège d’une implémentation naïve

file_naive = [1, 2, 3, 4, 5]
file_naive.pop(0)  # retire le premier élément... mais décale tout le reste !

pop(0) sur une liste Python coûte \(O(n)\), car tous les éléments doivent être décalés d’une case. Pour une vraie file efficace, on utilise collections.deque :

from collections import deque

guichet = deque()
guichet.append("client 1")
guichet.append("client 2")
guichet.append("client 3")
guichet.popleft()  # "client 1" — retrait en O(1), pas de décalage

'client 1'

5. La liste chaînée

Principe

Chaque élément (un maillon) connaît seulement l’élément suivant — comme des wagons de train reliés un à un, sans numérotation globale des places.

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

# Construction manuelle d'une petite liste chaînée : 3 -> 7 -> 1
liste = Maillon(3, Maillon(7, Maillon(1)))

# Parcours
courant = liste
valeurs = []
while courant is not None:
    valeurs.append(courant.valeur)
    courant = courant.suivant
valeurs

[3, 7, 1]

Coût des opérations

Opération	Tableau	Liste chaînée
Accès par indice	\(O(1)\)	\(O(n)\)
Insertion/suppression en tête	\(O(n)\)	\(O(1)\)
Recherche d’une valeur	\(O(n)\)	\(O(n)\)

Insérer ou retirer un maillon ne demande que de modifier deux liens — pas de décaler des éléments. En contrepartie, on perd l’accès direct par indice : il faut parcourir la liste depuis le début.

6. La table de hachage

Le problème : stocker des paires clé-valeur

On veut retrouver rapidement une valeur à partir d’une clé — par exemple, la note d’un élève à partir de son nom.

notes_par_nom = {"Claire": 17, "Merlin": 14, "Ting": 19}
notes_par_nom["Merlin"]  # accès direct, en moyenne O(1)

C’est exactement ce que fait un dictionnaire Python — implémenté avec une table de hachage.

Le principe

Une fonction de hachage transforme chaque clé en un indice dans un grand tableau
La paire (clé, valeur) est stockée à cet indice
Pour retrouver une valeur, on re-hache la clé et on va directement à la bonne case

Le problème des collisions : deux clés différentes peuvent produire le même indice. On gère ça en stockant une petite liste chaînée à chaque case (chaînage) — plusieurs paires cohabitent alors sur le même indice.

Une implémentation simplifiée

class TableHachage:
    def __init__(self, taille=16):
        self._cases = [[] for _ in range(taille)]
        self._taille = taille

    def _indice(self, cle):
        return hash(cle) % self._taille

    def inserer(self, cle, valeur):
        case = self._cases[self._indice(cle)]
        for i, (c, _) in enumerate(case):
            if c == cle:
                case[i] = (cle, valeur)
                return
        case.append((cle, valeur))

    def rechercher(self, cle):
        for c, v in self._cases[self._indice(cle)]:
            if c == cle:
                return v
        return None

table = TableHachage()
table.inserer("Claire", 17)
table.inserer("Merlin", 14)
table.rechercher("Merlin")

Pourquoi c’est (presque toujours) rapide

Cas moyen : si la fonction de hachage répartit bien les clés, chaque case contient peu d’éléments → recherche, insertion, suppression en \(O(1)\) en moyenne
Pire cas : si toutes les clés tombent dans la même case (mauvaise fonction de hachage, ou volontairement provoqué), la recherche redevient \(O(n)\)
D’où l’importance d’une bonne fonction de hachage : déterministe, rapide à calculer, et qui répartit les clés le plus uniformément possible

7. Bilan comparatif

Quelle structure pour quel besoin ?

Opération	Tableau	Pile	File	Liste chaînée	Table de hachage
Accès par indice	\(O(1)\)	—	—	\(O(n)\)	—
Ajout/retrait aux extrémités	\(O(n)\)*	\(O(1)\)	\(O(1)\)	\(O(1)\)	—
Recherche par clé	—	—	—	—	\(O(1)\) moy.

* \(O(1)\) seulement à la fin d’un tableau.

Aucune structure n’est universellement meilleure. Le bon choix dépend de l’opération la plus fréquente dans votre programme : accès direct → tableau ; annulation/retour en arrière → pile ; traitement dans l’ordre d’arrivée → file ; insertions fréquentes en tête → liste chaînée ; recherche par clé → table de hachage.

Conclusion

Interface (ce qu’on utilise) et implémentation (comment ça marche) sont deux choses différentes
Chaque structure de données a un profil de coût différent selon l’opération
Choisir la bonne structure, c’est d’abord identifier l’opération dominante de son programme