Les structures de données

Un programme, ça manipule des données : une liste de clients, un panier, un score. Une structure de données, c'est une façon d'organiser ces données en mémoire pour pouvoir les utiliser efficacement. Choisir la bonne, c'est déjà la moitié du travail : la même information rangée différemment se manipule plus ou moins facilement.

On va voir les quelques structures qu'on utilise tout le temps.

# Le tableau (array)

Une suite ordonnée d'éléments rangés côte à côte, chacun accessible par sa position (l'index, qui commence à 0).

["pomme", "poire", "cerise"]
    0        1         2

["pomme", "poire", "cerise"]

    0        1         2

• Accès direct et instantané par index : fruits[1] donne « poire ».
• Historiquement, sa taille est fixe (choisie à la création).

C'est la brique de base : beaucoup d'autres structures sont construites dessus.

# La liste (list)

Comme un tableau, mais dynamique : elle grandit et rétrécit toute seule quand on ajoute ou retire des éléments. C'est la structure du quotidien.

liste = [1, 2, 3]
liste.ajouter(4)   donne [1, 2, 3, 4]

liste = [1, 2, 3]

liste.ajouter(4)   donne [1, 2, 3, 4]

Dans beaucoup de langages, la « liste » est un tableau dynamique (list en Python, Array en JavaScript). C# distingue le tableau fixe int[] de la liste List<T>.

# Le dictionnaire (map / table de hachage)

Au lieu d'accéder par position, on accède par clé. Exactement comme un vrai dictionnaire : tu cherches un mot (la clé) pour obtenir sa définition (la valeur).

ages = {
  "Baptiste": 22,
  "Stefano": 30
}
ages["Baptiste"]   donne 22

ages = {

  "Baptiste": 22,

  "Stefano": 30

}

ages["Baptiste"]   donne 22

• Recherche très rapide par clé, même sur des millions d'entrées (c'est le rôle de la table de hachage derrière).
• Les clés sont uniques. L'ordre n'est pas sa raison d'être (même si beaucoup de langages conservent l'ordre d'insertion).

Idéal dès que tu veux retrouver une valeur à partir d'un identifiant.

# L'ensemble (set)

Une collection d'éléments uniques, sans doublon. On ne s'en sert pas pour ranger, mais pour répondre vite à une question : « est-ce que X est là-dedans ? ».

vus = {"a", "b"}
vus.contient("a")   donne vrai
vus.ajouter("a")    ignoré (déjà présent)

vus = {"a", "b"}

vus.contient("a")   donne vrai

vus.ajouter("a")    ignoré (déjà présent)

Parfait pour dédoublonner une liste ou tester une appartenance.

# Deux classiques : pile et file

Deux structures définies par leur ordre de sortie :

• Pile (stack) : dernier entré, premier sorti (LIFO). Comme une pile d'assiettes. On la retrouve dans le « annuler » (Ctrl+Z) ou la pile des appels de fonctions.
• File (queue) : premier entré, premier sorti (FIFO). Comme une file d'attente. Pour traiter des tâches dans l'ordre d'arrivée.

# Comment choisir ?

La structure dépend de ce que tu veux faire :

Et le même concept change de nom selon le langage :

Côté JavaScript, tableaux et objets sont détaillés dans tableaux & objets. Il existe bien d'autres structures (arbres, graphes, files de priorité), mais avec ces quelques-unes tu couvres déjà l'immense majorité des besoins du quotidien.

# À retenir

• Une structure de données = une façon d'organiser les données pour les manipuler efficacement.
• Tableau / liste : ordonnés, accès par position (la liste est un tableau dynamique).
• Dictionnaire : accès par clé (identifiant vers valeur), recherche très rapide.
• Ensemble : éléments uniques, idéal pour tester l'appartenance.
• Pile (LIFO) et file (FIFO) : spécialisées par l'ordre de sortie.
• Le bon choix dépend toujours de ce que tu veux en faire.