1.6 KiB
1.6 KiB
Structures de données linéaires
Un tableau Python permet d'accéder instantanément à n'importe quel élément par son indice. Mais certains problèmes demandent des structures plus souples : ajouter ou supprimer des éléments sans déplacer tout le reste, ou imposer un ordre d'accès strict. C'est l'objet de ce chapitre.
Programme
Les trois structures au programme
| Structure | Accès | Insertion | Suppression | Usage typique |
|---|---|---|---|---|
| Liste chaînée | Séquentiel | En tête : O(1) | En tête : O(1) | Structure de base, implémente pile et file |
| Pile (stack) | Dernier entré (LIFO) | En tête : O(1) | En tête : O(1) | Appels de fonctions, annulation (Ctrl+Z) |
| File (queue) | Premier entré (FIFO) | En queue : O(1) | En tête : O(1) | File d'attente, BFS, impression |
Ressources
| Fichier | Description |
|---|---|
| Listes chaînées | La brique de base : maillon, insertion, suppression, parcours |
| Piles et Files | Deux structures aux contraintes d'accès strictes |
Auteur : Florian Mathieu
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.