streamalism.org

1. Uvod

U ovom uputstvu implementirat ćemo dva povezana algoritma za poništavanje popisa u Javi.

2. Struktura podataka povezanog popisa

Povezani popis je linearna struktura podataka u kojoj pokazivač u svakom elementu određuje redoslijed. Svaki element povezanog popisa sadrži podatkovno polje za pohranu podataka popisa i polje pokazivača za usmjeravanje na sljedeći element u nizu. Također, možemo koristiti i glava pokazivač koji pokazuje na početni element povezanog popisa:

Nakon što preokrenemo povezani popis, glava ukazat će na posljednji element izvornog povezanog popisa, a pokazivač svakog elementa ukazat će na prethodni element izvornog povezanog popisa:

U Javi imamo LinkedList klase kako bi se osigurala dvostruko povezana provedba popisa Popis i Deque sučelja. Međutim, u ovom ćemo se priručniku koristiti općenitom pojedinačno povezanom strukturom podataka popisa.

Krenimo prvo s a ListNode klasa koja predstavlja element povezanog popisa:

javna klasa ListNode {privatni int podaci; privatni ListNode sljedeći; ListNode (int podaci) {this.data = podaci; this.next = null; } // standardni getteri i postavljači}

The ListNode razred ima dva polja:

• Cjelobrojna vrijednost koja predstavlja podatke elementa
• Pokazivač / referenca na sljedeći element

Povezani popis može sadržavati više njih ListNode predmeta. Na primjer, gornji uzorak povezani popis možemo konstruirati pomoću petlje:

ListNode constructLinkedList () {ListNode head = null; ListNode tail = null; for (int i = 1; i <= 5; i ++) {ListNode čvor = novi ListNode (i); if (head == null) {head = node; } else {tail.setNext (čvor); } rep = čvor; } povratna glava; }

3. Implementacija iterativnog algoritma

Primijenimo iterativni algoritam u Javi:

ListNode reverseList (glava ListNode) {ListNode previous = null; ListNode current = head; while (current! = null) {ListNode nextElement = current.getNext (); current.setNext (prethodno); prethodni = trenutni; current = nextElement; } povratak prethodni; }

U ovom iterativnom algoritmu koristimo dva ListNode varijable, prethodni i Trenutno, da predstavljaju dva susjedna elementa na povezanom popisu. Za svaku iteraciju obrćemo ta dva elementa, a zatim se prebacimo na sljedeća dva elementa.

Na kraju, Trenutno pokazivač će biti null, i prethodni pokazivač će biti posljednji element starog povezanog popisa. Stoga, prethodni je ujedno i novi pokazivač glave obrnutog povezanog popisa i vraćamo ga iz metode.

Ovu iterativnu implementaciju možemo provjeriti jednostavnim jediničnim testom:

@Test javna praznina givenLinkedList_whenIterativeReverse_thenOutputCorrectResult () {HeadNode head = constructLinkedList (); ListNode čvor = glava; za (int i = 1; i <= 5; i ++) {assertNotNull (čvor); assertEquals (i, node.getData ()); node = node.getNext (); } Preokret LinkedListReversal = novi LinkedListReversal (); node = reversal.reverseList (glava); za (int i = 5; i> = 1; i--) {assertNotNull (čvor); assertEquals (i, node.getData ()); node = node.getNext (); }}

U ovom jediničnom testu prvo konstruiramo uzorak povezani popis s pet čvorova. Također, provjeravamo sadrži li svaki čvor na povezanom popisu ispravnu vrijednost podataka. Zatim pozivamo iterativnu funkciju za preokretanje povezanog popisa. Na kraju provjeravamo obrnuti povezani popis kako bismo bili sigurni da su podaci obrnuti prema očekivanjima.

4. Rekurzivno Implementacija algoritma

Sada, implementirajmo rekurzivni algoritam u Javi:

ListNode reverseListRecursive (ListNode head) {if (head == null) {return null; } if (head.getNext () == null) {return head; } Čvor ListNode = reverseListRecursive (head.getNext ()); head.getNext (). setNext (head); head.setNext (null); povratni čvor; }

U reverseListRecursive funkcija, rekurzivno posjećujemo svaki element na povezanom popisu dok ne dođemo do posljednjeg. Ovaj posljednji element postat će nova glava obrnutog povezanog popisa. Također, posjećeni element dodajemo na kraj djelomično obrnutog povezanog popisa.

Slično tome, ovu rekurzivnu implementaciju možemo provjeriti jednostavnim jediničnim testom:

@Test javna praznina givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult () {HeadNode head = constructLinkedList (); ListNode čvor = glava; za (int i = 1; i <= 5; i ++) {assertNotNull (čvor); assertEquals (i, node.getData ()); node = node.getNext (); } Preokret LinkedListReversal = novi LinkedListReversal (); node = reversal.reverseListRecursive (glava); za (int i = 5; i> = 1; i--) {assertNotNull (čvor); assertEquals (i, node.getData ()); node = node.getNext (); }}

5. Zaključak

U ovom smo vodiču implementirali dva algoritma za preokretanje povezanog popisa. Kao i uvijek, izvorni kôd članka dostupan je na GitHubu.