streamalism.org

1. Introduktion

I denne vejledning implementerer vi to linkede reverseringsalgoritmer i Java.

2. Tilknyttet liste Datastruktur

En sammenkædet liste er en lineær datastruktur, hvor en markør i hvert element bestemmer rækkefølgen. Hvert element i en sammenkædet liste indeholder et datafelt til lagring af listedataene og et markørfelt til at pege på det næste element i sekvensen. Vi kan også bruge en hoved markør for at pege på startelementet på en linket liste:

Når vi har omvendt den sammenkædede liste, bliver hoved vil pege på det sidste element i den oprindeligt linkede liste, og markøren på hvert element vil pege på det forrige element i den oprindeligt linkede liste:

I Java har vi en LinkedList klasse for at give en dobbeltkoblet listeimplementering af Liste og Deque grænseflader. Vi bruger dog en generel enkeltkædet liste datastruktur i denne vejledning.

Lad os først starte med en ListNode klasse til at repræsentere et element på en linket liste:

offentlig klasse ListNode {private int-data; privat ListNode næste; ListNode (int data) {this.data = data; this.next = null; } // standard getters og setters}

Det ListNode klasse har to felter:

• En heltalværdi, der repræsenterer elementets data
• En markør / henvisning til det næste element

En linket liste kan indeholde flere ListNode genstande. For eksempel kan vi konstruere ovenstående liste over eksempler med en sløjfe:

ListNode constructLinkedList () {ListNode head = null; ListNode hale = null; for (int i = 1; i <= 5; i ++) {ListNode node = new ListNode (i); hvis (head == null) {head = node; } andet {tail.setNext (node); } hale = knude; } returner hovedet }

3. Iterativ algoritme implementering

Lad os implementere den iterative algoritme i Java:

ListNode reverseList (ListNode head) {ListNode forrige = null; ListNode strøm = hoved; mens (nuværende! = null) {ListNode nextElement = nuværende.getNext (); current.setNext (forrige); forrige = nuværende; nuværende = næsteElement; } returnere forrige; }

I denne iterative algoritme bruger vi to ListNode variabler, Tidligere og nuværende, for at repræsentere to tilstødende elementer på den sammenkædede liste. For hver iteration vender vi disse to elementer om og skifter derefter til de næste to elementer.

I sidste ende, den nuværende markøren bliver nul, og Tidligere pointer vil være det sidste element på den gamle linkede liste. Derfor, Tidligere er også den nye hovedmarkør på den omvendte linkede liste, og vi returnerer den fra metoden.

Vi kan verificere denne iterative implementering med en simpel enhedstest:

@Test offentlig ugyldighed givenLinkedList_whenIterativeReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); ListNode-node = hoved; for (int i = 1; i <= 5; i ++) {assertNotNull (node); assertEquals (i, node.getData ()); node = node.getNext (); } Reversering af LinkedListReversal = ny LinkedListReversal (); node = reversal.reverseList (head); for (int i = 5; i> = 1; i--) {assertNotNull (node); assertEquals (i, node.getData ()); node = node.getNext (); }}

I denne enhedstest konstruerer vi først en prøvekædet liste med fem noder. Vi verificerer også, at hver node på den linkede liste indeholder den korrekte dataværdi. Derefter kalder vi den iterative funktion for at vende den linkede liste. Endelig kontrollerer vi den omvendte linkede liste for at sikre, at dataene vendes som forventet.

4. Rekursiv Algoritmeimplementering

Lad os nu implementere den rekursive algoritme i Java:

ListNode reverseListRecursive (ListNode head) {if (head == null) {return null; } hvis (head.getNext () == null) {return head; } ListNode node = reverseListRecursive (head.getNext ()); head.getNext (). setNext (head); head.setNext (null); returknude }

I reverseListRecursive funktion, besøger vi hvert element på den linkede liste rekursivt, indtil vi når den sidste. Dette sidste element bliver det nye leder af den omvendte linkede liste. Vi tilføjer også det besøgte element til slutningen af ​​den delvist omvendte sammenkædede liste.

På samme måde kan vi kontrollere denne rekursive implementering med en simpel enhedstest:

@Test offentlig ugyldighed givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); ListNode-node = hoved; for (int i = 1; i <= 5; i ++) {assertNotNull (node); assertEquals (i, node.getData ()); node = node.getNext (); } Reversering af LinkedListReversal = ny LinkedListReversal (); node = reversal.reverseListRecursive (head); for (int i = 5; i> = 1; i--) {assertNotNull (node); assertEquals (i, node.getData ()); node = node.getNext (); }}

5. Konklusion

I denne vejledning implementerede vi to algoritmer for at vende en sammenkædet liste. Som altid er kildekoden til artiklen tilgængelig på GitHub.