La structure de données de la liste chaînée et comment l’utiliser

Vous connaissez peut-être les tableaux, mais il existe de nombreuses structures de données que vous pouvez utiliser en programmation. À certains égards, une liste chaînée est similaire à un tableau, mais il existe quelques différences essentielles. Découvrez ce qu’est une liste chaînée, les différents types et comment en utiliser une avec cet article.

Qu’est-ce qu’une liste chaînée ?

Comme un tableau, une liste linéaire est une structure de données linéaire. Mais la différence réside dans la manière dont ils stockent et accèdent aux données. Alors qu’un tableau stocke des éléments dans un bloc de mémoire contigu, une liste chaînée contient des éléments sous forme de nœuds, chaque nœud pointant vers l’élément suivant de la liste. En tant que tels, ils ne sont pas stockés de manière contiguë et les éléments ne sont pas accessibles à l’aide d’un index. Au lieu de cela, des pointeurs sont affectés à chaque nœud, qui dictent quel nœud est le suivant dans la séquence. Comme avec un tableau dynamique, les listes liées peuvent être modifiées en ajoutant ou en supprimant des nœuds si nécessaire.

Quels sont les bénéfices?

Maintenant que nous avons couvert exactement ce qu’est une liste chaînée, vous vous demandez peut-être pourquoi vous voudriez en utiliser une. Voici quelques avantages :

• À moins que vous n’utilisiez un tableau dynamique, la taille du tableau a tendance à être fixe, tandis que les listes chaînées peuvent être augmentées ou diminuées selon le cas.
• L’insertion ou la suppression d’éléments nécessite un temps constant, contrairement aux tableaux où d’autres éléments devront être décalés.
• Les listes chaînées ont tendance à être plus faciles sur vos contraintes de mémoire, en particulier avec de gros volumes de données. En effet, la mémoire n’est utilisée que pour les nœuds requis, mais la nature contiguë des tableaux signifie que vous pouvez prendre en charge certaines données dont vous n’avez pas besoin pour vos opérations.
• Il est plus facile de maintenir la persistance des données avec des listes liées, car les données peuvent être sérialisées plus facilement que dans des tableaux. Cela simplifie la transmission de données entre plusieurs programmes ou après la fin des programmes.
• Là où vous avez des données clairsemées, c’est-à-dire avec des éléments vides, un tableau les stockerait toujours. Une liste liée, cependant, ne stocke que les valeurs qui ne sont pas vides.

Quels sont les différents types de listes liées ?

Il existe plusieurs types de listes liées que vous pouvez utiliser, chacune avec ses propres qualités. Nous allons donner un bref aperçu ici et comment les implémenter en Python.

Liste chaînée simple

Comme vous pouvez vous y attendre, il s’agit du type de liste chaînée le plus simple, où vous ne pouvez parcourir la liste que dans une seule direction. Chaque pointeur pointe vers le nœud suivant, le nœud final ne pointant vers rien, ou NULL. Ceci est également connu sous le nom de liste liée individuellement. Le code pour implémenter une liste chaînée simple en Python est le suivant :

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

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

    def add(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_Node
        else:
            current_node = self.head
            while current_node.next is not None:
                current_node = current_node.next
            current_node.next = new_node
     
    def remove(self, data):
        if self.head is None:
            return

        if self.head.data == data:
            self.head = self.head.next
            return

        current_node = self.head
        while current_node.next is not None:
            if current_node.next.data == data:
                current_node.next = current_node.next.next
                return

    def display(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next

my_list = LinkedList()

my_list.add(1)
my_list.add(2)
my_list.add(3)

my_list.display()

my_list.remove(2)

my_list.display

Explication

C’est un bloc de code assez étendu, mais pas trop difficile à comprendre.

Tout d’abord, nous définissons les classes « Node » et « LinkedList ». La classe « Node » représente un nœud dans la liste, chacun avec un pointeur (indiqué par « self.next »). La liste est représentée par « LinkedList », et nous avons implémenté un nœud d’en-tête, qui permet une insertion ou une suppression plus facile des éléments.

La fonction « ajouter » indique qu’un nouveau nœud doit être ajouté à la fin de la liste. Si la liste est vide, le nœud d’en-tête est défini sur le nouveau nœud créé. Si elle n’est pas vide, alors la liste est parcourue jusqu’au dernier nœud et la pointe vers le nouveau nœud.

La fonction « supprimer » fonctionne en supprimant le premier nœud de la liste. S’il s’agit du nœud d’en-tête, le nœud suivant devient alors le nœud d’en-tête. Si le nœud principal n’a pas les données données, alors la liste est parcourue pour les trouver. Une fois qu’il a trouvé le nœud avec les données données, son attribut « suivant » est défini sur le nœud suivant, ce qui supprime ce nœud de la liste.

« Display » parcourt la liste et imprime les données trouvées à chaque nœud.

Les données de la liste sont définies avec la classe « LinkedList » à la fin, avec des nœuds de valeurs de données 1, 2 et 3. Le nœud 2 a été supprimé pour montrer le processus de suppression, et les deux listes sont imprimées pour la sortie. Consultez la capture d’écran pour savoir comment cela fonctionne.

Liste doublement chaînée

Ceci est similaire à une liste simple, sauf que la traversée peut se produire dans les deux sens, vers l’avant et vers l’arrière. Pour implémenter cela, nous pouvons utiliser le code suivant :

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def add(self,data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def remove(self, data):
        current_node = self.head
        while current_node is not None:
            if current_node.data == data:
                if current_node.prev is not None:
                    current_node.prev.next = current_node.next
                else:
                    self.head = current_node.next
                if current_node.next is not None:
                    current_node.next.prev = current_node.prev
                else:
                    self.tail = current_node.prev
                return

            current_node = current_node.next

    def display(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next

my_list = DoublyLinkedList()

my_list.add(1)
my_list.add(2)
my_list.add(3)

my_list.display()

my_list.remove(3)

my_list.display() 

Explication

Une grande partie du code de cet exemple est similaire, mais il existe quelques différences.

Nous définissons la classe « Node » de la même manière, mais il y a des références au nœud précédent ainsi qu’au nœud suivant cette fois. De même, la classe ‘ »DoublyLinkedList » représente la liste mais a des instances fonctionnant à la fois comme tête et queue de la liste.

Comme précédemment, la fonction « add » ajoute un nouveau nœud à la fin de la liste. Mais si la liste est vide, alors la tête et la queue sont définies sur ce nouveau nœud. Lorsque la liste n’est pas vide, l’attribut « prev » du nouveau nœud est défini sur la queue actuelle, et l’attribut « next » de la queue actuelle sur le nouveau nœud, et la queue est remplacée par le nouveau nœud.

La fonction « supprimer » supprime le premier nœud de la liste avec les données données. Les attributs « prev » et « next » des nœuds adjacents sont mis à jour pour éviter le nœud actuel, le supprimant ainsi de la liste. Si le nœud en question est la tête ou la queue, cet attribut est également mis à jour pour refléter cela.

Enfin, les fonctions « display » et « my_list » sont en grande partie les mêmes, mais cette fois, nous avons supprimé le nœud avec la valeur de données 3. Les captures d’écran illustrent l’exécution du code.

Listes liées circulaires

Un autre type de liste chaînée est une liste circulaire. Comme son nom l’indique, il s’agit d’une liste où il n’y a pas de « fin ». Le nœud de fin est reconnecté au nœud de début. Un exemple est vu avec le code suivant :

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

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

    def add(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
             current_node = self.head
             while current_node.next is not self.head:
                 current_node = current_node.next
             current_node.next = new_node
             new_node.next = self.head

     def remove(self,data):
         if self.head is None:
             return

         if self.head.data == data:
             current_node = self.head
             while current_node.next is not self.head:
                 current_node = current_node.next
             current_node.next = self.head.next
             self.head = self.head.next
         else:
              current_node = self.head
              while current_node.next is not self.head:
                  if current_node.next.data == data:
                      current_node.next = current_node.next.next
                      return
                  current_node = current_node.next

      def display(self):
          if self.head is None:
              return

          current_node = self.head
          while True:
              print(current_node.data)
              current_node = current_node.next
              if current_node is self.head:
                  break

my_list = CircularLinkedList()

my_list.add(1)
my_list.add(2)
my_list.add(3)

my_list.display()

Explication

Il y a quelques différences clés ici. Le « new_node.next = self.head » signifie que le nouveau nœud ajouté est le dernier nœud de la liste et pointe vers la tête de la liste, qui est le premier nœud.

La ligne « while current_node.next n’est pas self.head » est utilisée pour parcourir la liste chaînée et ajouter des éléments. Parce qu’il n’y a pas de vraie fin, comme avec la liste chaînée, nous devons vérifier si le nœud actuel est le nœud principal, plutôt que s’il est simplement non nul. Cela évite de changer le nœud principal.

Le code « new_node.next = self.head » garantit que le nœud ajouté à la liste est connecté au nœud principal.

La fonction « supprimer » fonctionne de manière similaire en ce que, si les données données sont contenues dans le premier nœud, elles sont supprimées et le nœud suivant devient le nouveau nœud principal. Si le nœud principal ne contient pas les données données, la liste est parcourue comme précédemment, jusqu’à ce que les données soient trouvées. L’attribut « suivant » est alors affecté au nœud après celui-ci, qui saute ce nœud. Dans l’ensemble, la fonction est la même, mais la mise en œuvre est un peu plus élaborée en raison de la nature circulaire de la liste.

La fonction « affichage » est également très similaire, sauf que nous devons vérifier que nous commençons au nœud principal et interrompre la traversée une fois que nous atteignons à nouveau ce point.

Listes liées circulaires doubles

Puisque nous avons examiné les listes liées simples, doubles et circulaires, il est logique de terminer avec une liste liée circulaire double. Tout à fait la bouchée, mais pas tout à fait insaisissable. Comme on pouvait s’y attendre, cela fait référence à une liste chaînée circulaire que nous pouvons parcourir à la fois vers l’avant et vers l’arrière. La mise en œuvre de ce type de liste peut être illustrée ainsi :

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

class DoubleCircularLinkedList:
    def__init__(self):
       self.head = None

    def add(self, data):
        new_node = Node(data)
        if self.head is None:
            new_node.next = new_node
            new_node.prev = new_node
            self.head = new_node
        else:
            last_node = self.head.prev
            last_node.next = new_node
            new_node.prev = last_node
            new_node.next = self.head
            self.head.prev = new_node

     def remove(self,data):
         if self.head is None:
             return

         current_node = self.head
         while current_node.data != data:
             current_node = current_node.next
             if current_node == self.head:
                 return

             if current_node == self.head:
                 self.head = current_node.next

             current_node.prev.next = current_node.next
             current_node.next.prev = current_node.prev

      def display(self):
          if self.head is None:
              return

          current_node = self.head
          while True:
              print(current_node.data)
              current_node = current_node.next
              if current_node == self.head:
                  break

my_list = DoubleCircularLinkedList()

my_list.add(1)
my_list.add(2)
my_list.add(3)

my_list.display()

Explication

La principale différence entre une liste liée circulaire double et une liste liée circulaire standard est que, comme auparavant avec la liste liée non circulaire, la liste double pointe chaque nœud vers le nœud précédent ainsi que vers le nœud suivant. Ceci est réalisé en mettant à jour les attributs « prev » et « next » du dernier nœud et du nouveau nœud lors de l’ajout d’un nœud. Lors de la suppression d’un nœud, ces attributs du nœud supprimé et des nœuds adjacents doivent être mis à jour. Si vous supprimez le nœud principal, les pointeurs du dernier nœud doivent être mis à jour pour refléter cela.

Emballer

De nombreux types de listes liées peuvent être utilisés comme alternative aux tableaux, par exemple lorsque vous devez insérer et supprimer des éléments régulièrement ou que vous avez des contraintes de mémoire. Bien que les tableaux fonctionnent plus rapidement lorsqu’il s’agit de certaines opérations, les listes chaînées ne sont pas sans avantages uniques, il est donc utile de comprendre leur fonctionnement.

Suivant…

FAQ sur la structure des données de la liste chaînée et son utilisation (Foire aux questions)

Qu’est-ce qu’une liste chaînée ?

Une liste chaînée est une structure de données où les données sont stockées dans des « nœuds », et non de manière contiguë, comme avec un tableau. Ils peuvent être simples ou circulaires, ce dernier impliquant le dernier nœud pointant vers le nœud principal. Vous pouvez également implémenter des listes à double liaison, où la traversée peut se produire en avant et en arrière dans la liste.

Quels sont les avantages et les inconvénients des listes chaînées ?

Les listes chaînées peuvent être meilleures que les tableaux lorsque vous devez insérer et supprimer fréquemment des données ou que vous avez des contraintes de mémoire. Cependant, un tableau peut être préférable lorsque vous devez utiliser la recherche binaire et, comme ils sont contigus, ils sont plus compatibles avec le cache. Bien que l’insertion d’éléments soit plus rapide, l’accès à un élément particulier peut être plus lent car vous devez parcourir toute la liste.

Quels sont les différents types de listes chaînées ?

Les types de listes chaînées comprennent les listes chaînées simples et doublement chaînées, et les listes chaînées circulaires et doublement circulaires.

Comment insérer ou supprimer un nœud d’une liste chaînée ?

Pour insérer un nœud, il faut créer le nouveau nœud et faire pointer l’attribut « suivant » de ce nœud vers le nœud suivant de la liste, ainsi que pointer l’attribut « suivant » du nœud précédent vers ce nouveau nœud. Pour supprimer un nœud, vous devez parcourir la liste pour trouver les données données. Ensuite, vous devez pointer l’attribut « suivant » du nœud précédent vers le nœud devant le nœud que vous souhaitez supprimer, afin qu’il soit ignoré dans la liste.

Comment parcourez-vous une liste chaînée ?

Pour parcourir la liste, vous commencez par le nœud principal et passez à chaque nœud de la séquence jusqu’à ce que vous atteigniez le nœud final.

Quelle est la complexité temporelle des opérations de liste chaînée ?

Chaque opération a sa propre complexité temporelle. Les opérations avec une complexité temporelle de O(1) incluent l’insertion d’un élément au début et la suppression d’un élément au début. La plupart des autres opérations ont une complexité de O(n). Cela comprend l’accès à un élément, l’insertion ou la suppression d’un élément à la fin, l’insertion ou la suppression d’un élément à un index spécifique et la recherche d’un élément particulier. En effet, la liste doit être parcourue, la complexité dépend donc de la taille de la liste.

Quelles sont les alternatives aux listes chaînées ?

Au lieu d’une liste chaînée, vous pouvez utiliser un tableau, où les données sont stockées dans un bloc contigu. Les tables de hachage sont utilisées pour mapper les clés aux indices dans un tableau, de sorte qu’elles puissent être utilisées conjointement les unes avec les autres. Ou, vous pouvez utiliser un arbre, où les nœuds sont connectés dans un format hiérarchique. Les tas sont un type d’arbre binaire et constituent une autre option. Enfin, les piles et les files d’attente peuvent être utilisées avec des tableaux ou des listes liées et, bien qu’elles ne soient pas aussi flexibles que certaines options, elles offrent une modification efficace des éléments.

Quelles sont certaines applications des listes chaînées ?

Les listes liées sont utiles lorsque vous ne connaissez pas la taille de la liste, souhaitez implémenter d’autres structures de données, dans le traitement d’images et de musique et pour représenter des graphiques et des arbres.