Tableaux, listes, piles et files
Cette fiche récapitule les structures de données linéaires de base vues en Licence 1 : tableaux, listes chaînées, piles et files.
1
Tableaux
Comparaison
Tableau statique
- Taille fixée à la création.
- Mémoire contiguë.
- Accès direct par indice.
Tableau dynamique
- Taille ajustable.
- Réallocation si capacité dépassée.
- Ajout amorti souvent efficace.
Piège
Taille logique et capacité mémoire ne sont pas la même chose. Un tableau dynamique peut recopier ses éléments lors d'un redimensionnement.
2
Listes chaînées
Principe
Une liste chaînée simple est une suite de cellules reliées par des pointeurs.
- Chaque cellule contient une valeur et un pointeur
suivant. - Le parcours commence à la tête de liste.
Parcours et insertion
- 1
Partir de la tête de liste.
- 2
Suivre les pointeurs un à un.
Suppression
- Chercher l'élément à supprimer.
- Retrouver son prédécesseur.
3
Pile et file
Pile
Principe
- Structure LIFO.
- Dernier entré, premier sorti.
- Une seule extrémité active.
Opérations
pushempile au sommet.popdépile au sommet.- Le sommet est la seule zone accessible.
File
Principe
- Structure FIFO.
- Premier entré, premier sorti.
- Deux extrémités distinctes.
Opérations
enfilerajoute en queue.défilerretire en tête.- L'ordre d'arrivée est respecté.
4
Implémentations
Séquentielle et chaînée
| Représentation | Idée | Atout | Limite |
|---|---|---|---|
| Séquentielle | Mémoire contiguë. | Accès indexé rapide. | Insertions et suppressions coûteuses. |
| Chaînée | Cellules et pointeurs. | Modifications locales faciles. | Accès direct impossible. |
Coûts à retenir
- L'accès indexé favorise le tableau.
- La recherche demande souvent un parcours linéaire.
Résumé
- Le tableau privilégie l'accès direct.
- La liste chaînée privilégie la flexibilité.
- La pile impose
LIFOet la file imposeFIFO. - Le bon choix dépend des opérations dominantes et de leur coût.