Structures de Données en Python

📋 Plan du Cours

1. Listes en Python
2. Piles (LIFO)
3. Files (FIFO)
4. Dictionnaires Python
5. Interfaces structures de données
6. Implémentations listes chaînées
7. Opérations sur listes chaînées
8. Choix structure selon tâche
9. Analyse fréquentielle dictionnaires

📖 1. Listes en Python

🔑 Notions clés & Définitions

• Liste (collection linéaire) : Ensemble ordonné d’éléments accessibles par leur indice, pouvant être modifiée (ajout, suppression). En Python, c’est une structure dynamique native, représentée par une séquence de valeurs entre crochets, par exemple [1, 2, 3].
• Tableau dynamique : Structure de tableau dont la taille peut varier par recopie, permettant d’ajouter ou supprimer des éléments sans connaître la nombre initial. Selon D. Roche (date non précisée), il consiste à créer un nouveau tableau plus grand, copier les éléments, puis ajouter le nouvel élément.
• Liste chaînée : Ensemble de cellules (ou nœuds), chaque contenant une donnée et un pointeur vers la cellule suivante. Selon D. Roche (date non précisée), cette structure facilite l’insertion rapide, mais nécessite plus d’espace mémoire et un accès séquentiel.
• Accès par indice vs accès par pointeur : La liste en Python permet un accès direct à un élément via son indice (ex. L[n]), en temps constant. La liste chaînée nécessite un parcours séquentiel pour atteindre un n-ième élément, ce qui est plus lent.
• Opérations sur listes chaînées : Ajout,…