Trova l'elemento centrale di un elenco collegato in Java

1. Panoramica

In questo tutorial, spiegheremo come trovare l'elemento centrale di un elenco collegato in Java.

Introdurremo i problemi principali nelle prossime sezioni e mostreremo diversi approcci per risolverli.

2. Tenere traccia delle dimensioni

Questo problema può essere facilmente risolto semplicemente tenendo traccia delle dimensioni quando aggiungiamo nuovi elementi all'elenco . Se conosciamo la dimensione, sappiamo anche dove si trova l'elemento centrale, quindi la soluzione è banale.

Vediamo un esempio utilizzando l'implementazione Java di una LinkedList :

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

Se controlliamo il codice interno della classe LinkedList , possiamo vedere che in questo esempio stiamo solo attraversando l'elenco fino a raggiungere l'elemento centrale:

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. Trovare il centro senza conoscere la dimensione

È molto comune che incontriamo problemi in cui abbiamo solo il nodo principale di un elenco collegato e dobbiamo trovare l'elemento centrale. In questo caso, non conosciamo la dimensione dell'elenco, il che rende questo problema più difficile da risolvere.

Mostreremo nelle prossime sezioni diversi approcci per risolvere questo problema, ma prima dobbiamo creare una classe per rappresentare un nodo della lista.

Creiamo una classe Node , che memorizza i valori 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; } }

Inoltre, utilizzeremo questo metodo di supporto nei nostri casi di test per creare un elenco collegato singolarmente utilizzando solo i nostri nodi:

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. Trovare prima la taglia

L'approccio più semplice per affrontare questo problema è trovare prima la dimensione dell'elenco, quindi seguire lo stesso approccio che abbiamo utilizzato prima: iterare fino all'elemento centrale.

Vediamo questa soluzione in azione:

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()); }

Come possiamo vedere, questo codice scorre l'elenco due volte. Pertanto, questa soluzione ha prestazioni scadenti e non è consigliata .

3.2. Trovare l'elemento centrale in un passaggio in modo iterativo

Miglioreremo ora la soluzione precedente trovando l'elemento centrale con una sola iterazione nell'elenco.

Per farlo in modo iterativo, abbiamo bisogno di due puntatori per scorrere l'elenco contemporaneamente. Un puntatore avanzerà di 2 nodi in ciascuna iterazione e l'altro puntatore avanzerà di un solo nodo per iterazione .

Quando il puntatore più veloce raggiunge la fine dell'elenco, il puntatore più lento si troverà al centro:

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()); }

Possiamo testare questa soluzione con un semplice test unitario utilizzando elenchi con numero pari e dispari di elementi:

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

3.3. Trovare l'elemento centrale in un passaggio ricorsivamente

Un altro modo per risolvere questo problema in un passaggio è usare la ricorsione. Possiamo iterare fino alla fine della lista per conoscere la dimensione e, nei callback, contiamo solo fino alla metà della dimensione.

Per fare ciò in Java, creeremo una classe ausiliaria per mantenere i riferimenti della dimensione della lista e dell'elemento centrale durante l'esecuzione di tutte le chiamate ricorsive:

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

Ora implementiamo il metodo ricorsivo:

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--; }

E infine, creiamo un metodo che chiami quello ricorsivo:

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()); }

Di nuovo, possiamo testarlo nello stesso modo in cui abbiamo fatto prima:

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

4. Conclusione

In questo articolo, abbiamo introdotto il problema di trovare l'elemento centrale di un elenco collegato in Java e abbiamo mostrato diversi modi per risolverlo.

Siamo partiti dall'approccio più semplice in cui tenevamo traccia delle dimensioni e, successivamente, abbiamo continuato con le soluzioni per trovare l'elemento centrale dal nodo principale dell'elenco.

Come sempre, il codice sorgente completo degli esempi è disponibile su GitHub.