Listes et dictionnaires

Une liste abstraite est une structure linéaire : ses éléments ont un ordre. Son interface peut proposer la consultation d’une tête et d’une suite, ou un accès par position selon la représentation choisie. Une liste Python, de type list, est une séquence mutable à accès par indice. Pour une liste de longueur n, les indices positifs valides vont de 0 à n − 1. L’indice est une position, pas une valeur contenue. Deux cases différentes peuvent contenir la même valeur ; la position reste nécessaire pour les distinguer.

L’écriture valeurs[i] consulte la case d’indice i. L’affectation valeurs[i] = x remplace son contenu sans ajouter une case. La méthode append(x) ajoute une valeur à la fin. La méthode pop(i) retire et renvoie la valeur à une position ; sans argument, elle agit à la dernière position. La présence de x dans valeurs se teste avec x in valeurs : ce test cherche parmi les valeurs, pas parmi les indices. Sur une liste non triée, une recherche séquentielle peut devoir examiner toutes les cases avant de conclure à une absence.

Une structure linéaire peut aussi être réalisée par chaînage : chaque maillon contient une valeur et une référence vers la suite. Consulter le troisième élément demande alors de suivre les liens depuis le début. La même idée abstraite d’ordre peut donc conduire à des coûts différents. Le mot liste ne suffit pas à connaître une complexité : il faut préciser l’interface, la représentation et l’opération. Dans ce chapitre, les codes utilisant des crochets et append concernent les listes Python, pas toutes les structures linéaires possibles.

Un dictionnaire associe à chaque clé présente une valeur. La clé sert à retrouver cette valeur ; elle n’est pas un numéro de position imposé. Par exemple, les clés peuvent être des noms de capteurs et les valeurs leurs mesures. Deux clés distinctes peuvent être associées à la même valeur. En revanche, une clé ne porte qu’une valeur à un instant donné : une nouvelle affectation avec cette clé remplace l’ancienne association. Les clés doivent être hachables ; des chaînes ou des entiers conviennent, mais une liste mutable ne peut pas servir directement de clé.

L’expression mesures["A"] lit la valeur associée à la clé A. Si cette clé est absente, elle provoque une KeyError. On peut tester "A" in mesures ou utiliser mesures.get("A", valeur_par_defaut). Le test d’appartenance sur un dictionnaire cherche une clé. Pour chercher une valeur, on parcourt mesures.values(). La méthode items() permet de parcourir les couples clé-valeur. Les dictionnaires Python conservent l’ordre d’insertion pour l’itération ; cela ne transforme pas les clés en indices de séquence. Une clé entière 0 est une clé choisie, pas forcément la première association.

Pour compter des occurrences, une liste conserve les observations et un dictionnaire associe chaque valeur rencontrée à son effectif. Au début, aucun effectif n’est connu. À chaque observation, on lit l’effectif courant, ou zéro si la valeur est nouvelle, puis on ajoute un. L’invariant est simple : après k observations traitées, chaque effectif correspond au nombre d’occurrences dans ces k observations. Il permet de justifier le résultat final. Le dictionnaire ne mémorise pas chaque occurrence séparément : il regroupe l’information selon les clés.

Choisis ensuite la structure selon les questions fréquentes. Pour obtenir une mesure par position et conserver les répétitions, une liste est naturelle. Pour retrouver une valeur à partir d’un identifiant, un dictionnaire est souvent adapté. Une recherche par clé dans un dictionnaire est en général efficace en moyenne, mais cela ne rend pas instantanée la recherche d’une valeur quelconque dans ses valeurs. Il faut préciser ce que l’on cherche. L’accès par indice à une liste et la recherche d’une valeur dans cette liste sont également deux opérations différentes.

Le partage de références concerne aussi ces conteneurs. Après b = a, les deux noms désignent la même liste. Une copie superficielle avec a.copy() crée une nouvelle liste extérieure, mais des listes imbriquées peuvent rester partagées. Par exemple, si une case contient une liste de mesures, copier le dictionnaire extérieur ne recopie pas automatiquement toutes les mesures. Pour vérifier l’indépendance attendue, modifie un élément intérieur et observe les deux structures. La question du partage porte sur les objets atteints, pas seulement sur les noms des conteneurs.

Pendant la mise au point, donne des noms qui rendent le rôle visible : indice, cle, mesure, effectif. Un même nom utilisé successivement pour une position puis pour une valeur rend les traces difficiles à lire. N’efface pas un élément d’une liste pendant un parcours dont les indices supposent sa longueur initiale. Pour un filtrage simple, construire une nouvelle liste rend souvent le raisonnement plus clair. Le bon modèle permet de réduire les erreurs avant même d’optimiser le programme.

S’entraîner : ouvre l’espace Exercices du site.