Type abstrait de donnée

Un type de données abstrait est la description d’un ensemble organisé d’objets et des opérations de manipulation sur cet ensemble (les primitives). Ces opérations comprennent les moyens d’accéder aux éléments de l’ensemble, et aussi, lorsque l’objet est dynamique, les possibilités de le modifier.
L’ensemble de ces opérations est appelé interface. il est généralement constitué des 4 opérations élémentaires suivantes:

  • Créer une donnée.
  • Lire une donnée.
  • Modifier une donnée.
  • Supprimer une donnée.

Avec ces définitions, une structure de données est la réalisation, l’implémentation explicite d’un type de données.

Décrire un type abstrait de données, le spécifier, c’est décrire les opérations possibles et licites, et leur effet.
Décrire une structure de données, c’est expliciter comment les objets sont représentés et comment les opérations sont implémentées. Pour l’évaluation d’algorithmes, il importe  de connaître leur coût en temps et en place.
(D. Beauquier, J. Berstel, Ph. Chrétienne, Eléments d’algorithmique)

Remarque: Nous n’évoquerons que la complexité en temps des primitives.

Structures linéaires

Listes, piles, et files sont des types linéaires.
Les piles et files sont des types de données simples mais présents partout:

Structures hiérarchiques