A l'origine de chaque logiciel se trouvent deux entités : les données et les algorithmes. Les structures de données permettent de stocker et de récupérer ces données. Elles représentent la connaissance à organiser en mémoire. Peu importe le problème que nous devons résoudre, d'une manière ou d'une autre, nous devrons manipuler des données : l'apprentissage des structures de données est donc essentiel !

Nous devons utiliser des informations stockées, une mémoire pour vivre. Les structures de données qui existent dans les langages de programmation sont assez similaires à celles que nous utilisons dans le monde réel.

Imaginons devoir trouver un livre spécifique dans une bibliothèque non organisée : cela pourrait prendre un temps interminable ! Tout comme les bibliothèques organisent leurs livres, nous devons organiser nos données afin que les opérations puissent être effectuées efficacement. Choisir la mauvaise structure de données peut entraîner un code lent ou sans réponse et gâcher notre programme !

Comprendre les différences entre les structures de données de base
Sélectionner correctement notre structure de données pour répondre à nos besoins
Créer nos propres structures de données

Dans ce cours, nous examinerons les structures de données utilisées quotidiennement. Nous discuterons des compromis liés au choix de chacune d'elles ainsi que leurs algorithmes de parcours, de récupération et de mise à jour.

Et ensuite ?

Les tableaux et les listes chaînées sont les deux structures de données fondamentales du monde de la programmation. Après les avoir comprises, nous pourrons commencer à jouer avec des algorithmes tels que la recherche ou encore les tris. Nous pourrons aussi voir des structures de données plus avancées telles que : piles, files d'attente, arbres binaires ou tables de hachage pour ensuite étudier des algorithmes tels que les générateurs de labyrinthes.

Cette première fiche donne un très bon aperçu des principales structures de données et de la complexité de leurs opérations communes (source: bigocheatsheet).

L'organigramme ci-dessous est un guide pour choisir la bonne structure de donnée en fonction du contexte du problème (par Mikael Persson depuis l'originale de David Moore).

Note: Il est particulièrement désigné pour les conteneurs standard du C++ mais reste valable pour tous les autres langages de programmation. En effet, il faut garder à l’esprit qu’une structure de données (abstraite) est un concept et non seulement une implémentation.

• Wikipedia