Listes Chaînées
Contrairement aux tableaux où les éléments sont contigus en mémoire, les listes chaînées utilisent des pointeurs pour lier des cellules dispersées. Cette structure offre des insertions et suppressions en O(1) !
Objectifs du cours
- Comprendre le concept de liste chaînée et ses variantes
- Implémenter une liste simplement chaînée en Python
- Maîtriser les opérations d'insertion et de suppression
- Comparer listes chaînées et tableaux dynamiques
- Implémenter une liste doublement chaînée
Erreurs courantes à éviter
- Perdre la référence à la tête de liste
- Oublier de mettre à jour les pointeurs lors d'insertion/suppression
- Ne pas gérer les cas limites (liste vide, un seul élément)
- Créer des cycles involontairement
Une **liste chaînée** est une structure de données où chaque élément (appelé **nœud** ou **cellule**) contient : 1. Une **valeur** (la donnée stockée) 2. Une **référence** (pointeur) vers l'élément suivant
**Visualisation** : ``` ┌───────────┐ ┌───────────┐ ┌───────────┐ │ valeur: 5 │───>│ valeur: 3 │───>│ valeur: 8 │───> None └───────────┘ └───────────┘ └───────────┘ tête queue ```
**Terminologie** : - **Tête (head)** : premier nœud de la liste - **Queue (tail)** : dernier nœud (pointe vers None) - **Nœud (node)** : élément contenant valeur + référence - **Suivant (next)** : pointeur vers le prochain nœud
**Comparaison avec les tableaux** : | Opération | Tableau | Liste chaînée | |-----------|---------|---------------| | Accès par index | O(1) | O(n) | | Insertion début | O(n) | O(1) | | Insertion fin | O(1)* | O(n) ou O(1)** | | Suppression début | O(n) | O(1) |
*amorti **si on garde une référence à la queue
# Un nœud est une simple classe avec deux attributs
class Noeud:
def __init__(self, valeur):
self.valeur = valeur # La donnée stockée
self.suivant = None # Référence vers le prochain nœud
# Créer une liste manuellement : 5 → 3 → 8
n1 = Noeud(5)
n2 = Noeud(3)
n3 = Noeud(8)
n1.suivant = n2 # 5 pointe vers 3
n2.suivant = n3 # 3 pointe vers 8
# n3.suivant reste None (fin de liste)
# Parcourir la liste
courant = n1
while courant is not None:
print(courant.valeur, end=" → ")
courant = courant.suivant
print("None")
# Sortie : 5 → 3 → 8 → NoneQuiz de validation
1. Quel est l'avantage principal des listes chaînées sur les tableaux ?
2. Que contient un nœud d'une liste simplement chaînée ?
3. Quelle est la complexité pour accéder au n-ième élément d'une liste chaînée ?
4. Que faut-il faire attention lors de la suppression d'un nœud ?
5. Quelle structure Python est implémentée comme une liste doublement chaînée ?
