streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban két összekapcsolt lista-megfordítási algoritmust valósítunk meg a Java-ban.

2. Összekapcsolt lista adatstruktúra

A kapcsolt lista egy lineáris adatstruktúra, amelyben az egyes elemek mutatója meghatározza a sorrendet. A csatolt lista minden eleme tartalmaz egy adatmezőt a lista adatainak tárolásához, és egy mutató mezőt, amely a sorozat következő elemére mutat. Ezenkívül használhatjuk a fej mutató egy hivatkozott lista kezdő elemére mutat:

Miután megfordítottuk a linkelt listát, a fej az eredeti összekapcsolt lista utolsó elemére fog mutatni, az egyes elemek mutatója pedig az eredeti összekapcsolt lista előző elemére mutat:

A Java-ban van egy LinkedList osztály, hogy biztosítsa a kettősen összekapcsolt lista megvalósítását a Lista és Deque interfészek. Ebben az oktatóanyagban azonban általános, külön-külön összekapcsolt lista adatstruktúrát fogunk használni.

Kezdjük először a ListNode osztály egy összekapcsolt lista elemének képviseletére:

public class ListNode {private int data; privát ListNode következő; ListNode (int adatok) {this.data = adatok; this.next = null; } // szokásos mérőeszközök és beállítók}

A ListNode osztály két mezővel rendelkezik:

• Egész elem, amely az elem adatait ábrázolja
• Mutató / hivatkozás a következő elemre

Egy összekapcsolt lista többet is tartalmazhat ListNode tárgyakat. Például elkészíthetjük a fenti minta kapcsolt listát egy hurokkal:

ListNode constructLinkedList () {ListNode fej = null; ListNode tail = null; for (int i = 1; i <= 5; i ++) {ListNode csomópont = new ListNode (i); if (fej == null) {fej = csomópont; } else {tail.setNext (csomópont); } farok = csomópont; } visszatérő fej; }

3. Iteratív algoritmus megvalósítása

Vezessük be az iteratív algoritmust Java-ban:

ListNode reverseList (ListNode head) {ListNode előző = null; ListNode current = fej; while (aktuális! = null) {ListNode nextElement = current.getNext (); current.setNext (előző); előző = aktuális; jelenlegi = következőElement; } return előző; }

Ebben az iteratív algoritmusban kettőt használunk ListNode változók, előző és jelenlegi, hogy a szomszédos elem két szomszédos elemét ábrázolja. Minden iterációnál megfordítjuk ezt a két elemet, majd áttérünk a következő két elemre.

Végül a jelenlegi mutató lesz nulla, és a előző mutató lesz a régi összekapcsolt lista utolsó eleme. Ebből kifolyólag, előző a megfordított linkelt lista új fejmutatója is, és a módszerből adjuk vissza.

Ezt az iteratív megvalósítást egyszerű egységteszt segítségével ellenőrizhetjük:

@Test public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); ListNode csomópont = head; for (int i = 1; i <= 5; i ++) {assertNotNull (csomópont); assertEquals (i, csomópont.getData ()); csomópont = csomópont.getNext (); } LinkedListReversal reversal = új LinkedListReversal (); csomópont = megfordítás.reverseList (fej); for (int i = 5; i> = 1; i--) {assertNotNull (csomópont); assertEquals (i, csomópont.getData ()); csomópont = csomópont.getNext (); }}

Ebben az egységtesztben először összeállítunk egy ötmintás csatolt listát. Azt is ellenőrizzük, hogy a csatolt lista minden csomópontja tartalmazza-e a helyes adatértéket. Ezután meghívjuk az iteratív függvényt a linkelt lista megfordítására. Végül ellenőrizzük a megfordított linkelt listát, hogy megbizonyosodjunk arról, hogy az adatok a várakozásoknak megfelelően megfordultak-e.

4. Rekurzív Algoritmus megvalósítása

Most valósítsuk meg a rekurzív algoritmust Java-ban:

ListNode reverseListRecursive (ListNode head) {if (head == null) {return null; } if (head.getNext () == null) {return head; } ListNode csomópont = reverseListRecursive (head.getNext ()); head.getNext (). setNext (head); head.setNext (null); visszatér csomópont; }

Ban,-ben reverseListRecursive függvény esetén rekurzívan meglátogatjuk a csatolt lista minden elemét, amíg el nem érjük az utolsót. Ez az utolsó elem lesz a megfordított linkelt lista új feje. A meglátogatott elemet hozzáfűzzük a részben megfordított linkelt lista végéhez is.

Hasonlóképpen ellenőrizhetjük ezt a rekurzív megvalósítást egy egyszerű egységteszt segítségével:

@Test public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); ListNode csomópont = fej; for (int i = 1; i <= 5; i ++) {assertNotNull (csomópont); assertEquals (i, csomópont.getData ()); csomópont = csomópont.getNext (); } LinkedListReversal reversal = új LinkedListReversal (); csomópont = megfordítás.reverseListRecursive (fej); for (int i = 5; i> = 1; i--) {assertNotNull (csomópont); assertEquals (i, csomópont.getData ()); csomópont = csomópont.getNext (); }}

5. Következtetés

Ebben az oktatóanyagban két algoritmust valósítottunk meg a linkelt lista megfordítására. Mint mindig, a cikk forráskódja elérhető a GitHubon.