Listes chaînées en Python : tutoriel avec exemples

Une liste chaînée est une structure de données qui joue un rôle clé dans l’organisation et la gestion des données. Elle contient une série de nœuds stockés à des emplacements aléatoires en mémoire, ce qui permet une gestion efficace de la mémoire. Chaque nœud d’une liste chaînée comporte deux éléments principaux : la partie données et une référence vers le nœud suivant dans la séquence.

Si ce concept vous semble complexe au premier abord, pas d’inquiétude !

Nous allons le ramener à ses fondamentaux pour expliquer ce que sont les listes chaînées, pourquoi on les utilise et les avantages spécifiques qu’elles offrent.

Pourquoi utiliser des listes chaînées ?

Les listes chaînées ont été conçues pour contourner plusieurs inconvénients liés au stockage des données dans des listes et des tableaux classiques, comme indiqué ci-dessous :

Facilité d’insertion et de suppression

Dans les listes, insérer ou supprimer un élément à une position autre que la fin oblige à décaler tous les éléments suivants. Ce processus a une complexité en temps de O(n) et peut fortement dégrader les performances, surtout à mesure que la liste grandit. Si vous n’êtes pas encore familier avec le fonctionnement ou l’implémentation des listes, vous pouvez lire notre tutoriel sur les listes Python.

Les listes chaînées, elles, fonctionnent différemment. Elles stockent les éléments dans des emplacements de mémoire non contigus et les relient via des pointeurs vers les nœuds suivants. Cette structure permet d’ajouter ou de retirer des éléments à n’importe quelle position en modifiant simplement les liens pour inclure un nouveau nœud ou contourner celui supprimé.

Dès que vous disposez d’une référence directe vers le nœud au point d’insertion ou de suppression, l’opération elle-même est en O(1). En revanche, trouver cette position exige toujours un parcours en O(n), donc l’avantage en O(1) ne s’applique que lorsque vous détenez déjà un pointeur vers le nœud concerné (par exemple lorsque vous travaillez en tête de liste).

Taille dynamique

Les listes Python sont des tableaux dynamiques, ce qui signifie qu’elles offrent la souplesse de modifier leur taille.

Cependant, ce processus implique une série d’opérations complexes, dont la réallocation du tableau vers un bloc mémoire plus grand. Cette réallocation est peu efficace puisque les éléments sont recopiés dans un nouveau bloc, en allouant potentiellement plus d’espace que nécessaire sur le moment.

À l’inverse, les listes chaînées peuvent grandir et rétrécir dynamiquement sans réallocation ni redimensionnement. Elles sont donc à privilégier pour les tâches nécessitant une grande flexibilité.

Efficience mémoire

Les listes allouent la mémoire de tous leurs éléments dans un bloc contigu. Si une liste doit dépasser sa taille initiale, elle doit allouer un nouveau bloc contigu plus grand puis copier tous les éléments existants dans ce bloc. Ce processus est coûteux en temps et inefficace, en particulier pour les grandes listes. À l’inverse, si la taille initiale est surestimée, la mémoire inutilisée est gaspillée.

En comparaison, les listes chaînées allouent la mémoire séparément pour chaque élément. Cette organisation permet une meilleure utilisation de la mémoire, car l’espace nécessaire pour de nouveaux éléments peut être alloué au fur et à mesure de leur ajout.

Quand utiliser des listes chaînées ?

Même si les listes chaînées présentent des avantages par rapport aux listes et tableaux classiques, comme la taille dynamique et l’efficience mémoire, elles ont aussi des limites. Comme il faut stocker des pointeurs pour référencer le nœud suivant, l’utilisation mémoire par élément est plus élevée. De plus, cette structure ne permet pas l’accès direct aux données. Accéder à un élément exige un parcours séquentiel depuis le début de la liste, avec une complexité de recherche en O(n).

Le choix entre une liste chaînée et un tableau dépend des besoins spécifiques de l’application. Les listes chaînées sont particulièrement utiles lorsque :

• Vous devez insérer et supprimer fréquemment de nombreux éléments
• La taille des données est imprévisible ou susceptible d’évoluer souvent
• L’accès direct aux éléments n’est pas requis
• Le jeu de données contient de gros éléments ou structures

Types de listes chaînées

Il existe trois types de listes chaînées, chacune offrant des avantages spécifiques selon les cas d’usage :

Listes simplement chaînées

Liste simplement chaînée

Une liste simplement chaînée est le type le plus simple : chaque nœud contient des données et une référence vers le nœud suivant. Elle ne peut être parcourue que dans un seul sens : de la tête (premier nœud) à la queue (dernier nœud).

Chaque nœud d’une liste simplement chaînée comprend généralement deux parties :

• Données : les informations stockées dans le nœud.
• Pointeur suivant : une référence vers le nœud suivant. Le pointeur du dernier nœud est généralement défini à null.

Puisque ces structures ne se parcourent que dans un seul sens, accéder à un élément donné par valeur ou par index impose de partir de la tête et d’avancer nœud par nœud jusqu’au nœud recherché. Cette opération a une complexité en O(n), ce qui est moins efficace pour de grandes listes.

Insérer ou supprimer un nœud au début d’une liste simplement chaînée est très efficace avec une complexité de O(1). En revanche, insérer ou supprimer au milieu ou à la fin exige de parcourir la liste jusqu’au point visé, ce qui mène à une complexité en O(n).

Par leur conception, les listes simplement chaînées sont utiles lorsque les opérations se font principalement en tête de liste.

Listes doublement chaînées

Liste doublement chaînée

Un inconvénient des listes simplement chaînées est qu’on ne peut les parcourir que dans un seul sens, sans possibilité de revenir au nœud précédent si nécessaire. Cette contrainte limite les opérations nécessitant une navigation bidirectionnelle.

Les listes doublement chaînées résolvent ce problème en ajoutant un pointeur supplémentaire dans chaque nœud, ce qui permet un parcours dans les deux sens. Chaque nœud contient alors trois éléments : les données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent.

Listes chaînées circulaires

Liste chaînée circulaire

Les listes chaînées circulaires sont une forme particulière où le dernier nœud pointe vers le premier, formant une boucle. Contrairement aux listes simplement ou doublement chaînées vues plus haut, la liste circulaire n’a pas de fin : elle se répète.

Cette cyclicité les rend idéales pour des scénarios nécessitant un parcours continu, comme des jeux de plateau qui reviennent du dernier joueur au premier, ou des algorithmes informatiques comme l’ordonnancement en tourniquet (round-robin).

Résumé des complexités

Voici, en un coup d’œil, la comparaison avec les listes Python :

À retenir : les listes chaînées excellent pour les insertions et suppressions en tête (O(1)), mais sont moins performantes pour le reste. Si vous n’ajoutez ni ne retirez souvent des éléments au début de votre structure, une liste Python classique sera probablement un meilleur choix.

Comment créer une liste chaînée en Python

Maintenant que nous savons ce que sont les listes chaînées, pourquoi on les utilise et leurs variantes, passons à leur implémentation en Python. Le notebook de ce tutoriel est disponible dans ce workbook DataLab ; en en créant une copie, vous pourrez modifier et exécuter le code. Idéal si vous rencontrez des difficultés à l’exécuter localement !

Initialiser un nœud

Comme vu précédemment, un nœud est un élément de la liste chaînée qui stocke des données et une référence vers le nœud suivant. Voici comment définir un nœud en Python :

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

    def __repr__(self):
        return f"Node({self.data})"

Le code ci-dessus initialise un nœud en accomplissant deux actions principales : l’attribut « data » du nœud reçoit la valeur à stocker, et l’attribut « next » représente l’adresse du nœud suivant. Il est initialement défini à None, ce qui signifie que le nœud n’est pas encore lié à un autre. À mesure que nous ajouterons de nouveaux nœuds à la liste chaînée, cet attribut sera mis à jour pour pointer vers le nœud suivant.

Créer la classe de liste chaînée

Ensuite, créons la classe de liste chaînée. Elle encapsulera toutes les opérations de gestion des nœuds, comme l’insertion et la suppression. Commençons par l’initialisation :

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

En définissant self.head à None, nous indiquons que la liste est initialement vide et qu’aucun nœud n’est référencé. Nous allons maintenant la peupler en insérant de nouveaux nœuds.

Insérer un nouveau nœud au début d’une liste chaînée

Au sein de la classe LinkedList, ajoutons une méthode pour créer un nouveau nœud et le placer en tête de liste :

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

À chaque appel de cette méthode, un nouveau nœud est créé avec les données fournies. Le pointeur « next » de ce nœud est défini sur la tête actuelle, ce qui place ce nœud devant les autres. Enfin, ce nouveau nœud devient la tête de la liste.

Nous allons maintenant remplir cette liste chaînée avec une série de mots pour mieux comprendre l’insertion. Pour cela, commençons par créer une méthode qui parcourt et affiche le contenu de la liste :

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

Cette méthode affiche le contenu de la liste chaînée. Utilisons maintenant les méthodes définies pour y insérer une série de mots : « the quick brown fox ».

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

Les lignes ci-dessus devraient produire la sortie suivante :

"the quick brown fox"

Insérer un nouveau nœud à la fin d’une liste chaînée

Créons à présent une méthode insertAtEnd dans la classe LinkedList pour ajouter un nouveau nœud en fin de liste. Si la liste est vide, ce nœud deviendra la tête. Sinon, il sera ajouté après le dernier nœud. Voyons cela en pratique :

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Cette méthode commence par créer un nouveau nœud. Elle vérifie ensuite si la liste est vide : si oui, le nouveau nœud devient la tête. Sinon, elle parcourt la liste pour trouver le dernier nœud et affecte son pointeur « next » au nouveau nœud.

Intégrez maintenant cette méthode dans votre classe LinkedList et utilisez-la pour ajouter un mot à la fin de la liste. Pour cela, modifiez votre fonction principale comme suit :

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

Notez que nous avons simplement appelé la méthode insertAtEnd pour ajouter le mot « jumps » à la fin de la liste. Le code ci-dessus devrait produire la sortie suivante :

"the quick brown fox jumps"

Supprimer un nœud au début d’une liste chaînée

Supprimer le premier nœud d’une liste chaînée est simple : il suffit de faire pointer la tête vers le deuxième nœud. Ainsi, le premier nœud ne fait plus partie de la liste. Pour cela, ajoutez la méthode suivante à la classe LinkedList :

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

Supprimer un nœud à la fin d’une liste chaînée

Pour supprimer le dernier nœud d’une liste chaînée, il faut parcourir la liste pour trouver l’avant-dernier nœud et définir son pointeur « next » à None. De cette façon, le dernier nœud est détaché de la liste. Copiez-collez la méthode suivante dans votre classe LinkedList :

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

Cette méthode vérifie d’abord si la liste est vide, et renvoie un message le cas échéant. Sinon, si la liste ne contient qu’un nœud, celui-ci est supprimé. Pour les listes à plusieurs nœuds, la méthode repère l’avant-dernier nœud et met sa référence « next » à None.

Mettons maintenant à jour la fonction principale pour supprimer des éléments au début et à la fin de la liste chaînée :

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

Ce code affichera la liste avant et après suppression, illustrant le fonctionnement des opérations d’insertion et de suppression dans les listes chaînées. Vous devriez obtenir la sortie suivante :

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

Rechercher une valeur précise dans la liste chaînée

La dernière opération que nous allons voir ici est la recherche d’une valeur spécifique dans la liste chaînée. Pour ce faire, la méthode démarre à la tête et parcourt chaque nœud, en vérifiant si les données du nœud correspondent à la valeur recherchée. Voici une implémentation pratique :

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

Pour chercher des valeurs spécifiques dans la liste créée, mettez à jour votre fonction principale afin d’inclure la méthode de recherche que nous venons d’implémenter :

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

Le code ci-dessus produira la sortie suivante :

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

Le mot « quick » a bien été trouvé dans la liste chaînée puisqu’il se trouve en première position. En revanche, « lazy » n’en fait pas partie, d’où l’absence de correspondance.

Pour conclure

Si vous êtes arrivé jusqu’ici, félicitations ! Vous avez désormais une compréhension solide des principes de base des listes chaînées : leur structure, leurs types, comment y ajouter et supprimer des éléments, et comment les parcourir.

Mais le voyage ne s’arrête pas là. Les listes chaînées ne sont qu’une porte d’entrée vers l’univers des structures de données et des algorithmes. Voici quelques pistes pour approfondir le sujet :

Créez votre propre projet

Plongez dans les applications concrètes des listes chaînées en les intégrant à un projet de code ou de data science. Elles servent à développer des systèmes de fichiers, construire des tables de hachage, et même créer des systèmes de navigation GPS ou des jeux de plateau. Pour démarrer vos propres projets, découvrez nos projets data science guidés et gratuits, qui vous apprennent à résoudre des problèmes réels en Python, R et SQL.

Apprenez les structures de données et algorithmes

Étudier d’autres structures, comme les arbres, piles et files, est la suite logique après les listes chaînées. Elles s’appuient sur les mêmes principes et vous aident à résoudre efficacement un plus large éventail de problèmes. Les arbres et arbres binaires de recherche, par exemple, étendent le concept des listes chaînées sous une forme hiérarchique, où chaque nœud peut se connecter à plusieurs éléments.

Si ces notions vous semblent encore abstraites, pas d’inquiétude ! Datacamp propose un cours complet sur les structures de données et algorithmes en Python qui vous guidera plus en détail. Vous commencerez par les piles, arbres, tables de hachage, files et graphes. Au fil du cours, vous découvrirez les algorithmes de recherche et de tri, de quoi devenir un programmeur plus efficace et un meilleur résolveur de problèmes.

Explorer des concepts avancés de listes chaînées

Dans ce tutoriel, nous avons implémenté des listes simplement chaînées, avec des opérations d’insertion, de suppression et de parcours.

Vous pouvez aller plus loin en apprenant l’implémentation des listes doublement chaînées et circulaires. Les skip lists sont une autre extension des listes chaînées qui accélèrent la recherche en facilitant un accès plus rapide aux éléments.

Découvrir ces structures avancées fera passer vos compétences techniques au niveau supérieur et améliorera sensiblement vos capacités de programmation, vous préparant à des défis plus complexes en data science, développement logiciel et ingénierie en apprentissage automatique.

Si vous préférez une introduction plus accessible à la programmation avant d’aborder ces sujets avancés, explorez notre parcours de compétences Python Programming. Il propose une série de cours pour acquérir les fondamentaux du langage.