Cours complet : Structures lineaires : listes, piles, files
Les structures de donnees linéaires sont des collections ordonnees d'éléments ou chaque élément possede au plus un predecesseur et un successeur. Elles constituent le socle de la programmation et de l'algorithmique, et leur maitrise est indispensable pour tout informaticien.
Les principales structures linéaires sont les listes chainees, les piles (LIFO - Last In, First Out) et les files (FIFO - First In, First Out). Chacune repond a des besoins specifiques en termes d'acces, d'insertion et de suppression des donnees. Leur choix depend du probleme a résoudre et des contraintes de complexite.
Comprendre ces structures, leurs implementations en Python et leurs complexites algorithmiques est essentiel pour choisir la structure adaptee a un probleme donne. Le concept de type abstrait de donnees (TAD) permet de raisonner sur les opérations independamment de l'implementation concrete, favorisant la modularite et la reutilisabilite du code.
Ce chapitre presente les listes chainees, les piles et les files, en detaillant pour chacune leur interface, leur implementation et leurs applications.
Prérequis
- Notions de base en Python (classes, listes, boucles)
- Concept de reference et de pointeur
- Notion de complexite algorithmique O(1), O(n)
1. Les listes chainees
Une liste chainee est une structure de donnees ou chaque élément (noeud) contient une valeur et une reference vers l'élément suivant. Contrairement aux tableaux, les éléments ne sont pas stockes de maniere contigue en memoire, ce qui permet des insertions et suppressions efficaces sans decalage d'éléments.
On distingue les listes simplement chainees (chaque noeud pointe vers le suivant) des listes doublement chainees (chaque noeud pointe vers le suivant et le précédent). La liste simplement chainee ne permet le parcours que dans un sens, tandis que la doublement chainee autorise un parcours bidirectionnel au prix d'un surcout memoire.
L'acces a un élément par son indice est en O(n) car il faut parcourir la liste depuis la tete. En revanche, l'insertion en tete est en O(1) puisqu'il suffit de creer un noeud et de le relier a l'ancienne tete. L'insertion en queue est en O(n) sauf si on maintient une reference vers le dernier élément, auquel cas elle passe en O(1).
En Python, les listes natives (list) sont implementees comme des tableaux dynamiques, pas comme des listes chainees. Pour implementer une liste chainee, on utilise une classe Noeud avec un attribut valeur et un attribut suivant. Cette distinction est fondamentale et constitue un piege frequent au BAC.
Méthode — Implementer une liste chainee en Python
- définir une classe Noeud avec attributs valeur et suivant (initialise a None)
- Creer la liste en chainant les noeuds : tete = Noeud(1, Noeud(2, Noeud(3)))
- Parcourir avec une boucle while : courant = tete, avancer avec courant = courant.suivant
- Inserer en tete : nouveau = Noeud(val, tete), puis tete = nouveau
- vérifier la fin de liste : courant is None (pas courant == None)
Exemple : On considere la liste chainee 3 -> 7 -> 2 -> 9. écrire une fonction Python qui retourne la somme des éléments de la liste.
- Identifier le cas de base : Si le noeud courant est None (liste vide ou fin de liste), la somme est 0.
- définir le cas recursif : La somme est la valeur du noeud courant plus la somme du reste de la liste.
- Implementer en Python : def somme(noeud): if noeud is None: return 0 return noeud.valeur + somme(noeud.suivant)
- Tracer l'execution : somme(3) = 3 + somme(7) = 3 + 7 + somme(2) = 3 + 7 + 2 + somme(9) = 3 + 7 + 2 + 9 + somme(None) = 21
⚠️ Attention : La list Python est un tableau dynamique, PAS une liste chainee. Ne pas les confondre au BAC. list[i] est O(1) pour un tableau, O(n) pour une liste chainee.
2. Les piles (LIFO)
Une pile est une structure de donnees linéaire suivant le principe LIFO (Last In, First Out) : le dernier élément ajoute est le premier retire. On peut la comparer a une pile d'assiettes ou seule l'assiette du dessus est accessible.
Les opérations fondamentales d'une pile sont : empiler (push) pour ajouter un élément au sommet, depiler (pop) pour retirer l'élément du sommet, consulter le sommet (peek ou top) sans le retirer, et tester si la pile est vide. Toutes ces opérations sont en O(1), ce qui rend la pile extremement efficace.
Une pile peut etre implementee avec un tableau dynamique (liste Python avec append et pop) ou une liste chainee (insertion et suppression en tete). Les deux implementations offrent des opérations en O(1).
Les piles sont utilisees dans de nombreux contextes fondamentaux : la gestion des appels de fonctions (pile d'execution du processeur), l'evaluation d'expressions arithmetiques en notation postfixee, la verification du parenthesage d'expressions, l'algorithme de parcours en profondeur (DFS) des graphes et arbres, et le mecanisme undo/redo des editeurs. La pile d'appels est un concept central pour comprendre la recursivite.
Méthode — vérifier le parenthesage d'une expression
- Creer une pile vide
- Parcourir chaque caractere de l'expression
- Si c'est une parenthese ouvrante '(' : empiler
- Si c'est une parenthese fermante ')' : vérifier que la pile n'est pas vide, puis depiler
- A la fin, la pile doit etre vide (autant d'ouvertures que de fermetures)
Exemple : On empile successivement les valeurs 5, 3, 8, 1 dans une pile. On depile deux fois. Quel est l'état de la pile et que valent les éléments depiles ?
- Empiler les valeurs : Empiler 5 : pile = [5] Empiler 3 : pile = [5, 3] Empiler 8 : pile = [5, 3, 8] Empiler 1 : pile = [5, 3, 8, 1] (sommet = 1)
- Premier depilage : On retire le sommet (LIFO). élément depile = 1. Pile = [5, 3, 8]
- Deuxieme depilage : On retire le sommet. élément depile = 8. Pile = [5, 3]
⚠️ Attention : Toujours vérifier est_vide() avant de depiler. Depiler une pile vide provoque une erreur. C'est une erreur classique dans les exercices du BAC.
3. Les files (FIFO)
Une file est une structure de donnees linéaire suivant le principe FIFO (First In, First Out) : le premier élément ajoute est le premier retire. On peut la comparer a une file d'attente dans un magasin : le premier arrive est le premier servi.
Les opérations fondamentales sont : enfiler (enqueue) pour ajouter un élément a l'arriere, defiler (dequeue) pour retirer l'élément a l'avant, consulter l'avant (front) sans le retirer, et tester si la file est vide.
Une implementation naive avec une liste Python utilisant pop(0) pour defiler est en O(n) car il faut decaler tous les éléments restants vers la gauche. On prefere utiliser collections.deque qui offre des opérations en O(1) aux deux extremites grace a une implementation en tableau circulaire doublement chaine.
Les files sont utilisees pour le parcours en largeur (BFS) dans les graphes et les arbres, la gestion des processus dans un systeme d'exploitation (ordonnancement FIFO), les tampons (buffers) en reseau pour gerer les donnees en transit, et les files d'impression. La file est la structure duale de la pile : la ou la pile traite le dernier arrive en priorite, la file traite le premier arrive en priorite.
Méthode — Implementer un parcours en largeur (BFS) avec une file
- Creer une file avec deque et enfiler le sommet de depart
- Creer un ensemble de sommets visites contenant le depart
- Tant que la file n'est pas vide : defiler un sommet
- Pour chaque voisin non visite : le marquer visite et l'enfiler
- Le parcours visite les sommets par distance croissante au depart
Exemple : On enfile successivement A, B, C, D dans une file. On defile deux fois, puis on enfile E. Quel est l'état de la file ?
- Enfiler les éléments : Enfiler A : file = [A] Enfiler B : file = [A, B] Enfiler C : file = [A, B, C] Enfiler D : file = [A, B, C, D] (avant = A)
- Defiler deux fois : Premier defilement : A sort (FIFO). File = [B, C, D] Deuxieme defilement : B sort. File = [C, D]
- Enfiler E : E est ajoute a l'arriere. File = [C, D, E]
⚠️ Attention : Ne JAMAIS utiliser list.pop(0) pour implementer une file : c'est O(n). Toujours utiliser collections.deque avec popleft() pour obtenir O(1).
4. Comparaison et choix de la structure
Le choix entre liste chainee, pile et file depend du probleme a résoudre. La pile est adaptee quand on doit traiter le dernier élément ajoute en priorite (LIFO) : parcours en profondeur, verification de parenthesage, pile d'appels. La file convient quand on traite les éléments dans leur ordre d'arrivee (FIFO) : parcours en largeur, ordonnancement, buffers.
En termes de complexite, les piles et files offrent des opérations principales en O(1). Les listes chainees offrent une insertion en tete en O(1) mais un acces par indice en O(n). Les tableaux (listes Python) offrent un acces par indice en O(1) mais une insertion en debut en O(n) a cause du decalage des éléments.
Les listes doublement chainees combinent les avantages : insertion et suppression en O(1) en tete et en queue, mais au prix d'une consommation memoire supplementaire (deux references par noeud au lieu d'une). C'est la structure sous-jacente de collections.deque en Python.
Il est essentiel de maitriser l'interface (les opérations abstraites) independamment de l'implementation. Le concept de type abstrait de donnees (TAD) separe la specification des opérations de leur realisation concrete. Ainsi, on peut définir le TAD Pile par ses opérations (empiler, depiler, est_vide, sommet) sans preciser si l'implementation utilise un tableau ou une liste chainee.
Méthode — Choisir la bonne structure de donnees
- Identifier le mode d'acces : sequentiel, par indice, dernier/premier ajoute
- Si besoin de LIFO (dernier ajoute = premier traite) : choisir une pile
- Si besoin de FIFO (premier ajoute = premier traite) : choisir une file
- Si besoin d'acces par indice en O(1) : choisir un tableau
- Si insertions/suppressions frequentes en tete : choisir une liste chainee
- définir le TAD avec les opérations necessaires avant de choisir l'implementation
Exemple : On doit gerer une liste d'attente ou le premier inscrit est le premier servi, avec possibilite d'ajouter des personnes et de retirer la prochaine personne. Quelle structure choisir et pourquoi ?
- Identifier le mode d'acces : Premier inscrit = premier servi : c'est le principe FIFO.
- Choisir la structure : Le principe FIFO correspond a une file. Les opérations necessaires sont enfiler (ajouter une personne) et defiler (retirer la prochaine personne).
- Choisir l'implementation : En Python, utiliser collections.deque pour des opérations en O(1). Pas une list avec pop(0) qui serait en O(n).
⚠️ Attention : Ne pas confondre le TAD (interface abstraite) et l'implementation (code concret). Un TAD Pile peut etre implemente avec un tableau OU une liste chainee, les deux sont corrects.
Conclusion
Les structures linéaires (listes chainees, piles, files) sont fondamentales en informatique. Leur maitrise implique de comprendre leurs principes (LIFO, FIFO), leurs complexites algorithmiques et leurs cas d'utilisation. Le concept de type abstrait de donnees permet de raisonner sur les opérations independamment de l'implementation. Au BAC, il est essentiel de savoir choisir et justifier la structure adaptee a chaque probleme.
Mots-clés