Rechercher l'élément central d'une liste liée en Java

1. Vue d'ensemble

Dans ce tutoriel, nous allons expliquer comment trouver l'élément central d'une liste chaînée en Java.

Nous présenterons les principaux problèmes dans les sections suivantes, et nous montrerons différentes approches pour les résoudre.

2. Suivi de la taille

Ce problème peut être facilement résolu simplement en gardant une trace de la taille lorsque nous ajoutons de nouveaux éléments à la liste . Si nous connaissons la taille, nous savons également où se trouve l'élément du milieu, donc la solution est triviale.

Voyons un exemple utilisant l'implémentation Java d'une LinkedList :

public static Optional findMiddleElementLinkedList( LinkedList linkedList) { if (linkedList == null || linkedList.isEmpty()) { return Optional.empty(); } return Optional.of(linkedList.get( (linkedList.size() - 1) / 2)); }

Si nous vérifions le code interne de la classe LinkedList , nous pouvons voir que dans cet exemple, nous parcourons simplement la liste jusqu'à ce que nous atteignions l'élément du milieu:

Node node(int index) { if (index > 1)) { Node x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } }

3. Trouver le milieu sans connaître la taille

Il est très courant que nous rencontrions des problèmes où nous n'avons que le nœud principal d'une liste chaînée, et nous devons trouver l'élément du milieu. Dans ce cas, nous ne connaissons pas la taille de la liste, ce qui rend ce problème plus difficile à résoudre.

Nous montrerons dans les sections suivantes plusieurs approches pour résoudre ce problème, mais d'abord, nous devons créer une classe pour représenter un nœud de la liste.

Créons une classe Node , qui stocke les valeurs String :

public static class Node { private Node next; private String data; // constructors/getters/setters public boolean hasNext() { return next != null; } public void setNext(Node next) { this.next = next; } public String toString() { return this.data; } }

De plus, nous utiliserons cette méthode d'assistance dans nos cas de test pour créer une liste liée individuellement en utilisant uniquement nos nœuds:

private static Node createNodesList(int n) { Node head = new Node("1"); Node current = head; for (int i = 2; i <= n; i++) { Node newNode = new Node(String.valueOf(i)); current.setNext(newNode); current = newNode; } return head; }

3.1. Trouver d'abord la taille

L'approche la plus simple pour résoudre ce problème est de trouver d'abord la taille de la liste, puis de suivre la même approche que celle que nous avons utilisée auparavant: itérer jusqu'à l'élément du milieu.

Voyons cette solution en action:

public static Optional findMiddleElementFromHead(Node head) { if (head == null) { return Optional.empty(); } // calculate the size of the list Node current = head; int size = 1; while (current.hasNext()) { current = current.next(); size++; } // iterate till the middle element current = head; for (int i = 0; i < (size - 1) / 2; i++) { current = current.next(); } return Optional.of(current.data()); }

Comme nous pouvons le voir, ce code parcourt la liste deux fois. Par conséquent, cette solution a de mauvaises performances et n'est pas recommandée .

3.2. Recherche de l'élément central en une seule passe de manière itérative

Nous allons maintenant améliorer la solution précédente en trouvant l'élément du milieu avec une seule itération sur la liste.

Pour ce faire de manière itérative, nous avons besoin de deux pointeurs pour parcourir la liste en même temps. Un pointeur avancera de 2 nœuds à chaque itération, et l'autre pointeur avancera d'un seul nœud par itération .

Lorsque le pointeur le plus rapide atteint la fin de la liste, le pointeur le plus lent sera au milieu:

public static Optional findMiddleElementFromHead1PassIteratively(Node head) { if (head == null) { return Optional.empty(); } Node slowPointer = head; Node fastPointer = head; while (fastPointer.hasNext() && fastPointer.next().hasNext()) { fastPointer = fastPointer.next().next(); slowPointer = slowPointer.next(); } return Optional.ofNullable(slowPointer.data()); }

Nous pouvons tester cette solution avec un simple test unitaire en utilisant des listes avec un nombre pair et impair d'éléments:

@Test public void whenFindingMiddleFromHead1PassIteratively_thenMiddleFound() { assertEquals("3", MiddleElementLookup .findMiddleElementFromHead1PassIteratively( createNodesList(5)).get()); assertEquals("2", MiddleElementLookup .findMiddleElementFromHead1PassIteratively( reateNodesList(4)).get()); }

3.3. Recherche récursive de l'élément central en un seul passage

Une autre façon de résoudre ce problème en une seule passe consiste à utiliser la récursivité. Nous pouvons itérer jusqu'à la fin de la liste pour connaître la taille et, dans les rappels, nous comptons juste jusqu'à la moitié de la taille.

Pour ce faire en Java, nous allons créer une classe auxiliaire pour conserver les références de la taille de la liste et de l'élément du milieu lors de l'exécution de tous les appels récursifs:

private static class MiddleAuxRecursion { Node middle; int length = 0; }

Maintenant, implémentons la méthode récursive:

private static void findMiddleRecursively( Node node, MiddleAuxRecursion middleAux) { if (node == null) { // reached the end middleAux.length = middleAux.length / 2; return; } middleAux.length++; findMiddleRecursively(node.next(), middleAux); if (middleAux.length == 0) { // found the middle middleAux.middle = node; } middleAux.length--; }

Et enfin, créons une méthode qui appelle la méthode récursive:

public static Optional findMiddleElementFromHead1PassRecursively(Node head) { if (head == null) { return Optional.empty(); } MiddleAuxRecursion middleAux = new MiddleAuxRecursion(); findMiddleRecursively(head, middleAux); return Optional.of(middleAux.middle.data()); }

Encore une fois, nous pouvons le tester de la même manière que nous l'avons fait auparavant:

@Test public void whenFindingMiddleFromHead1PassRecursively_thenMiddleFound() { assertEquals("3", MiddleElementLookup .findMiddleElementFromHead1PassRecursively( createNodesList(5)).get()); assertEquals("2", MiddleElementLookup .findMiddleElementFromHead1PassRecursively( createNodesList(4)).get()); }

4. Conclusion

Dans cet article, nous avons présenté le problème de la recherche de l'élément central d'une liste chaînée en Java, et nous avons montré différentes façons de le résoudre.

Nous sommes partis de l'approche la plus simple où nous avons suivi la taille, et après cela, nous avons continué avec les solutions pour trouver l'élément du milieu à partir du nœud principal de la liste.

Comme toujours, le code source complet des exemples est disponible à l'adresse over sur GitHub.