streamalism.org

1. Introduksjon

I denne opplæringen vil vi se på implementeringen av en sirkulær koblet liste i Java.

2. Rundkoblet liste

En sirkulær koblet liste er en variant av en koblet liste der den siste noden peker mot den første noden, og fullfører en full sirkel av noder. Med andre ord har denne varianten av den koblede listen ikke en null element på slutten.

Med denne enkle endringen får vi noen fordeler:

• Enhver node i den sirkulære koblede listen kan være et utgangspunkt
• Følgelig kan hele listen krysses fra hvilken som helst node
• Siden den siste noden i den sirkulære koblede listen har pekeren til den første noden, er det enkelt å utføre enqueue- og dequeue-operasjoner

Alt i alt, dette er veldig nyttig i implementeringen av kødatastrukturen.

Ytelsesmessig er det det samme som andre koblede listeimplementeringer bortsett fra én ting: Å krysse fra den siste noden til hodetoden kan gjøres i konstant tid. Med konvensjonelle koblede lister er dette en lineær operasjon.

3. Implementering i Java

La oss starte med å lage en hjelpestøtte Node klasse som vil lagre int verdier og en peker til neste node:

klasse Node {int-verdi; Node nesteNode; offentlig node (int-verdi) {this.value = verdi; }}

La oss nå opprette de første og siste nodene i den sirkulære koblede listen, vanligvis kalt hode og hale:

offentlig klasse CircularLinkedList {private Node head = null; private Node tail = null; // ....}

I de neste underavsnittene ser vi på de vanligste operasjonene vi kan utføre på en sirkulær koblet liste.

3.1. Sette inn elementer

Den første operasjonen vi skal dekke er innsetting av nye noder. Når du setter inn et nytt element, må vi håndtere to saker:

• De hode noden er null, det vil si at det ikke er lagt til noen elementer allerede. I dette tilfellet lager vi den nye noden vi legger til som både hode og hale av listen siden det bare er en node
• De hode node er ikke null, det vil si at det allerede er lagt til ett eller flere elementer i listen. I dette tilfellet, den eksisterende hale skal peke på den nye noden og den nylagte noden blir hale

I begge de ovennevnte tilfellene har nesteNode til hale vil peke på hode

La oss lage en addNode metoden som tar verdi skal settes inn som parameter:

public void addNode (int-verdi) {Node newNode = ny Node (verdi); hvis (head == null) {head = newNode; } annet {tail.nextNode = newNode; } hale = newNode; tail.nextNode = hode; }

Nå kan vi legge til noen få tall i vår sirkulære koblede liste:

private CircularLinkedList createCircularLinkedList () {CircularLinkedList cll = new CircularLinkedList (); cll.addNode (13); cll.addNode (7); cll.addNode (24); cll.addNode (1); cll.addNode (8); cll.addNode (37); cll.addNode (46); retur cll; }

3.2. Finne et element

Den neste operasjonen vi ser på, er å søke etter om et element er til stede i listen.

For dette, vi fikser en node i listen (vanligvis hode) som currentNode og krysse gjennom hele listen ved hjelp av nesteNode av denne noden, til vi finner det nødvendige elementet.

La oss legge til en ny metode inneholderNode som tar searchValue som parameter:

offentlig boolsk inneholderNode (int searchValue) {Node currentNode = head; if (head == null) {return false; } annet {gjør {if (currentNode.value == searchValue) {return true; } currentNode = currentNode.nextNode; } mens (nåværendeNode! = hode); returner falsk; }}

La oss nå legge til et par tester for å bekrefte at listen ovenfor opprettet inneholder elementene vi la til og ingen nye:

@Test offentlig ugyldig gittACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements () {CircularLinkedList cll = createCircularLinkedList (); assertTrue (cll.containsNode (8)); assertTrue (cll.containsNode (37)); } @Test offentlig ugyldig gittACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse () {CircularLinkedList cll = createCircularLinkedList (); assertFalse (cll.containsNode (11)); }

3.3. Slette et element

Deretter ser vi på sletteoperasjonen. I likhet med innsetting har vi et par tilfeller (unntatt saken der selve listen er tom) som vi må se på.

• Element å slette er hode seg selv. I dette tilfellet må vi oppdatere hode som neste node for gjeldende hode, og neste node på hale som det nye hodet
• Element som skal slettes er et annet element enn hode. I dette tilfellet trenger vi bare å oppdatere neste node i forrige node som neste node i node som må slettes

Vi legger nå til en ny metode Slett node som tar valueToDelete som parameter:

public void deleteNode (int valueToDelete) {Node currentNode = head; if (head! = null) {if (currentNode.value == valueToDelete) {head = head.nextNode; tail.nextNode = hode; } annet {do {Node nextNode = currentNode.nextNode; hvis (nextNode.value == valueToDelete) {currentNode.nextNode = nextNode.nextNode; gå i stykker; } currentNode = currentNode.nextNode; } mens (nåværendeNode! = hode); }}}

La oss nå legge til en enkel test for å bekrefte at sletting fungerer som forventet i alle tilfeller:

@Test offentlig ugyldig gittACircularLinkedList_WhenDeletingElements_ThenListDoesNotContainThoseElements () {CircularLinkedList cll = createCircularLinkedList (); assertTrue (cll.containsNode (13)); cll.deleteNode (13); assertFalse (cll.containsNode (13)); assertTrue (cll.containsNode (1)); cll.deleteNode (1); assertFalse (cll.containsNode (1)); assertTrue (cll.containsNode (46)); cll.deleteNode (46); assertFalse (cll.containsNode (46)); }

3.4. Krysser listen

Vi kommer til å se på gjennomgangen av vår sirkulære koblede liste i denne siste delen. I likhet med søke- og sletteoperasjonene, for traversal fikser vi currentNode som hode og krysse gjennom hele listen ved hjelp av nesteNode av denne noden.

La oss legge til en ny metode traverseList som skriver ut elementene som er lagt til i listen:

public void traverseList () {Node currentNode = head; if (head! = null) {do {LOGGER.info (currentNode.value + ""); currentNode = currentNode.nextNode; } mens (nåværendeNode! = hode); }} 

Som vi kan se, i eksemplet ovenfor, under gjennomkjøringen, skriver vi bare ut verdien av hver av nodene, til vi kommer tilbake til hodetoden.

4. Konklusjon

I denne opplæringen har vi sett hvordan vi implementerer en sirkulær koblet liste i Java og utforsket noen av de vanligste operasjonene.

Først lærte vi hva akkurat en sirkulær koblet liste er, inkludert noen av de vanligste funksjonene og forskjellene med en konvensjonell koblet liste. Så så vi hvordan vi setter inn, søker, sletter og krysser elementer i implementeringen av den sirkulære koblede listen.

Som vanlig er alle eksemplene som brukes i denne artikkelen tilgjengelig på GitHub.