Een gekoppelde lijst omkeren in Java

1. Inleiding

In deze zelfstudie implementeren we twee omkeeralgoritmen voor gekoppelde lijsten in Java.

2. Gegevensstructuur gekoppelde lijst

Een gekoppelde lijst is een lineaire datastructuur waarin een aanwijzer in elk element de volgorde bepaalt. Elk element van een gekoppelde lijst bevat een gegevensveld om de lijstgegevens op te slaan en een aanwijzerveld om naar het volgende element in de reeks te verwijzen. We kunnen ook een hoofd aanwijzer om naar het startelement van een gekoppelde lijst te wijzen:

Nadat we de gekoppelde lijst hebben omgedraaid, wordt de hoofd zal naar het laatste element van de originele gelinkte lijst wijzen, en de pointer van elk element zal naar het vorige element van de originele gelinkte lijst wijzen:

In Java hebben we een LinkedList class om een ​​dubbelgekoppelde lijstimplementatie van de Lijst en Deque interfaces. In deze zelfstudie gebruiken we echter een algemene enkelvoudig gekoppelde lijstgegevensstructuur.

Laten we beginnen met een ListNode class om een ​​element van een gekoppelde lijst te vertegenwoordigen:

openbare klasse ListNode {privé int-gegevens; privé ListNode volgende; ListNode (int data) {this.data = data; this.next = null; } // standaard getters en setters}

De ListNode klasse heeft twee velden:

  • Een geheel getal om de gegevens van het element weer te geven
  • Een aanwijzer / verwijzing naar het volgende element

Een gekoppelde lijst kan meerdere bevatten ListNode voorwerpen. We kunnen bijvoorbeeld de bovenstaande voorbeeldgekoppelde lijst samenstellen met een lus:

ListNode constructLinkedList () {ListNode head = null; ListNode tail = null; voor (int i = 1; i <= 5; i ++) {ListNode node = nieuwe ListNode (i); if (head == null) {head = node; } else {tail.setNext (knooppunt); } tail = node; } terugkeer hoofd; }

3. Implementatie van iteratief algoritme

Laten we het iteratieve algoritme in Java implementeren:

ListNode reverseList (ListNode-kop) {ListNode previous = null; ListNode current = head; while (current! = null) {ListNode nextElement = current.getNext (); current.setNext (vorige); vorige = huidig; current = nextElement; } terugkeer vorige; }

In dit iteratieve algoritme gebruiken we er twee ListNode variabelen, vorige en actueel, om twee aangrenzende elementen in de gekoppelde lijst weer te geven. Voor elke iteratie keren we deze twee elementen om en gaan we vervolgens naar de volgende twee elementen.

Uiteindelijk is het actueel wijzer zal zijn nul, en de vorige pointer is het laatste element van de oude gekoppelde lijst. Daarom vorige is ook de nieuwe hoofdaanwijzer van de omgekeerde gekoppelde lijst, en we retourneren deze van de methode.

We kunnen deze iteratieve implementatie verifiëren met een eenvoudige unit-test:

@Test openbare ongeldig gegevenLinkedList_whenIterativeReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); ListNode-knooppunt = hoofd; voor (int i = 1; i <= 5; i ++) {assertNotNull (knooppunt); assertEquals (i, node.getData ()); knooppunt = knooppunt.getNext (); } LinkedListReversal reversal = nieuwe LinkedListReversal (); knooppunt = reversal.reverseList (hoofd); voor (int i = 5; i> = 1; i--) {assertNotNull (knooppunt); assertEquals (i, node.getData ()); knooppunt = knooppunt.getNext (); }}

In deze unit-test construeren we eerst een voorbeeld van een gekoppelde lijst met vijf knooppunten. We controleren ook of elk knooppunt in de gekoppelde lijst de juiste gegevenswaarde bevat. Vervolgens noemen we de iteratieve functie om de gekoppelde lijst om te keren. Ten slotte controleren we de omgekeerde gekoppelde lijst om er zeker van te zijn dat de gegevens worden omgekeerd zoals verwacht.

4. Recursief Implementatie van algoritme

Laten we nu het recursieve algoritme in Java implementeren:

ListNode reverseListRecursive (ListNode head) {if (head == null) {return null; } if (head.getNext () == null) {return head; } ListNode-knooppunt = reverseListRecursive (head.getNext ()); head.getNext (). setNext (head); head.setNext (null); terugkeerknooppunt; }

In de reverseListRecursive functie, bezoeken we elk element in de gekoppelde lijst recursief totdat we het laatste bereiken. Dit laatste element wordt de nieuwe kop van de omgekeerde gekoppelde lijst. Ook voegen we het bezochte element toe aan het einde van de gedeeltelijk omgekeerde gekoppelde lijst.

Evenzo kunnen we deze recursieve implementatie verifiëren met een eenvoudige unit-test:

@Test openbare leegte gegevenLinkedList_whenRecursiveReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); ListNode-knooppunt = hoofd; voor (int i = 1; i <= 5; i ++) {assertNotNull (knooppunt); assertEquals (i, node.getData ()); knooppunt = knooppunt.getNext (); } LinkedListReversal reversal = nieuwe LinkedListReversal (); knooppunt = reversal.reverseListRecursive (hoofd); voor (int i = 5; i> = 1; i--) {assertNotNull (knooppunt); assertEquals (i, node.getData ()); knooppunt = knooppunt.getNext (); }}

5. Conclusie

In deze tutorial hebben we twee algoritmen geïmplementeerd om een ​​gekoppelde lijst om te keren. Zoals altijd is de broncode voor het artikel beschikbaar op GitHub.