Les types abstraits sont définis par leur interface (comment on s’en sert) plutôt que par leur implémentation (comment ils fonctionnent). Ils permettent d’étudier des algorithmes indépendamment du langage utilisé.
I. Structures de données, types abstraits
Une structure de données est une manière de stocker, d’accéder à, et de manipuler des données (comme les types list ou dict de Python).
L’interface de la structure de données décrit de quelle manière on peut la manipuler, par exemple en utilisant append pour le type list ou get pour le type dict.
L’implémentation de la structure de données, au contraire, contient le code de ces méthodes (comment fait Python). Il n’est pas nécessaire de connaître l’implémentation pour manipuler la structure de données.
Un type abstrait décrit essentiellement une interface, indépendamment du langage de programmation, avec éventuellement des précisions sur la complexité en temps et en espace de ces opérations.
II. Listes
Une liste est composée de données et offre un moyen de passer à la donnée suivante. Les listes sont très souvent implémentées sous forme d’une chaîne de valeurs, chacune pointant vers la suivante (on parle alors de liste chaînée), comme sur la figure ci-contre.
Les opérations généralement disponibles sont :
savoir si la liste est vide (is_empty) ;
insérer un élément en tête de liste (insert) en temps constant ;
récupérer l’élément en tête de liste (head) en temps constant ;
récupérer la liste privée du premier élément (tail).
Il existe de multiples variantes de listes, mais le principe reste toujours plus ou moins identique. Cette structure est à la base de nombreuses autres.
À noterLes noms des structures de données Python sont parfois trompeurs : le type list s’apparente par exemple à un tableau dynamique, et non à une liste chaînée dont il est question ici.
III. Piles
Une pile (stack ou LIFO pour last in, first out) est une collection d’objets munie des opérations suivantes :
savoir si la pile est vide (is_empty) ;
empiler un nouvel élément au sommet de la pile (empiler, push) en temps constant ;
dépiler l’élément au sommet de la pile et le renvoyer (depiler, pop) en temps constant (parfois, il y a deux opérations : une pour renvoyer le sommet de la pile sans le supprimer, et une pour simplement le supprimer).
IV. Files
Une file (queue ou FIFO pour first in, first out) est une collection d’objets munie des opérations suivantes :
savoir si la file est vide (is_empty) ;
ajouter un élément dans la file (enfiler ou enqueue) en temps constant ;
retirer et renvoyer l’élément le plus ancien de la file (defiler ou dequeue).
V. Tableaux associatifs
Un tableau associatif est un type abstrait qui associe des valeurs à des clés et est muni des opérations suivantes :
ajout d’une nouvelle valeur associée à une nouvelle clé ;
modification de la valeur associée à une clé existante ;
suppression d’une clé et de la valeur associée ;
récupération de la valeur associée à une clé donnée.
Un tableau associatif pourrait par exemple associer les valeurs « couples prénom/nom » aux clés « numéro de sécurité sociale », la contrainte étant que chaque clé doit être unique dans le tableau associatif.