Structures de Données Linéaires

Pour organiser les données, il faut des structures adaptées. En Terminale, trois structures abstraites fondamentales sont étudiées : les Listes, les Piles et les Files.

1. Les Listes Chaînées (Linked Lists)

Contrairement aux tableaux (tableaux dynamiques de Python list) où les éléments sont contigus en mémoire, une liste chaînée est composée de maillons. Chaque maillon contient :

Une valeur (la donnée).
Une référence (lien) vers le maillon suivant.

Structure

[Tête | •] -> [Maillon 2 | •] -> [Maillon 3 | None]

Avantage : Insertion/Suppression en tête très rapide (O(1)).
Inconvénient : Accès au i-ème élément lent (O(n), il faut tout parcourir).

Implémentation

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

# Création manuelle de la liste 1 -> 2 -> 3
m3 = Maillon(3)
m2 = Maillon(2, m3)
tete = Maillon(1, m2)

2. Les Piles (Stacks)

Le principe est LIFO (Last In, First Out) : Dernier Arrivé, Premier Sorti. C'est comme une pile d'assiettes. On ne peut ajouter ou retirer que sur le dessus.

Interface (Opérations)

empiler(e) (push) : Ajoute un élément au sommet.
depiler() (pop) : Retire et renvoie l'élément du sommet.
est_vide() : Renvoie Vrai si la pile est vide.

Utilisations

Gestion des appels de fonctions (récursivité).
Fonction "Annuler" (Ctrl+Z) des éditeurs de texte.
Vérification de parenthésage : (( )).

# Implémentation simple avec une liste Python
pile = []
pile.append(1) # Empiler
pile.append(2)
sommet = pile.pop() # Dépiler (renvoie 2)

3. Les Files (Queues)

Le principe est FIFO (First In, First Out) : Premier Arrivé, Premier Sorti. C'est comme une file d'attente à la cantine. On ajoute à la fin (queue), on retire au début (tête).

Interface (Opérations)

enfiler(e) (enqueue) : Ajoute un élément à la queue.
defiler() (dequeue) : Retire et renvoie l'élément de tête.
est_vide() : Renvoie Vrai si la file est vide.

Utilisations

File d'attente d'impression.
Tampon (buffer) de clavier ou de réseau.
Parcours en largeur (BFS) d'un graphe.

Choisir un exercice

Cliquer sur un exercice de la liste pour afficher son sujet.