Umkehren einer verknüpften Liste in Java

1. Einleitung

In diesem Tutorial implementieren wir zwei Algorithmen zur Umkehrung verknüpfter Listen in Java.

2. Datenstruktur der verknüpften Liste

Eine verknüpfte Liste ist eine lineare Datenstruktur, in der ein Zeiger in jedem Element die Reihenfolge bestimmt. Jedes Element einer verknüpften Liste enthält ein Datenfeld zum Speichern der Listendaten und ein Zeigerfeld zum Zeigen auf das nächste Element in der Sequenz. Außerdem können wir einen verwenden Kopf Zeiger auf Punkt auf dem Startelement einer verketteten Liste:

Nachdem wir die verknüpfte Liste umgekehrt haben, zeigt der Kopf auf das letzte Element der ursprünglichen verknüpften Liste, und der Zeiger jedes Elements zeigt auf das vorherige Element der ursprünglichen verknüpften Liste:

In Java, haben wir eine LinkedList Klasse eine doppelt verknüpfte Liste Umsetzung der bereitzustellen Liste und Deque - Schnittstellen. In diesem Lernprogramm wird jedoch eine allgemeine, einfach verknüpfte Listendatenstruktur verwendet.

Beginnen wir zunächst mit einer ListNode- Klasse, um ein Element einer verknüpften Liste darzustellen:

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

Die ListNode- Klasse hat zwei Felder:

  • Ein ganzzahliger Wert zur Darstellung der Daten des Elements
  • Ein Zeiger / Verweis auf das nächste Element

Eine verknüpfte Liste kann mehrere ListNode- Objekte enthalten. Zum Beispiel können wir die obige verknüpfte Beispielliste mit einer Schleife erstellen:

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. Implementierung des iterativen Algorithmus

Lassen Sie uns den iterativen Algorithmus in Java implementieren:

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 diesem iterativen Algorithmus verwenden wir zwei ListNode- Variablen, vorherige und aktuelle , um zwei benachbarte Elemente in der verknüpften Liste darzustellen. Für jede Iteration kehren wir diese beiden Elemente um und wechseln dann zu den nächsten beiden Elementen.

Am Ende ist der aktuelle Zeiger null und der vorherige Zeiger das letzte Element der alten verknüpften Liste. Daher ist der vorherige auch der neue Kopfzeiger der umgekehrten verknüpften Liste, und wir geben ihn von der Methode zurück.

Wir können diese iterative Implementierung mit einem einfachen Komponententest überprüfen:

@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 diesem Komponententest erstellen wir zunächst eine verknüpfte Beispielliste mit fünf Knoten. Außerdem überprüfen wir, ob jeder Knoten in der verknüpften Liste den richtigen Datenwert enthält. Dann rufen wir die iterative Funktion auf, um die verknüpfte Liste umzukehren. Schließlich überprüfen wir die umgekehrte verknüpfte Liste, um sicherzustellen, dass die Daten wie erwartet umgekehrt werden.

4. Implementierung eines rekursiven Algorithmus

Lassen Sie uns nun den rekursiven Algorithmus in Java implementieren:

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

In der Funktion reverseListRecursive besuchen wir jedes Element in der verknüpften Liste rekursiv, bis wir das letzte erreichen. Dieses letzte Element wird zum neuen Kopf der umgekehrten verknüpften Liste. Außerdem hängen wir das besuchte Element an das Ende der teilweise umgekehrten verknüpften Liste an.

Ebenso können wir diese rekursive Implementierung mit einem einfachen Komponententest überprüfen:

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

In diesem Tutorial haben wir zwei Algorithmen implementiert, um eine verknüpfte Liste umzukehren. Wie immer ist der Quellcode für den Artikel auf GitHub verfügbar.