Comment inverser une liste chaînée, avec des exemples

Il existe de nombreuses applications pour les listes chaînées, telles que le traitement de la musique et des images et la représentation de graphiques, d’arbres et de structures de données plus élaborées. Mais pourquoi voudriez-vous inverser une liste chaînée ? Allons-y.

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

Comme vous pouvez probablement le deviner, c’est une liste chaînée qui a… été inversée ! Normalement, chaque nœud pointe vers le nœud suivant dans une liste, en commençant par le nœud principal et en terminant par le nœud final. Mais, lorsque vous inversez une liste chaînée, les pointeurs sont inversés, de sorte que la tête devient la queue et la queue devient la tête. Considérons le cas simple d’une liste à 5 nœuds. Cela ressemblerait normalement à ceci :

tête → nœud1 → nœud2 → nœud3 → nœud4 → nœud5 → queue

une fois la liste inversée, on obtient :

queue → nœud5 → nœud4 → nœud3 → nœud2 → nœud1 → tête

Même si la liste s’allonge et implique plus de valeurs de données, le principe reste le même.

Pourquoi voudriez-vous inverser une liste chaînée ?

Puisqu’une liste chaînée inversée est toujours une liste chaînée, par essence, beaucoup d’applications sont similaires. En tant que telles, les listes inversées sont toujours utilisées pour implémenter d’autres structures de données, dans des piles et dans des files d’attente. Mais, il y a quelques utilisations uniques que les listes chaînées inverses apportent à la table :

• Puisque les éléments sont inversés, nous pouvons imprimer les éléments et traiter la liste dans l’ordre inverse. Ceci est utile si vous souhaitez afficher l’historique Internet d’un navigateur.
• Si vous souhaitez supprimer certains éléments vers la fin de la liste, l’inverser facilite grandement la tâche. C’est parce que ces éléments sont maintenant au début de la liste. Cela peut faire gagner beaucoup de temps, surtout si la liste est importante. Vous n’avez pas besoin de parcourir toute la liste si vous inversez la liste.
• Parfois, nous voulons effectuer un algorithme récursif sur une liste entière, en exécutant des opérations à chaque nœud. Dans certains de ces cas, les traiter dans l’ordre inverse peut avoir plus de sens.
• Une autre raison d’utiliser une liste chaînée inversée est de vérifier si la liste est palindromique – cela signifie que la séquence est la même vers l’avant ou vers l’arrière. Un exemple de ceci serait le nombre 212. Quelle que soit la façon dont vous le regardez, la séquence de valeurs de données est identique.

Comment inverser une liste chaînée

Il existe généralement deux approches pour inverser une liste chaînée – l’approche itérative et l’approche récursive. Jetons un coup d’œil à ceux-ci.

L’approche itérative

Dans cette méthode, nous répétons l’exécution de l’algorithme jusqu’à ce que chaque pointeur ait été inversé. Pour ce faire, nous suivons nos nœuds à l’aide des attributs « prev », « curr » et « next ». Nous pouvons les attribuer comme tels :

while (current != NULL)
{
next = current -> next
current -> next = prev
prev = current
current = next 
}
head_ref = prev

L’instruction « while » itère essentiellement sur chaque nœud qui n’est pas nul.

La ligne suivante garde la trace du nœud suivant dans la liste, donc nous ne le perdons pas une fois que nous avons inversé les pointeurs.

Ensuite, nous définissons l’attribut « suivant » du nœud actuel sur le nœud précédent, en inversant les pointeurs.

La ligne suivante définit l’attribut « prev » sur le nœud précédent, en gardant une trace comme nous l’avons fait pour le nœud suivant.

L’avant-dernière ligne indique que le pointeur « actuel » se trouve sur le nœud suivant, nous pouvons donc nous déplacer de manière itérative le long de la liste.

Enfin, nous définissons le pointeur « head_ref » sur le dernier nœud de la liste d’origine, qui sera le premier nœud de la liste inversée. Par conséquent, nous le définissons comme le nouveau nœud principal.

Voici comment nous pouvons implémenter ce processus en Python :

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

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

    def push(self, new_data):
      new_node = Node(new_data)
      new_node.next = self.head
      self.head = new_node

    def reverse(self):
      prev_node = None
      current_node = self.head
      while current_node is not None:
          next_node = current_node.next
          current_node.next = prev_node
          prev_node = current_node
          current_node = next_node
      self.head = prev_node

    def printList(self):
       current_node = self.head
       while current_node:
          print(current_node.data, end=" ")
          current_node = current_node.next

my_list = LinkedList()
my_list.push(16)
my_list.push(2)
my_list.push(19)
my_list.push(71)

print("Given linked list")
my_list.printList()
my_list.reverse()
print("nReversed linked list")
my_list.printList()

Tout d’abord, nous définissons les classes « Node » et « LinkedList ». Ensuite, nous définissons la fonction « push », qui permet d’ajouter un nouveau nœud au début de la liste, qui est désigné comme nœud principal.

Ensuite, nous voyons la fonction « inverser » implémentée à peu près de la même manière que celle décrite précédemment.

Enfin, nous définissons la fonction « printList » pour la classe « LinkedList », qui imprime la valeur des données à chaque nœud, qui continue jusqu’à ce que le « current_node » soit égal à « None », indiquant que nous avons atteint la fin de la liste. Voir la capture d’écran pour savoir comment cela fonctionne en Python.

L’approche récursive

L’autre méthode pour inverser une liste chaînée est l’approche récursive. Alors que les approches itératives fonctionnent en utilisant des boucles ou des instructions répétitives pour résoudre un problème, les approches récursives exécutent la même fonction sur des exemples de plus en plus petits du même problème. Une fois ces sous-problèmes résolus, les solutions sont combinées pour donner un résultat global au problème initial. Voyons comment fonctionne la récursivité pour inverser une liste chaînée :

Tout d’abord, nous divisons la liste en deux parties, le premier nœud et la liste restante.

Ensuite, nous appelons la fonction « inverser » pour la liste restante.

Cette liste inversée est ensuite liée au premier nœud et le pointeur de tête d’origine est défini sur NULL. Le nouveau pointeur principal est défini sur le nouveau nœud principal et la liste est inversée.

Voici un aperçu de la façon dont cela est implémenté :

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

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

   def push(self, new_data):
     new_node = Node(new_data)
     new_node.next = self.head
     self.head = new_node

   def reverse_recursive(self, current_node):
     if current_node is None or current_node.next is None:
        return current_node

     rest = self.reverse_recursive(current_node.next)

     current_node.next.next = current_node
     current_node.next = None

     return rest

   def reverse(self):
     self.head = self.reverse_recursive(self.head)

   def printList(self):
     current_node = self.head
     while current_node:
       print(current_node.data, end =" ")
       current_node = current_node.next
     print()

my_list = LinkedList()
my_list.push(16)
my_list.push(2)
my_list.push(19)
my_list.push(71)

print("Given linked list")
my_list.printList()

my_list.reverse()
print("Reversed linked list (recursive):")
my_list.printList()

Une grande partie de ce code est identique au processus itératif. La principale différence réside, sans surprise, dans la fonction inverse utilisée.

Dans ce cas, nous définissons la fonction « reverse_recursive » en fonction du nœud courant. Chaque nœud après celui-ci est inversé de manière récursive en appelant la fonction inverse avec le nœud suivant en entrée jusqu’à ce que le nœud actuel soit égal à « Aucun ». Cela se produit lorsque la fin de la liste est atteinte, ou dans le cas simple où il n’y a qu’un seul nœud dans la liste.

Ensuite, le nœud courant est inversé en mettant à jour l’attribut « suivant » du nœud suivant vers le nœud courant, et l’attribut « suivant » du nœud courant vers « Aucun ». Le nœud courant devient la queue de la liste inversée.

Emballer

Lorsque vous devez inverser une liste chaînée, vous pouvez choisir entre une approche itérative et une approche récursive. Alors que les approches itératives reposent sur la répétition des mêmes instructions dans une boucle « while » pour chaque nœud, les fonctions récursives exécutent leur fonction sur des instances plus petites du même problème. Inverser une liste chaînée peut être utile pour détecter la palindromicité d’une liste et modifier les éléments à la fin de la liste d’origine.

Comment inverser une liste chaînée, avec des exemples FAQ (Foire aux questions)

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

Une liste chaînée inversée est une liste chaînée dont l’ordre de ses éléments a été inversé, de sorte que le dernier nœud devient le premier nœud de la nouvelle liste et que les pointeurs sont inversés.

Pourquoi voudriez-vous inverser une liste chaînée ?

L’inversion d’une liste peut être utile pour déterminer si une liste est palindromique, modifier des éléments à la fin de la liste d’origine (comme ils sont maintenant au début), ou lorsque vous souhaitez utiliser certains algorithmes qu’il est préférable d’utiliser avec une liste inversée. liste.

Comment inverser une liste chaînée ?

Les moyens les plus courants d’inverser une liste liée sont les fonctions itératives ou récursives. Là où l’approche itérative fonctionne en parcourant la liste et en modifiant les pointeurs de chaque nœud, la fonction inverse récursive fonctionne en inversant la liste en dehors du nœud principal, puis en mettant à jour les pointeurs du nœud actuel.

Comment inverser les listes doublement liées et les listes circulaires liées ?

Vous pouvez inverser une liste à double liaison de la même manière qu’une liste à liaison simple, mais vous devez mettre à jour les attributs « next » et « prev » de chaque nœud en conséquence. Pour les listes chaînées circulaires, vous devez mettre à jour l’attribut « next » du nœud de queue pour qu’il pointe vers le nouveau nœud de tête.

Quelle est la complexité temporelle de l’inversion d’une liste chaînée ?

La complexité temporelle est égale à O(n), où n est le nombre de nœuds, car vous devez parcourir la liste pour inverser les pointeurs quelle que soit la méthode que vous utilisez.

Quelle est la complexité spatiale de l’inversion d’une liste chaînée ?

La complexité spatiale est égale à O(1) en ce qui concerne l’approche itérative, puisque les variables temporaires dont vous avez besoin pour inverser la liste restent constantes. Pour l’approche récursive, la complexité spatiale est égale à O(n), puisque vous devez stocker chaque appel de la fonction récursive dans une pile.