Cours de Structures de données – Licence 2

Une liste chaînée est une structure dynamique formée de cellules reliées par des pointeurs : chaque cellule contient une valeur et la référence vers la suivante. Ce chapitre compare les listes aux tableaux, décrit les opérations de base (parcours, insertion en tête et en queue, recherche, suppression) avec leur complexité, présente les listes doublement chaînées et circulaires et traite des…

5 chapitres · exercices corrigés et quiz dans l'application

Programme : les chapitres

Chapitre à lire gratuitement : Listes chaînées

1. Structures de données et complexité

Une structure de données organise des données en mémoire pour que certaines opérations soient efficaces. On mesure l'efficacité par la complexité asymptotique, notée O(f(n)) : une opération en O(1) coûte un temps constant, en O(n) un temps proportionnel à la taille n, en O(n²) un temps quadratique.

Tableau contre liste : un tableau offre un accès direct à l'élément d'indice i en O(1) mais l'insertion au milieu coûte O(n) (décalages) et sa taille est fixée. Une liste chaînée permet l'insertion en tête en O(1) mais l'accès au i-ème élément coûte O(i).

2. La liste simplement chaînée

Définition : une cellule contient une valeur et un lien suivant vers la cellule suivante (ou None / nil pour la dernière). Une liste est repérée par sa tête, le lien vers la première cellule. La liste vide est tête = None.

En Python :

class Cellule:

def __init__(self, valeur, suivant=None):

self.valeur = valeur

self.suivant = suivant

Pseudo-code : Cellule = enregistrement (valeur, suivant).

3. Parcours, recherche, longueur

Parcours : c ← tête ; tant que c ≠ nil : traiter c.valeur ; c ← c.suivant. Le temps est O(n).

def longueur(tete):

n, c = 0, tete

while c is not None:

n += 1

c = c.suivant

return n

La recherche d'une valeur est une variante : on s'arrête dès que c.valeur égale la valeur cherchée. Dans le pire cas, O(n).

4. Insertion et suppression

Insertion en tête : créer une cellule dont suivant pointe sur l'ancienne tête, puis changer la tête : O(1).

tete = Cellule(v, tete)

Insertion en queue : il faut parcourir jusqu'à la dernière cellule : O(n), sauf si l'on mémorise aussi un pointeur de queue (alors O(1)).

Suppression de la première cellule contenant v : on garde un pointeur sur la cellule précédente prec ; si prec est None, on change la tête, sinon prec.suivant = c.suivant. Coût O(n) pour trouver, O(1) pour détacher.

Attention : toujours traiter à part le cas de la liste vide et celui de la tête. Perdre la référence à la tête, ou modifier c.suivant avant d'avoir sauvegardé l'ancien suivant, fait perdre le reste de la liste.

5. Variantes

• Liste doublement chaînée : chaque cellule a aussi un lien précédent ; on peut supprimer une cellule connue en O(1) et parcourir dans les deux sens, au prix d'un lien de plus par cellule.
• Liste circulaire : la dernière cellule pointe vers la première ; utile pour les structures cycliques (tourniquet d'ordonnancement).
• Sentinelle : une cellule factice en tête évite les cas particuliers de la tête.

6. Algorithmes classiques

Inversion : on parcourt en retournant les liens, avec trois pointeurs (prec, c, suiv) :

def inverser(tete):

prec, c = None, tete

while c is not None:

suiv = c.suivant

c.suivant = prec

prec, c = c, suiv

return prec

Complexité O(n) en temps, O(1) en mémoire supplémentaire.

Fusion de deux listes triées : on compare les têtes et on avance dans la liste dont la tête est la plus petite (récursivement ou avec une sentinelle). Complexité O(n + m).

Détection de cycle (Floyd) : deux pointeurs, la tortue avance de 1 et le lièvre de 2. S'il y a un cycle, ils se rencontrent ; sinon le lièvre atteint None. Temps O(n), mémoire O(1).

7. Méthode pour les examens

• Dessiner la liste avant et après chaque opération (cellules et flèches) : l'ordre des affectations est l'erreur la plus fréquente.
• Dire explicitement la complexité de chaque opération.
• Tester l'algorithme sur trois cas : liste vide, liste à un élément, cas général.
• Penser à la sentinelle pour simplifier le code.