Listes chaînées : Implémentation et Opérations de Base

1. Pourquoi utiliser une liste chaînée ?

Avant de nous lancer dans l'implémentation, il est crucial de comprendre la raison d'être des listes chaînées. En Python, nous disposons des listes (list), qui sont en réalité des tableaux dynamiques. Pourquoi s'encombrer d'une nouvelle structure ? La vidéo suivante expose de manière très claire le compromis fondamental entre tableaux et listes chaînées.

En résumé, les tableaux offrent un accès en temps constant $O(1)$ à n'importe quel élément par son indice, mais l'insertion ou la suppression d'un élément en début ou milieu de tableau a un coût linéaire $O(n)$, car elle nécessite de décaler tous les éléments suivants. Les listes chaînées, quant à elles, excellent pour les insertions/suppressions en tête ($O(1)$) mais sacrifient l'accès direct, qui devient une opération en $O(n)$.

2. Anatomie d'une liste chaînée

Une liste chaînée est une séquence de nœuds (ou maillons). Chaque nœud est un objet simple contenant deux informations essentielles :

1. La valeur (les données que l'on souhaite stocker).
2. Un pointeur (une référence) vers le nœud suivant.

Le dernier nœud de la liste a un pointeur qui ne mène nulle part, classiquement une valeur None en Python. La liste entière est accessible via une seule référence : celle qui pointe vers son premier nœud, la tête (head).

Pour implémenter cela en Python, nous utiliserons deux classes :

• Une classe Node pour représenter un maillon.
• Une classe LinkedList qui encapsulera la logique de la liste et ne contiendra qu'une référence vers la tête.

La vidéo suivante met en place ces deux classes de base.

Voici le squelette de notre code basé sur la vidéo :

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    



    # Nos méthodes d'insertion, suppression et recherche viendront ici.

3. Implémentation des opérations fondamentales

Nous allons maintenant implémenter les opérations requises. Pour chaque opération, nous décrirons d'abord la logique, puis vous visionnerez le segment vidéo correspondant pour voir le code prendre vie.

Insertion

L'insertion consiste à créer un nouveau nœud et à manipuler les pointeurs next pour l'intégrer dans la chaîne.

a) Insertion en tête de liste (prepend)

C'est l'opération la plus efficace d'une liste chaînée.

1. Créez un nouveau nœud avec la valeur donnée.
2. Faites pointer le next de ce nouveau nœud vers la tête actuelle de la liste.
3. Mettez à jour la tête de la liste pour qu'elle pointe vers ce nouveau nœud.

Cette opération est en $O(1)$ car elle ne dépend pas de la taille de la liste.

b) Insertion en fin de liste (append)

1. Si la liste est vide, l'insertion en fin est identique à l'insertion en tête.
2. Sinon, parcourez la liste depuis la tête jusqu'à atteindre le dernier nœud (celui dont le next est None).
3. Créez un nouveau nœud.
4. Faites pointer le next de ce dernier nœud vers le nouveau nœud.

Cette opération est en $O(n)$ car dans le pire des cas, il faut parcourir toute la liste.

c) Insertion à un indice spécifique (insert)

1. Si l'indice est 0, c'est une insertion en tête.
2. Sinon, parcourez la liste jusqu'au nœud situé à index - 1 (le prédécesseur).
3. Créez un nouveau nœud.
4. Faites pointer le next du nouveau nœud vers le next du prédécesseur.
5. Faites pointer le next du prédécesseur vers le nouveau nœud.

Cette opération est en $O(n)$ en raison du parcours.

Recherche

La recherche dans une liste chaînée se fait toujours par parcours séquentiel depuis la tête.

a) Recherche par valeur (contains)

Parcourez la liste nœud par nœud. Si la valeur du nœud courant correspond à la valeur cherchée, retournez True. Si vous atteignez la fin de la liste sans la trouver, retournez False. La complexité est $O(n)$.

b) Recherche par indice (get)

Parcourez la liste en maintenant un compteur. Lorsque le compteur atteint l'indice désiré, retournez la valeur du nœud courant. Si la fin de la liste est atteinte avant, l'indice est invalide. La complexité est $O(n)$.

Suppression

La suppression est l'opération la plus délicate, car elle requiert de modifier le pointeur next du nœud précédant celui que l'on souhaite supprimer.

a) Suppression par valeur (delete)

1. Cas particulier : si le nœud à supprimer est la tête, faites simplement pointer la tête sur le nœud suivant.
2. Sinon, parcourez la liste en gardant une référence sur le nœud courant et son successeur.
3. Lorsque la valeur du successeur est celle à supprimer, "court-circuitez" la chaîne : faites pointer le next du nœud courant vers le next de son successeur (courant.next = courant.next.next).
   En Python, le garbage collector se chargera de libérer la mémoire du nœud qui n'est plus référencé.

La complexité est $O(n)$.

b) Suppression par indice (pop)

La logique est identique à la suppression par valeur, mais la condition d'arrêt est basée sur un compteur d'indice. Vous devez vous arrêter au nœud d'indice index - 1 pour modifier son pointeur next. La complexité est $O(n)$.

4. Code complet et test

Après avoir exploré chaque méthode séparément, il est temps de voir la classe complète en action.

Je vous encourage vivement à recopier le code, à le faire fonctionner sur votre machine et à le tester avec vos propres exemples. C'est en forgeant qu'on devient forgeron.

Conclusion

Aujourd'hui, nous avons non seulement compris l'intérêt des listes chaînées, mais surtout, nous les avons implémentées de A à Z en Python. C'est une étape majeure.

Points clés à retenir :

• Une liste chaînée est une structure dynamique composée de nœuds, chacun contenant une valeur et un pointeur next.
• Le principal compromis par rapport aux tableaux est un accès séquentiel $O(n)$ en échange d'une insertion/suppression en tête en $O(1)$.
• Les opérations d'insertion et de suppression se résument à une manipulation précise des pointeurs next.
• Pour supprimer un nœud (ou en insérer un après un nœud donné), il est impératif d'avoir une référence à son prédécesseur.

Dans notre prochaine leçon, nous reviendrons sur les tableaux dynamiques. Nous définirons la notion de complexité amortie et l'appliquerons à l'analyse des opérations sur un tableau dynamique. Cela nous permettra de comprendre formellement pourquoi, en moyenne, l'ajout d'éléments à une liste Python est considéré comme efficace, malgré les coûteuses opérations de réallocation que nous avons évoquées au début de cette leçon.