Inversione di un elenco collegato in Java

1. Introduzione

In questo tutorial, implementeremo due algoritmi di inversione di elenchi collegati in Java.

2. Struttura dei dati dell'elenco collegato

Un elenco collegato è una struttura dati lineare in cui un puntatore in ogni elemento determina l'ordine. Ogni elemento di un elenco collegato contiene un campo dati per memorizzare i dati dell'elenco e un campo puntatore per puntare all'elemento successivo nella sequenza. Inoltre, possiamo usare un puntatore a testa per puntare all'elemento iniziale di un elenco collegato:

Dopo aver invertito l'elenco collegato, la testa punterà all'ultimo elemento dell'elenco collegato originale e il puntatore di ogni elemento punterà all'elemento precedente dell'elenco collegato originale:

In Java, abbiamo una classe LinkedList per fornire un'implementazione di elenchi a doppio collegamento delle interfacce List e Deque . Tuttavia, in questo tutorial utilizzeremo una struttura di dati di elenco a collegamento singolo generale.

Iniziamo prima con una classe ListNode per rappresentare un elemento di un elenco collegato:

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 ha due campi:

  • Un valore intero per rappresentare i dati dell'elemento
  • Un puntatore / riferimento all'elemento successivo

Un elenco collegato può contenere più oggetti ListNode . Ad esempio, possiamo costruire l'elenco collegato di esempio sopra con un ciclo:

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. Implementazione dell'algoritmo iterativo

Implementiamo l'algoritmo iterativo in 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; }

In questo algoritmo iterativo, utilizziamo due variabili ListNode , precedente e corrente , per rappresentare due elementi adiacenti nell'elenco collegato. Per ogni iterazione, invertiamo questi due elementi e quindi passiamo ai due elementi successivi.

Alla fine, il puntatore corrente sarà nullo e il puntatore precedente sarà l'ultimo elemento del vecchio elenco collegato. Pertanto, il precedente è anche il nuovo puntatore a testa della lista collegata invertita e lo restituiamo dal metodo.

Possiamo verificare questa implementazione iterativa con un semplice unit test:

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

In questo unit test, costruiamo prima un elenco collegato di esempio con cinque nodi. Inoltre, verifichiamo che ogni nodo nell'elenco collegato contenga il valore di dati corretto. Quindi, chiamiamo la funzione iterativa per invertire l'elenco collegato. Infine, controlliamo l'elenco collegato invertito per assicurarci che i dati siano invertiti come previsto.

4. Implementazione dell'algoritmo ricorsivo

Ora implementiamo l'algoritmo ricorsivo in 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; }

Nella funzione reverseListRecursive , visitiamo ricorsivamente ogni elemento nell'elenco collegato fino a raggiungere l'ultimo. Quest'ultimo elemento diventerà il nuovo capo della lista collegata invertita. Inoltre, aggiungiamo l'elemento visitato alla fine dell'elenco collegato parzialmente invertito.

Allo stesso modo, possiamo verificare questa implementazione ricorsiva con un semplice unit test:

@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. conclusione

In questo tutorial, abbiamo implementato due algoritmi per invertire un elenco collegato. Come sempre, il codice sorgente dell'articolo è disponibile su GitHub.