Obrátenie prepojeného zoznamu v prostredí Java

1. Úvod

V tomto tutoriále implementujeme dva spojené algoritmy obrátenia zoznamu v Jave.

2. Dátová štruktúra prepojeného zoznamu

Prepojený zoznam je lineárna dátová štruktúra, v ktorej poradie určuje každý ukazovateľ v každom prvku. Každý prvok prepojeného zoznamu obsahuje údajové pole na uloženie údajov zoznamu a pole ukazovateľa smerujúce na nasledujúci prvok v poradí. Môžeme tiež použiť a hlava ukazovateľ smerujúci na počiatočný prvok prepojeného zoznamu:

Po obrátení prepojeného zoznamu sa zobrazí ikona hlava bude ukazovať na posledný prvok pôvodného prepojeného zoznamu a ukazovateľ každého prvku bude smerovať na predchádzajúci prvok pôvodného prepojeného zoznamu:

V Jave máme a LinkedList triedy, aby poskytla implementáciu zoznamu, ktorý je dvojnásobne prepojený Zoznam a Deque rozhrania. V tomto tutoriále však použijeme všeobecnú jednotlivo prepojenú štruktúru dátových zoznamov.

Najprv začnime s ListNode trieda, ktorá predstavuje prvok prepojeného zoznamu:

public class ListNode {private int data; privátny ListNode ďalej; ListNode (int data) {this.data = data; this.next = null; } // štandardní zakladatelia a zakladatelia}

The ListNode trieda má dve polia:

  • Celé číslo, ktoré predstavuje údaje prvku
  • Ukazovateľ / odkaz na nasledujúci prvok

Prepojený zoznam môže obsahovať viac ListNode predmety. Napríklad môžeme vytvoriť vyššie uvedený zoznam prepojených odkazov pomocou slučky:

ListNode constructLinkedList () {ListNode head = null; ListNode tail = null; pre (int i = 1; i <= 5; i ++) {uzol ListNode = nový ListNode (i); if (head == null) {head = node; } else {tail.setNext (uzol); } chvost = uzol; } vratna hlavica; }

3. Implementácia iteratívneho algoritmu

Implementujme iteračný algoritmus v Jave:

ListNode reverseList (ListNode head) {ListNode previous = null; ListNode current = hlava; while (current! = null) {ListNode nextElement = current.getNext (); current.setNext (predchádzajúci); predošlý = aktuálny; current = nextElement; } návrat predchádzajúci; }

V tomto iteračnom algoritme používame dva ListNode premenné, predchádzajúci a prúd, aby predstavovali dva susedné prvky v prepojenom zozname. Pri každej iterácii tieto dva prvky obrátime a potom prejdeme na ďalšie dva prvky.

Nakoniec prúd ukazovateľ bude nulový, a predchádzajúci ukazovateľ bude posledným prvkom starého prepojeného zoznamu. Preto predchádzajúci je tiež nový hlavný ukazovateľ obráteného prepojeného zoznamu a vrátime ho z metódy.

Túto iteračnú implementáciu môžeme overiť jednoduchým testom jednotky:

@Test public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); Uzol ListNode = hlava; pre (int i = 1; i <= 5; i ++) {assertNotNull (uzol); assertEquals (i, node.getData ()); node = node.getNext (); } Zvrátenie LinkedListReversal = nový LinkedListReversal (); uzol = reversal.reverseList (hlava); for (int i = 5; i> = 1; i--) {assertNotNull (uzol); assertEquals (i, node.getData ()); node = node.getNext (); }}

V tomto teste jednotky najskôr zostavíme ukážkový prepojený zoznam s piatimi uzlami. Overíme tiež, že každý uzol v prepojenom zozname obsahuje správnu hodnotu údajov. Potom zavoláme iteračnú funkciu na obrátenie prepojeného zoznamu. Nakoniec skontrolujeme obrátený prepojený zoznam, aby sme sa ubezpečili, že údaje sú obrátené podľa očakávania.

4. Rekurzívne Implementácia algoritmu

Teraz implementujme rekurzívny algoritmus v Jave:

ListNode reverseListRecursive (ListNode head) {if (head == null) {return null; } if (head.getNext () == null) {návratová hlava; } Uzol ListNode = reverseListRecursive (head.getNext ()); head.getNext (). setNext (head); head.setNext (null); spätný uzol; }

V reverseListRecursive funkcie rekurzívne navštevujeme každý prvok v prepojenom zozname, kým nedosiahneme posledný. Tento posledný prvok sa stane novou hlavičkou obráteného prepojeného zoznamu. Navštívený prvok tiež pripojíme na koniec čiastočne obráteného prepojeného zoznamu.

Podobne môžeme túto rekurzívnu implementáciu overiť jednoduchým testom jednotky:

@Test public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); Uzol ListNode = hlava; pre (int i = 1; i <= 5; i ++) {assertNotNull (uzol); assertEquals (i, node.getData ()); node = node.getNext (); } Zvrátenie LinkedListReversal = nový LinkedListReversal (); uzol = reversal.reverseListRecursive (hlava); for (int i = 5; i> = 1; i--) {assertNotNull (uzol); assertEquals (i, node.getData ()); node = node.getNext (); }}

5. Záver

V tomto tutoriáli sme implementovali dva algoritmy na obrátenie prepojeného zoznamu. Zdrojový kód článku je ako vždy k dispozícii na stránkach GitHub.