Une structure de données en informatique est un moyen de stocker des données
dans un ordinateur afin qu'elles puissent être utilisées efficacement. C'est une organisation
de concepts mathématiques et logiques de données. Souvent, une
structure de données soigneusement choisie
permettra d'utiliser l'
algorithme
le plus
efficace . Le choix de la structure de données commence souvent par le
choix d'un type de données abstrait. Une structure de données bien conçue permet d'effectuer
une variété d'opérations critiques, en utilisant le moins de
ressources possible, à la fois en temps d'exécution et en espace mémoire. Les
structures de données
sont implémentées par un
langage de programmation en tant que types de données et les
référenceset les opérations qu'ils fournissent.
Différents types de structures de données conviennent à différents types d'
applications, et certaines sont hautement spécialisées pour certaines tâches. Par
exemple,
les arbres B sont particulièrement bien adaptés à la mise en œuvre de bases de données, tandis que les réseaux de machines reposent sur des tables de routage pour fonctionner.
Dans la conception de nombreux types de programmes informatiques, le choix des
structures de données
est une considération de conception primordiale. L'expérience dans la construction de
grands systèmes a montré que la difficulté de mise en œuvre et la
qualité et la performance du résultat final dépendent fortement du choix de
la meilleure structure de données. Une fois les structures de données choisies, le
les algorithmes à utiliser deviennent souvent relativement évidents. Parfois, les choses
fonctionnent dans la direction opposée - les structures de données sont choisies parce que
certaines tâches clés ont des algorithmes qui fonctionnent le mieux avec des
structures de données particulières
. Dans les deux cas, le choix des structures de données appropriées
est crucial.
Cette idée a donné naissance à de nombreuses méthodes de conception et
langages de programmation formalisés
dans lesquels les structures de données, plutôt que les algorithmes,
sont le facteur d'organisation clé. La plupart des langages comportent une sorte de
système de
modules, permettant aux structures de données d'être réutilisées en toute sécurité dans
différentes applications en cachant leurs détails de mise en œuvre vérifiés
derrière des interfaces contrôlées.
Les langages de programmation orientés objet tels que C++ et
Java en particulier utilisent des
classes à cette fin.
Étant donné que les structures de données sont si cruciales, nombre d'entre elles sont incluses dans les bibliothèques standard des langages de programmation modernes et des
API , telles que les
conteneurs C++
, le
Java Collections Framework et le Microsoft
.NET Framework .
Les blocs de construction fondamentaux de la plupart des structures de données sont les tableaux, les
enregistrements ,
les unions discriminées et les
références .
Par exemple, la référence Nullable, une référence qui peut être Null, est
une combinaison de références et d'unions discriminées, et la
structure de données liée la plus simple
, la liste chaînée, est construite à partir d'enregistrements et de
références Nullable.
Les structures de données représentent des implémentations ou des
interfaces :
Une structure de données peut être considérée comme une interface entre deux fonctions ou
comme une implémentation de méthodes pour accéder à un stockage organisé
selon le type de données associé