Structures de données

Listes, piles, files, dictionnaires, arbres, graphes — interfaces et implémentations.

Structures linéaires

Pile (Stack) — LIFO: Last In First Out : le dernier élément ajouté est le premier sorti. Opérations : push (empiler), pop (dépiler), peek (consulter le sommet). Applications : appels de fonctions (pile d'exécution), historique de navigation, validation des parenthèses. Implémentable avec un tableau ou une liste chaînée.
File (Queue) — FIFO: First In First Out : le premier arrivé est le premier sorti. Opérations : enqueue (enfiler), dequeue (défiler). Applications : file d'attente de processus, tampons réseau (buffers), impression de documents. La file de priorité (priority queue) ordonne selon une priorité, non l'ordre d'arrivée.
Dictionnaire (table de hachage): Structure associant des clés uniques à des valeurs. La fonction de hachage transforme la clé en indice de tableau. Accès, insertion, suppression en O(1) en moyenne. Collisions gérées par chaînage ou sondage. En Python : dict{}. Utilisé en bases de données, caches, déduplication.

Arbre binaire: Structure hiérarchique où chaque nœud possède au plus deux enfants (gauche et droit). Vocabulaire : racine (nœud initial), feuilles (sans enfants), hauteur (longueur du plus long chemin). Arbre binaire de recherche (ABR) : gauche < nœud < droite, recherche en O(log n) si équilibré.
Graphe orienté vs non orienté: Graphe non orienté : arêtes bidirectionnelles (réseau routier sans sens). Graphe orienté (digraphe) : arcs avec direction (Twitter : suivre ≠ être suivi). Graphe pondéré : poids sur les arêtes (distances, coûts). Représentation : matrice d'adjacence (dense) ou liste d'adjacence (creux).

Séparation interface/implémentation: L'interface définit ce que la structure fait (opérations disponibles et leur comportement attendu). L'implémentation choisit comment le faire techniquement (tableau, liste chaînée, arbre). L'encapsulation permet de changer l'implémentation sans modifier le code utilisateur. Principe fondamental du génie logiciel.
Complexités à connaître: Tableau : accès O(1), insertion/suppression O(n). Liste chaînée : accès O(n), insertion/suppression O(1) si position connue. Dictionnaire (hachage) : accès/insertion O(1) moyen. ABR équilibré : recherche/insertion O(log n). Ces complexités guident le choix de la structure adaptée au problème.

Flashcards, mode examen et suivi de progression — gratuit pour commencer.