Å reversere en koblet liste i Java

1. Introduksjon

I denne opplæringen implementerer vi to koblede listeomvendingsalgoritmer i Java.

2. Koblet liste datastruktur

En koblet liste er en lineær datastruktur der en peker i hvert element bestemmer rekkefølgen. Hvert element i en koblet liste inneholder et datafelt for å lagre listedataene og et pekefelt for å peke på neste element i sekvensen. Vi kan også bruke en hode peker for å peke på startelementet til en koblet liste:

Etter at vi har reversert den koblede listen, blir hode vil peke på det siste elementet i den opprinnelige koblede listen, og pekeren til hvert element vil peke på det forrige elementet i den opprinnelige koblede listen:

I Java har vi en LinkedList klasse for å gi en dobbeltkoblet listeimplementering av Liste og Deque grensesnitt. Imidlertid bruker vi en generell enkeltkoblet listedatastruktur i denne opplæringen.

La oss først starte med en ListNode klasse for å representere et element i en koblet liste:

offentlig klasse ListNode {private int data; privat ListNode neste; ListNode (int data) {this.data = data; this.next = null; } // standard getters and setters}

De ListNode klasse har to felt:

  • Et heltall som representerer elementets data
  • En peker / referanse til neste element

En koblet liste kan inneholde flere ListNode gjenstander. For eksempel kan vi konstruere listen over eksempler knyttet til en løkke:

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; } annet {tail.setNext (node); } hale = node; } returnere hodet; }

3. Iterativ algoritmeimplementering

La oss implementere den iterative algoritmen i Java:

ListNode reverseList (ListNode head) {ListNode forrige = null; ListNode gjeldende = hode; mens (gjeldende! = null) {ListNode nextElement = gjeldende.getNeste (); current.setNext (forrige); forrige = nåværende; gjeldende = nesteElement; } returnere forrige; }

I denne iterative algoritmen bruker vi to ListNode variabler, tidligere og nåværende, for å representere to tilstøtende elementer i den koblede listen. For hver iterasjon reverserer vi disse to elementene og skifter deretter til de neste to elementene.

Til slutt, nåværende pekeren vil være null, og tidligere pekeren vil være det siste elementet i den gamle koblede listen. Derfor, tidligere er også den nye hodepekeren til den omvendte koblede listen, og vi returnerer den fra metoden.

Vi kan bekrefte denne iterative implementeringen med en enkel enhetstest:

@Test offentlig ugyldighet givenLinkedList_whenIterativeReverse_thenOutputCorrectResult () {ListNode head = constructLinkedList (); ListNode-node = hode; for (int i = 1; i <= 5; i ++) {assertNotNull (node); assertEquals (i, node.getData ()); node = node.getNext (); } Reversering av 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 enhetstesten konstruerer vi først en prøvekoblet liste med fem noder. Vi bekrefter også at hver node i den koblede listen inneholder riktig dataverdi. Deretter kaller vi den iterative funksjonen for å reversere den koblede listen. Til slutt sjekker vi den omvendte koblede listen for å sikre at dataene blir reversert som forventet.

4. Rekursiv Algoritmeimplementering

La oss nå implementere den rekursive algoritmen i Java:

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

I reverseListRecursive funksjon, besøker vi rekursivt hvert element i den koblede listen til vi når den siste. Dette siste elementet blir den nye lederen for den omvendte koblede listen. Vi legger også det besøkte elementet til slutten av den delvis omvendte koblede listen.

På samme måte kan vi bekrefte denne rekursive implementeringen med en enkel enhetstest:

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

5. Konklusjon

I denne opplæringen implementerte vi to algoritmer for å reversere en koblet liste. Som alltid er kildekoden for artikkelen tilgjengelig på GitHub.