#Structures de donnéesCopier le lien

Le choix d'une structure détermine quelles opérations sont simples et efficaces. Python offre quatre collections de base: liste (séquence ordonnée modifiable), tuple (séquence ordonnée immuable), dictionnaire (association clé-valeur) et ensemble (éléments uniques, test d'appartenance rapide).

Prérequis: variables et types (mutabilité, aliasing).

Objectifs d'apprentissage:

• Choisir la collection adaptée: séquence, association, unicité.
• Connaître les opérations courantes et leurs ordres de grandeur.
• Utiliser les tuples pour les enregistrements et retours multiples.
• Éviter le piège de la modification pendant itération.

#ListesCopier le lien

Une liste est une séquence ordonnée et mutable. L'accès par index est direct (xs[0], coût constant); l'insertion en tête décale tous les éléments (coût linéaire).

1a = [3, 1, 2]2a.append(4)        # ajout en fin: [3, 1, 2, 4]3a.sort()           # tri en place4print(a)           # [1, 2, 3, 4]5print(a[1:])       # [2, 3, 4]6print(sum(a), max(a), a.index(3))   # 10 4 2

Les tranches (a[1:]) produisent une nouvelle liste: a[debut:fin] va de l'index debut inclus à fin exclu. Le tri en place a.sort() modifie la liste et retourne None, tandis que sorted(a) retourne une nouvelle liste triée sans toucher à l'originale.

#TuplesCopier le lien

Un tuple est une séquence ordonnée immuable, adaptée aux enregistrements de petite taille (coordonnées, paires clé-valeur) et aux retours multiples.

1point = (3, 4)2x, y = point              # déballage3print(x, y)               # 3 44 5def min_max(valeurs: list[int]) -> tuple[int, int]:6    return min(valeurs), max(valeurs)7 8bas, haut = min_max([12, 9, 18])9print(bas, haut)          # 9 18

L'immuabilité rend les tuples hachables (s'ils ne contiennent que des hachables): ils servent de clés de dictionnaire, ce que les listes ne peuvent pas.

1distances = {(3, 4): 5}2# distances[[3, 4]] = 5   # TypeError: unhashable type: 'list'

#DictionnairesCopier le lien

Un dictionnaire associe des clés (immuables et hachables) à des valeurs. La recherche par clé est quasi constante, ce qui en fait la structure de choix pour "associer".

1prix = {'pomme': 1.2, 'banane': 2.0}2prix['cerise'] = 3.5                  # ajout3print(prix['pomme'])                  # 1.24print(prix.get('kiwi', 0))            # 0 (clé absente, valeur par défaut)5 6for fruit, p in sorted(prix.items()):7    print(f"{fruit}: {p} €")8# Sortie:9# banane: 2.0 €10# cerise: 3.5 €11# pomme: 1.2 €

.get(cle, defaut) évite le KeyError des clés absentes. Trois méthodes de parcours: .items() (paires), .keys() (clés), .values() (valeurs).

Comptage idiomatique: le dictionnaire est la structure naturelle pour compter des occurrences.

1mots = ['le', 'chat', 'le', 'chien', 'le']2compteur = {}3for mot in mots:4    compteur[mot] = compteur.get(mot, 0) + 15print(compteur)   # {'le': 3, 'chat': 1, 'chien': 1}

#EnsemblesCopier le lien

Un ensemble stocke des éléments uniques sans ordre. Deux usages: dédupliquer, et tester l'appartenance en temps quasi constant.

1s = {1, 2, 3}2s.add(3)                 # déjà présent: rien ne change3print(s, len(s))         # {1, 2, 3} 34 5a, b = {1, 2, 3}, {2, 3, 4}6print(a | b)             # union: {1, 2, 3, 4}7print(a & b)             # intersection: {2, 3}8print(a - b)             # différence: {1}9 10print(sorted({5, 5, 3, 1}))   # [1, 3, 5]: déduplication puis tri11print(2 in a)                 # True, test rapide

#Choisir: tableau de décisionCopier le lien

Pour n éléments, parcourir une liste ou un dictionnaire coûte n étapes; tester x in liste coûte jusqu'à n comparaisons, x in ensemble quasi constant: sur un million d'éléments, la différence se voit.

#Ce que la structure impose: coûts comparésCopier le lien

Les collections Python ne sont pas interchangeables, et le cours d'algorithmique justifie ces différences par la représentation en mémoire. Un tableau est une zone contiguë: l'élément d'indice i se calcule par une adresse, ce qui donne un accès direct. Une liste chaînée est une suite de maillons reliés par des pointeurs: pour atteindre le k-ième élément, il faut traverser les k-1 précédents.

Le point à retenir est le compromis: le tableau gagne sur l'accès, la liste chaînée sur la modification en tête. Aucune structure n'est meilleure partout, et c'est la raison pour laquelle le choix de la structure précède l'écriture de l'algorithme.

En Python, la liste combine les deux régimes: a[i] est direct, a.append(x) est en temps constant amorti, mais a.insert(0, x) décale tous les éléments et coûte Θ(n). Pour empiler en tête de façon répétée, on utilise collections.deque.

#Pile et fileCopier le lien

Une pile (LIFO, dernier entré premier sorti) et une file (FIFO, premier entré premier sorti) ne diffèrent que par l'extrémité où l'on retire:

1from collections import deque2 3# Pile : on empile et on dépile par la fin4pile = []5pile.append(1); pile.append(2); pile.append(3)6print(pile.pop())          # 3, le dernier entré7 8# File : on ajoute par la fin, on retire par le début9file = deque()10file.append(1); file.append(2); file.append(3)11print(file.popleft())      # 1, le premier entré

Les deux opérations sont en temps constant. Utiliser une liste comme file avec pop(0) serait un piège: pop(0) décale tous les éléments restants et transforme un traitement linéaire en traitement quadratique.

#Listes chaînées: la structure récursive en mémoireCopier le lien

La liste chaînée est la traduction directe de la définition récursive [n] · L1. Un maillon porte une valeur et un lien vers le maillon suivant; le lien None joue le rôle de la liste vide.

1class Maillon:2    __slots__ = ('valeur', 'suivant')3    def __init__(self, valeur, suivant=None):4        self.valeur = valeur5        self.suivant = suivant6 7def taille(tete: Maillon | None) -> int:8    if tete is None:9        return 010    return 1 + taille(tete.suivant)11 12def insere_tete(tete: Maillon | None, valeur) -> Maillon:13    return Maillon(valeur, tete)          # Θ(1) : deux pointeurs suffisent14 

Insérer en tête ne coûte que la création d'un maillon, alors que l'insertion en tête d'une liste Python décale tout. En revanche, atteindre le dernier élément demande de traverser toute la chaîne: la liste chaînée paie en accès ce qu'elle économise en modification.

#Pièges fréquentsCopier le lien

#Modifier pendant l'itérationCopier le lien

1nombres = [1, 2, 3, 4]2# Mauvais: la suppression décale les indices, des éléments sont sautés3for x in nombres[:]:        # copie explicite: sûr4    if x % 2 == 0:5        nombres.remove(x)6print(nombres)   # [1, 3]7 8# Meilleur: compréhension, sans mutation9pairs_gardes = [x for x in [1, 2, 3, 4] if x % 2 == 1]10print(pairs_gardes)   # [1, 3]

#Clé absenteCopier le lien

d['inconnue'] lève KeyError: utilisez .get(cle) ou testez if cle in d: quand l'absence est un cas normal.

#PlaygroundCopier le lien

#ExercicesCopier le lien

1. Tri par sélection en place. Implémentez le tri par sélection (à chaque tour, chercher le minimum du reste et l'échanger avec la position courante). Vérifiez que [5, 2, 4, 1, 3] devient [1, 2, 3, 4, 5].
2. Index inversé. Construisez un dictionnaire associant chaque mot d'un texte à la liste de ses positions. Pour 'le chat le chien', attendez {'le': [0, 2], 'chat': [1], 'chien': [3]}.
3. Déduplication ordonnée. Supprimez les doublons d'une liste en conservant l'ordre de première apparition. Pour [3, 1, 3, 2, 1], attendez [3, 1, 2].
4. File de priorité avec heapq. Implémentez une file où pop() retire l'élément de priorité la plus haute en premier.
5. File avec deux piles. Implémentez une file FIFO en n'utilisant que deux piles (listes avec append/pop). Analysez le coût amorti d'une suite de n opérations.
6. Liste chaînée. À partir de la classe Maillon, écrivez renverse(tete) qui retourne la liste chaînée dans l'ordre inverse, en temps linéaire et sans allouer de nouvelle liste.
7. Tri par comptage. Implémentez le tri par comptage pour des entiers dans [0, k] et vérifiez qu'il est stable sur une entrée contenant des doublons.

#CorrectionsCopier le lien

1def tri_selection(xs: list[int]) -> None:2    for i in range(len(xs)):3        mini = i4        for j in range(i + 1, len(xs)):5            if xs[j] < xs[mini]:6                mini = j7        xs[i], xs[mini] = xs[mini], xs[i]8 9xs = [5, 2, 4, 1, 3]10tri_selection(xs)11print(xs)   # [1, 2, 3, 4, 5]

1def index_inverse(texte: str) -> dict[str, list[int]]:2    index = {}3    for pos, mot in enumerate(texte.split()):4        index.setdefault(mot, []).append(pos)5    return index6 7print(index_inverse('le chat le chien'))8# {'le': [0, 2], 'chat': [1], 'chien': [3]}

1def sans_doublons(xs: list) -> list:2    vus = set()3    resultat = []4    for x in xs:5        if x not in vus:6            vus.add(x)7            resultat.append(x)8    return resultat9 10print(sans_doublons([3, 1, 3, 2, 1]))   # [3, 1, 2]

1import heapq2 3class FilePriorite:4    def __init__(self):5        self._tas = []6        self._compteur = 07 8    def push(self, item, priorite: int) -> None:9        heapq.heappush(self._tas, (-priorite, self._compteur, item))10        self._compteur += 111 12    def pop(self):13        return heapq.heappop(self._tas)[2]14 

1class FileDeuxPiles:2    def __init__(self):3        self._entree = []      # pile où l'on empile les nouveaux éléments4        self._sortie = []      # pile d'où l'on dépile5 6    def enfile(self, x) -> None:7        self._entree.append(x)                 # Θ(1)8 9    def defile(self):10        if not self._sortie:                   # transférer seulement si vide11            while self._entree:12                self._sortie.append(self._entree.pop())13        return self._sortie.pop()14 

1def renverse(tete):2    """Renverse la liste chaînée en Θ(n), sans allocation supplémentaire."""3    precedent = None4    courant = tete5    while courant is not None:6        suivant = courant.suivant     # mémoriser avant d'écraser le lien7        courant.suivant = precedent   # inverser le pointeur8        precedent = courant9        courant = suivant10    return precedent                  # l'ancienne queue est devenue la tête11 12# 1 -> 2 -> 3 devient 3 -> 2 -> 113chaine = None14for x in [3, 2, 1]:

1def tri_comptage(a: list[int], k: int) -> list[int]:2    c = [0] * (k + 1)3    for x in a:4        c[x] += 15    for i in range(1, k + 1):6        c[i] += c[i - 1]7    b = [0] * len(a)8    for j in range(len(a) - 1, -1, -1):9        c[a[j]] -= 110        b[c[a[j]]] = a[j]11    return b12 13a = [4, 1, 3, 4, 0, 1, 4]14print(tri_comptage(a, 4))   # [0, 1, 1, 3, 4, 4, 4]

#QuizCopier le lien