Inverser une liste chaînée en Python

Une liste chaînée est une structure de données linéaire en informatique qui permet d’ajouter et de supprimer des éléments en temps constant. Il est composé de nœuds.

Un nœud unique stocke certaines données et l’adresse du nœud suivant. Le nœud suivant stocke ses données et l’adresse du nœud suivant. Un seul nœud ne connaît que le nœud vers lequel il pointe. Il n’a aucune information sur les nœuds qui pointent vers lui.

Cette structure nous permet d’ajouter de nouveaux nœuds et de supprimer des nœuds existants en temps constant, étant donné le nœud qui le précède, contrairement aux tableaux, où nous devons copier un tableau dans un nouveau tableau ou déplacer les éléments d’un tableau pour créer de la place pour l’ajout et la suppression.

Dans les tableaux, on peut accéder aux éléments en temps constant à l’aide d’index. Mais avec les listes chaînées, il faut un temps O(n) pour accéder à un élément, où n est la longueur de la liste chaînée.

Puisqu’une liste chaînée est similaire à un tableau en termes de structure (linéaire), nous pouvons également effectuer des opérations telles que le tri, le filtrage et la recherche dans des listes chaînées. Nous pouvons utiliser des algorithmes de tri et de recherche tels que le tri à bulles, le tri par insertion, le tri par fusion, le tri rapide, le tri par sélection, la recherche binaire et la recherche linéaire sur des listes chaînées.

Cet article montrera comment inverser une liste chaînée à l’aide de Python. Notez que l’extrait de code considère une classe Node représentant un bloc d’une liste chaînée.

La classe Node doit se présenter comme suit.

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

Inverser une liste chaînée en Python

Reportez-vous au code Python suivant pour inverser une liste chaînée en Python.

def reverse(head: Node) -> Node:
    previous = None
    current = head
    next = None

    while current is not None:
        next = current.next
        current.next = previous
        previous = current
        current = next

    head = previous
    return head

Pour comprendre le code, considérons un exemple de liste chaînée, 1 -> 2 -> 3 -> 4 -> 5 -> None.

Tout d’abord, nous déclarons trois variables, previous, current et next, qui pointent vers None, la tête de la liste chaînée d’entrée, et None, respectivement. Ensuite, nous déclarons une boucle while qui se termine lorsque le nœud current pointe sur None.

Pour chaque itération :

• On stocke le nœud suivant du nœud current dans le nœud next.
• Définissez le nœud suivant du nœud current sur le nœud previous.
• Réinitialiser le nœud previous au nœud current.
• Réinitialiser le nœud current au nœud next.

Le tableau suivant représente comment les valeurs des variables, à savoir previous, current et next, changent lorsque l’algorithme est appliqué pour l’exemple ci-dessus.

Les cellules du tableau ci-dessus affichent la valeur stockée par un nœud.