Python possède dans la bibliothèque standard un grand nombre de structures de données, programmées de manière efficace. La compréhension des limites des structures de données proposées fait partie du bagage du programmeur averti.
I. Tableaux dynamiques et piles : list
1) Tableaux dynamiques
Le type list de Python ne s’apparente pas aux listes chaînées, car la suppression ou l’ajout ailleurs qu’en fin de liste nécessite de décaler les valeurs de fin de liste, et n’est donc pas réalisé en temps constant. D’autre part, l’accès à un élément quelconque est réalisé en temps constant, ce qui n’est pas le cas avec une liste chaînée. Le type list de Python correspond donc plutôt à un tableau dynamique.
À noter
Avec une list Python, l’ajout et la suppression ailleurs qu’en fin de liste ne sont pas réalisés en temps constant.
2) Piles
Le type list Python contient tout ce qu’il faut pour implémenter une pile. Le code est suffisamment simple pour ne pas nécessiter l’écriture d’une nouvelle classe (le push de la pile correspond à append).
II. Tableau associatif : dict
Le type dict de Python est une implémentation du type abstrait tableau associatif. L’implémentation correspond à une table de hachage, ce qui signifie que la valeur est stockée dans un tableau et que la position dans ce tableau dépend du résultat d’une fonction de hachage appliquée à la clé. En un temps indépendant du nombre de valeurs stockées dans le dictionnaire, Python peut retrouver la valeur associée à n’importe quelle clé : pour cela il calcule un indice à partir de la valeur de la clé (qui doit donc être hachable, c’est-à-dire récursivement non mutable) et récupère la valeur stockée à cet indice dans un tableau.
Une caractéristique essentielle des dictionnaires est que la récupération d’une valeur associée à une clé se fait en un temps constant, indépendant de la taille du dictionnaire. De même, savoir si une clé fait partie du dictionnaire prend un temps constant (alors que vérifier si un élément est dans une liste prend un temps proportionnel à la taille de la liste).
III. Ensemble : set
Un ensemble Python (set) est équivalent à un dictionnaire ne contenant que des clés. Par construction, chaque élément est donc unique. De plus, avec le type set on dispose déjà des opérations ensemblistes habituelles, implémentées de manière très efficace : union, intersection, différence…
IV. File : collections.deque
Nous avons présenté deux implémentations (dont une imparfaite) de la structure de file, qui ne peuvent pas être implémentées correctement avec une simple liste python, contrairement à la structure de pile (voir plus haut).
La bibliothèque standard possède toutefois un module nommé collections qui contient quelques structures de données supplémentaires, dont le type deque, qui est une implémentation de file :
À noter
Attention à ne pas confondre le type deque (double-ended queue) avec le verbe dequeue (défiler) !
Résultat :
Avec le type deque, les opérations d’ajout et de suppression dans la file sont toutes deux réalisées en temps constant.