Inverser une liste liée en Java

1. Introduction

Dans ce didacticiel, nous allons implémenter deux algorithmes d'inversion de liste chaînée en Java.

2. Structure des données de la liste liée

Une liste chaînée est une structure de données linéaire dans laquelle un pointeur dans chaque élément détermine l'ordre. Chaque élément d'une liste liée contient un champ de données pour stocker les données de la liste et un champ de pointeur pour pointer vers l'élément suivant de la séquence. En outre, nous pouvons utiliser un pointeur de tête pour pointer vers l'élément de départ d'une liste liée:

Après avoir inversé la liste liée, l'en- tête pointera sur le dernier élément de la liste liée d'origine et le pointeur de chaque élément pointera vers l'élément précédent de la liste liée d'origine:

En Java, nous avons une classe LinkedList pour fournir une implémentation de liste à double lien des interfaces List et Deque . Cependant, nous utiliserons une structure générale de données de liste à lien unique dans ce didacticiel.

Commençons par une classe ListNode pour représenter un élément d'une liste liée:

public class ListNode { private int data; private ListNode next; ListNode(int data) { this.data = data; this.next = null; } // standard getters and setters }

La classe ListNode comporte deux champs:

  • Une valeur entière pour représenter les données de l'élément
  • Un pointeur / référence vers l'élément suivant

Une liste liée peut contenir plusieurs objets ListNode . Par exemple, nous pouvons construire l'exemple de liste chaînée ci-dessus avec une boucle:

ListNode constructLinkedList() { ListNode head = null; ListNode tail = null; for (int i = 1; i <= 5; i++) { ListNode node = new ListNode(i); if (head == null) { head = node; } else { tail.setNext(node); } tail = node; } return head; }

3. Implémentation d'algorithme itératif

Implémentons l'algorithme itératif en Java:

ListNode reverseList(ListNode head) { ListNode previous = null; ListNode current = head; while (current != null) { ListNode nextElement = current.getNext(); current.setNext(previous); previous = current; current = nextElement; } return previous; }

Dans cet algorithme itératif, nous utilisons deux variables ListNode , précédente et actuelle , pour représenter deux éléments adjacents dans la liste chaînée. Pour chaque itération, nous inversons ces deux éléments puis passons aux deux éléments suivants.

À la fin, le pointeur actuel sera nul et le pointeur précédent sera le dernier élément de l'ancienne liste chaînée. Par conséquent, previous est également le nouveau pointeur de tête de la liste chaînée inversée, et nous le renvoyons à partir de la méthode.

Nous pouvons vérifier cette implémentation itérative avec un simple test unitaire:

@Test public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() { ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i <= 5; i++) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseList(head); for (int i = 5; i>= 1; i--) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } }

Dans ce test unitaire, nous construisons d'abord un exemple de liste chaînée avec cinq nœuds. En outre, nous vérifions que chaque nœud de la liste liée contient la valeur de données correcte. Ensuite, nous appelons la fonction itérative pour inverser la liste chaînée. Enfin, nous vérifions la liste chaînée inversée pour nous assurer que les données sont inversées comme prévu.

4. Implémentation d'algorithme récursif

Maintenant, implémentons l'algorithme récursif en Java:

ListNode reverseListRecursive(ListNode head) { if (head == null) { return null; } if (head.getNext() == null) { return head; } ListNode node = reverseListRecursive(head.getNext()); head.getNext().setNext(head); head.setNext(null); return node; }

Dans la fonction reverseListRecursive , nous visitons récursivement chaque élément de la liste chaînée jusqu'à ce que nous atteignions le dernier. Ce dernier élément deviendra la nouvelle tête de la liste chaînée inversée. De plus, nous ajoutons l'élément visité à la fin de la liste chaînée partiellement inversée.

De même, nous pouvons vérifier cette implémentation récursive avec un simple test unitaire:

@Test public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() { ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i <= 5; i++) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseListRecursive(head); for (int i = 5; i>= 1; i--) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } }

5. Conclusion

Dans ce tutoriel, nous avons implémenté deux algorithmes pour inverser une liste chaînée. Comme toujours, le code source de l'article est disponible à l'adresse over sur GitHub.