Inverser une liste chaînée

Inverser une liste chaînée est un problème intéressant en structure de données et en algorithmes. Dans ce tutoriel, nous discuterons des différents algorithmes pour inverser une Liste Chaînée puis les mettrons en œuvre en utilisant Java.

Inverser une Liste Chaînée

LinkedList est une structure de données qui stocke les données de manière linéaire. Bien que pas de manière contiguë. Chaque élément d’une LinkedList contient une partie de données et une adresse vers l’élément suivant de la LinkedList. Les éléments de LinkedList sont communément appelés des nœuds.

Les LinkedLists doubles stockent deux adresses. L’adresse de l’élément précédent et de l’élément suivant.

Pour inverser une LinkedList sur place, nous devons inverser les pointeurs de sorte que l’élément suivant pointe désormais vers l’élément précédent. Voici l’entrée et la sortie.

La tête de la LinkedList est le premier nœud. Aucun autre élément n’a l’adresse stockée pour cela. La queue de la LinkedList est le dernier nœud. L’adresse suivante stockée dans ce nœud est `null`. Nous pouvons inverser une LinkedList de telle sorte que la tête et la queue changent également en utilisant:

• Approche itérative
• Approche récursive

Approche itérative pour inverser une liste chaînée

Pour inverser une LinkedList de manière itérative, nous devons stocker les références des éléments suivants et précédents, afin qu’elles ne soient pas perdues lorsque nous échangeons les pointeurs d’adresse mémoire vers l’élément suivant dans la LinkedList. L’illustration suivante montre comment nous allons inverser notre LinkedList en modifiant les références.

Voici les étapes à suivre pour inverser une LinkedList. Créez 3 instances : current, next, previous. Bouclez jusqu’à ce que current ne soit PAS nul :

• Enregistrez le nœud suivant de l’élément courant dans le pointeur next.
• Définissez le next du nœud current sur le previous. C’est la ligne MVP.
• Déplacez previous vers current.
• Déplacez l’élément courant vers next.

À la fin, puisque current a avancé d’une place par rapport au dernier élément, nous devons définir la tête sur le dernier élément atteint. Cela est disponible dans previous. Définissez la tête sur previous. Ainsi, nous avons notre nouvelle tête de LinkedList qui est le dernier élément de l’ancienne LinkedList.

Voici une implémentation très simple de LinkedList. Notez que ce n’est pas une implémentation prête pour la production et nous l’avons gardée simple pour que notre attention reste sur l’algorithme pour inverser la liste liée.

package com.journaldev.linkedlist.reverse;

public class MyLinkedList {

	public Node head;

	public static class Node {

		Node next;

		Object data;

		Node(Object data) {
			this.data = data;
			next = null;
		}
	}
}

Le programme Java pour inverser une liste chaînée de manière itérative et afficher ses éléments est donné ci-dessous :

package com.journaldev.linkedlist.reverse;

import com.journaldev.linkedlist.reverse.MyLinkedList.Node;

public class ReverseLinkedList {

	public static void main(String[] args) {
		MyLinkedList myLinkedList = new MyLinkedList();
		myLinkedList.head = new Node(1);
		myLinkedList.head.next = new Node(2);
		myLinkedList.head.next.next = new Node(3);

		printLinkedList(myLinkedList);
		reverseLinkedList(myLinkedList);
		printLinkedList(myLinkedList);

	}

	public static void printLinkedList(MyLinkedList linkedList) {
		Node h = linkedList.head;
		while (linkedList.head != null) {
			System.out.print(linkedList.head.data + " ");
			linkedList.head = linkedList.head.next;
		}
		System.out.println();
		linkedList.head = h;
	}

	public static void reverseLinkedList(MyLinkedList linkedList) {
		Node previous = null;
		Node current = linkedList.head;
		Node next;
		while (current != null) {
			next = current.next;
			current.next = previous;
			previous = current;
			current = next;
		}
		linkedList.head = previous;
	}

}

Sortie :

1 2 3 
3 2 1 

Inverser une liste chaînée récursivement

Pour inverser une liste chaînée de manière récursive, nous devons diviser la liste en deux parties : tête et reste. La tête pointe vers le premier élément initialement. Le reste pointe vers l’élément suivant à partir de la tête.

Nous parcourons récursivement la liste chaînée jusqu’à l’avant-dernier élément. Une fois que nous avons atteint le dernier élément, nous le définissons comme tête. À partir de là, nous faisons ce qui suit jusqu’à ce que nous atteignions le début de la liste chaînée. node.next.next = node; node.next = null; Pour ne pas perdre la trace de la tête originale, nous sauvegardons une copie de l’instance de tête.

Voici l’illustration de la procédure ci-dessus. Le programme Java pour inverser une liste chaînée de manière récursive est :

public static Node recursiveReverse(Node head) {
	Node first;

	if (head==null || head.next == null)
		return head;

	first = recursiveReverse(head.next);
	head.next.next = head;
	head.next = null;

	return first;
}

Nous passons simplement head.next dans l’appel récursif afin d’aller à la fin de la liste chaînée. Une fois que nous atteignons la fin, nous définissons l’avant-dernier élément comme le suivant du dernier élément et nous définissons le pointeur suivant de l’avant-dernier élément sur NULL. Le dernier élément sera marqué comme la nouvelle tête. Utilisez le code suivant pour inverser la liste chaînée en utilisant l’approche récursive.

myLinkedList.head = recursiveReverse(myLinkedList.head);

La sortie restera la même que l’approche itérative précédente.

Complexité Temporelle et Spatiale de l’Inversion d’une Liste Chaînée

Complexité Temporelle – O(n) Complexité Spatiale – O(1)

Vous pouvez consulter le code complet et plus d’exemples de structures de données et d’algorithmes sur notre Dépôt GitHub.