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 crucial dans l'organisation et la gestion des données. Il contient une série de nœuds qui sont stockés à des emplacements aléatoires dans la mémoire, ce qui permet une gestion efficace de la mémoire. Chaque nœud d'une liste chaînée contient deux éléments principaux : les données et une référence au nœud suivant dans la séquence.

Si ce concept semble complexe à première vue, ne vous inquiétez pas !

Nous allons reprendre les principes de base pour expliquer ce que sont les listes chaînées, pourquoi nous les utilisons et les avantages uniques qu'elles offrent.

Pourquoi des listes liées ?

Les listes liées ont été créées pour remédier à divers inconvénients liés au stockage de données dans des listes et des tableaux ordinaires, comme indiqué ci-dessous :

Facilité d'insertion et de suppression

Dans les listes, l'insertion ou la suppression d'un élément à une position autre que la fin nécessite de déplacer tous les éléments suivants à une position différente. Ce processus a une complexité temporelle de O(n) et peut dégrader considérablement les performances, en particulier lorsque la taille de la liste augmente. Si vous n'êtes pas encore familiarisé avec le fonctionnement des listes ou leur implémentation, vous pouvez lire notre tutoriel sur les listes en Python.

Les listes chaînées, en revanche, fonctionnent différemment. Ils stockent les éléments dans divers emplacements de mémoire non contigus et les relient par des pointeurs aux nœuds suivants. Cette structure permet aux listes chaînées d'ajouter ou de supprimer des éléments à n'importe quelle position en modifiant simplement les liens pour inclure un nouvel élément ou contourner l'élément supprimé.

Une fois que la position de l'élément est identifiée et qu'il existe un accès direct au point d'insertion ou de suppression, l'ajout ou la suppression de nœuds peut être réalisé en O(1) temps.

Taille dynamique

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

Toutefois, ce processus implique une série d'opérations complexes, notamment la réaffectation du tableau à un nouveau bloc de mémoire plus grand. Cette réaffectation est inefficace car les éléments sont copiés dans un nouveau bloc, ce qui peut entraîner l'allocation de plus d'espace que nécessaire.

En revanche, les listes chaînées peuvent croître et décroître dynamiquement sans nécessiter de réaffectation ou de redimensionnement. Cela en fait une option préférable pour les tâches qui nécessitent une grande flexibilité.

Efficacité de la mémoire

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

En revanche, les listes chaînées allouent de la mémoire à chaque élément séparément. Cette structure permet une meilleure utilisation de la mémoire puisque la mémoire pour les nouveaux éléments peut être allouée au fur et à mesure qu'ils sont ajoutés.

Quand devez-vous utiliser des listes liées ?

Si les listes chaînées présentent certains avantages par rapport aux listes et aux tableaux ordinaires, tels que la taille dynamique et l'efficacité de la mémoire, elles ont également leurs limites. Étant donné que des pointeurs doivent être stockés pour chaque élément afin de référencer le nœud suivant, l'utilisation de la mémoire par élément est plus élevée lors de l'utilisation de listes chaînées. En outre, cette structure de données ne permet pas un accès direct aux données. L'accès à un élément nécessite une traversée séquentielle depuis le début de la liste, ce qui se traduit par une complexité de temps de recherche 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 dans les cas suivants

• Vous devez fréquemment insérer et supprimer de nombreux éléments
• La taille des données est imprévisible ou susceptible de changer fréquemment.
• L'accès direct aux éléments n'est pas obligatoire
• L'ensemble de données contient des éléments ou des structures de grande taille

Types de listes chaînées

Il existe trois types de listes chaînées, chacune offrant des avantages uniques pour différents scénarios. Ces types sont les suivants :

Listes à lien unique

Liste à lien unique

Une liste simple est le type le plus simple de liste liée, où chaque nœud contient des données et une référence au nœud suivant dans la séquence. Ils ne peuvent être parcourus que dans une seule direction - de la tête (le premier nœud) à la queue (le dernier nœud).

Chaque nœud d'une liste à lien unique se compose généralement de deux parties :

• Données: L'information réelle stockée dans le nœud.
• Prochain pointeur: Une référence au nœud suivant. Le pointeur suivant du dernier nœud est généralement défini comme nul.

Comme ces structures de données ne peuvent être parcourues que dans une seule direction, l'accès à un élément spécifique par valeur ou par index nécessite de commencer par la tête et de se déplacer séquentiellement à travers les nœuds jusqu'à ce que le nœud souhaité soit trouvé. Cette opération a une complexité temporelle de O(n), ce qui la rend moins efficace pour les grandes listes.

L'insertion et la suppression d'un nœud au début d'une liste à lien unique est très efficace avec une complexité temporelle de O(1). Cependant, l'insertion et la suppression au milieu ou à la fin nécessitent de parcourir la liste jusqu'à ce point, ce qui entraîne une complexité temporelle de O(n).

La conception des listes à lien unique en fait une structure de données utile pour effectuer des opérations au début de la liste.

Listes à double lien

Liste à double lien

L'un des inconvénients des listes à lien unique est qu'elles ne peuvent être parcourues que dans une seule direction et qu'il n'est pas possible de revenir au nœud précédent si nécessaire. Cette contrainte limite notre capacité à effectuer des opérations nécessitant une navigation bidirectionnelle.

Les listes à double lien résolvent ce problème en incorporant un pointeur supplémentaire dans chaque nœud, ce qui garantit que la liste peut être parcourue dans les deux sens. Chaque nœud d'une liste doublement liée contient 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 circulaire chaînée

Les listes chaînées circulaires sont une forme spécialisée de liste chaînée dans laquelle le dernier nœud pointe vers le premier nœud, créant ainsi une structure circulaire. Cela signifie que, contrairement aux listes simplement et doublement liées que nous avons vues jusqu'à présent, la liste circulaire liée ne se termine pas ; au lieu de cela, elle tourne en boucle.

La nature cyclique des listes chaînées circulaires les rend idéales pour les scénarios qui doivent être parcourus en boucle, tels que les jeux de société qui reviennent en boucle du dernier joueur au premier, ou dans les algorithmes informatiques tels que l'ordonnancement round-robin.

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

Maintenant que nous avons compris ce que sont les listes chaînées, pourquoi nous les utilisons et leurs variantes, passons à la mise en œuvre de ces structures de données en Python. Le carnet de notes de ce tutoriel est également disponible dans ce classeur DataLab; si vous créez une copie, vous pouvez modifier et exécuter le code. Il s'agit d'une excellente option si vous rencontrez des difficultés à exécuter le code par vous-même !

Initialisation d'un nœud

Comme nous l'avons appris 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 au nœud suivant dans la séquence. Voici comment vous pouvez définir un nœud en Python :

class Node:
    def __init__(self, data):
        self.data = data  # Assigns the given data to the node
        self.next = None  # Initialize the next attribute to null

Le code ci-dessus initialise un nœud en effectuant deux actions principales : L'attribut "data" du nœud se voit attribuer une valeur représentant l'information réelle que le nœud est censé contenir. L'attribut "next" représente l'adresse du nœud suivant. La valeur actuelle est None, ce qui signifie que le nœud n'est lié à aucun autre nœud de la liste. Au fur et à 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éation d'une classe de listes chaînées

Ensuite, nous devons créer la classe de liste chaînée. Il encapsule toutes les opérations de gestion des nœuds, telles que l'insertion et la suppression. Nous commencerons par initialiser la liste chaînée :

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

En fixant la valeur de self.head à None, nous indiquons que la liste chaînée est initialement vide et qu'il n'y a pas de nœuds dans la liste vers lesquels pointer. Nous allons maintenant remplir la liste en insérant de nouveaux nœuds.

Insertion d'un nouveau nœud au début d'une liste chaînée

Dans la classe LinkedList, nous allons ajouter une méthode pour créer un nouveau nœud et le placer au début de la 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 fois que vous appelez la méthode ci-dessus, un nouveau nœud est créé avec les données que vous avez spécifiées. Le pointeur suivant de ce nouveau nœud est placé à la tête actuelle de la liste, ce qui place ce nœud devant les nœuds existants. Enfin, le nœud nouvellement créé devient la tête de liste.

Nous allons maintenant remplir cette liste chaînée avec une série de mots pour mieux comprendre le fonctionnement de l'opération d'insertion. Pour ce faire, nous allons d'abord créer une méthode conçue pour parcourir et imprimer 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

La méthode ci-dessus permet d'imprimer le contenu de notre liste chaînée. Utilisons maintenant les méthodes que nous avons définies pour remplir notre liste avec une série de mots : "le renard brun rapide".

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 de code ci-dessus devraient produire le résultat suivant :

"the quick brown fox"

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

Nous allons maintenant créer une méthode appelée insertAtEnd dans la classe LinkedList, afin de créer un nouveau nœud à la fin de la liste. Si la liste est vide, le nouveau nœud devient la tête de liste. Sinon, il sera ajouté au dernier nœud de la liste. Voyons comment cela fonctionne en pratique :

def insertAtEnd(self, new_data):
        new_node = Node(new_data)  # Create a new node
        if self.head is None:
            self.head = new_node  # If the list is empty, make the new node the head
            return
        last = self.head 
        while last.next:  # Otherwise, traverse the list to find the last node
            last = last.next
        last.next = new_node  # Make the new node the next node of the last node

La méthode ci-dessus commence par la création d'un nouveau nœud. Il vérifie ensuite si la liste est vide et, si c'est le cas, le nouveau nœud est désigné comme tête de liste. Sinon, il parcourt la liste pour trouver le dernier nœud et place le pointeur de ce nœud sur le nouveau nœud.

Nous devons maintenant inclure cette méthode dans notre classe LinkedList et l'utiliser pour ajouter un mot à la fin de notre liste. Pour ce faire, modifiez votre fonction principale pour qu'elle ressemble à ceci :

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()

Remarquez que nous avons simplement appelé la méthode insertAtEnd pour imprimer le mot "jumps" à la fin de la liste. Le code ci-dessus devrait produire le résultat suivant :

"the quick brown fox jumps"

Suppression d'un nœud au début d'une liste chaînée

La suppression du premier nœud d'une liste chaînée est facile puisqu'il s'agit simplement de pointer la tête de cette liste vers le deuxième nœud. Ainsi, le premier nœud ne fera plus partie de la liste. Pour ce faire, incluez la méthode suivante dans 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

Suppression d'un nœud à la fin d'une liste chaînée

Pour supprimer le dernier nœud d'une liste chaînée, nous devons parcourir la liste pour trouver l'avant-dernier nœud et changer son pointeur suivant en None. Ainsi, le dernier nœud ne fera plus partie de la liste. Pour ce faire, copiez et 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

La méthode ci-dessus vérifie d'abord si la liste chaînée est vide, et renvoie un message à l'utilisateur si c'est le cas. Sinon, si la liste contient un seul nœud, ce nœud est supprimé. Pour les listes comportant plusieurs nœuds, la méthode localise l'avant-dernier nœud et sa référence au nœud suivant est mise à jour à None.

Mettons maintenant à jour la fonction principale afin de 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()

Le code ci-dessus imprime la liste avant et après la suppression, montrant ainsi comment les opérations d'insertion et de suppression fonctionnent dans les listes chaînées. Vous devriez voir la sortie suivante après avoir exécuté ce code :

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

Recherche d'une valeur spécifique dans la liste chaînée

La dernière opération que nous allons apprendre dans ce chapitre est la récupération d'une valeur spécifique dans la liste chaînée. Pour ce faire, la méthode doit commencer à la tête de la liste et parcourir chaque nœud, en vérifiant si les données du nœud correspondent à la valeur recherchée. Voici une mise en œuvre pratique de cette opération :

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 trouver des valeurs spécifiques dans la liste chaînée que nous avons créée, mettez à jour votre fonction principale pour y inclure la méthode de recherche que nous venons de créer :

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 le résultat suivant :

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 "rapide" a été localisé avec succès dans la liste chaînée puisqu'il existe en première position de la liste. Cependant, le mot "paresseux" ne fait pas partie de la liste, c'est pourquoi il n'a pas été trouvé.

Réflexions finales

Si vous êtes arrivé jusqu'ici, félicitations ! Vous avez maintenant une bonne compréhension des principes de base des listes chaînées, y compris leur structure, leurs types, la manière d'ajouter et de supprimer des éléments, et la manière de les parcourir.

Mais le voyage ne s'arrête pas là. Les listes chaînées ne sont que le début du monde des structures de données et des algorithmes. Voici quelques pistes pour approfondir votre compréhension du sujet :

Créez votre propre projet

Plongez dans les applications pratiques des listes chaînées en les intégrant dans un projet de codage ou de science des données. Les listes chaînées sont utilisées pour développer des systèmes de fichiers, construire des tableaux de hachage et même créer des systèmes de navigation GPS et des jeux de société. Pour vous lancer dans vos propres projets, consultez nos projets guidés gratuits en science des données qui vous apprennent à résoudre des problèmes du monde réel en Python, R et SQL.

Apprendre les structures de données et les algorithmes

L'apprentissage d'autres structures de données, telles que les arbres, les piles et les files d'attente, est une progression naturelle après la compréhension des listes chaînées. Ces structures s'appuient sur les principes des listes chaînées et vous aident à résoudre efficacement un plus grand nombre de problèmes de calcul. Les arbres et les arbres de recherche binaires, par exemple, étendent le concept des listes liées à une forme hiérarchique, permettant à chaque nœud de se connecter à plusieurs éléments de la structure de données.

Si ces concepts ne vous semblent pas familiers, ne vous inquiétez pas ! DataCamp propose un cours entier sur les structures de données et les algorithmes en Python qui vous permettra d'approfondir ces concepts. Vous apprendrez d'abord à connaître les structures de données telles que les piles, les arbres, les tableaux de hachage, les files d'attente et les graphes. Au fur et à mesure que vous progresserez dans le cours, vous comprendrez les algorithmes de recherche et de tri, ce qui vous aidera à devenir un programmeur et un résolveur de problèmes plus efficace.

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

Nous avons mis en œuvre des listes à lien unique dans ce tutoriel, couvrant des opérations telles que l'insertion, la suppression et la traversée.

Vous pouvez approfondir ces connaissances en apprenant à mettre en œuvre des listes doublement et circulairement liées. Les listes de saut sont une autre extension des listes liées qui permettent des opérations de recherche plus rapides en facilitant l'accès aux éléments.

L'apprentissage de ces structures de données avancées fera passer vos compétences techniques au niveau supérieur et améliorera considérablement vos capacités de programmation, vous préparant ainsi à relever des défis plus complexes dans des domaines tels que la science des données, le développement de logiciels et l'ingénierie de l'apprentissage automatique.

Si vous souhaitez une introduction à la programmation plus conviviale pour les débutants avant d'aborder ces sujets avancés, explorez notre filière professionnelle de programmeur Python. Il propose une série de cours qui vous apprendront les bases de la langue.