Cirkulær sammenkædet liste Java-implementering

1. Introduktion

I denne vejledning ser vi på implementeringen af en cirkulær linket liste i Java.

2. Cirkulær sammenkædet liste

En cirkulær sammenkædet liste er en variation af en sammenkædet liste, hvor den sidste node peger på den første node og udfylder en fuld cirkel af noder. Med andre ord har denne variation af den linkede liste ikke en nul element i slutningen.

Med denne enkle ændring får vi nogle fordele:

Enhver knude på den cirkulære sammenkædede liste kan være et udgangspunkt
Derfor kan hele listen krydses startende fra enhver knude
Da den sidste node på den cirkulære sammenkædede liste har markøren til den første node, er det let at udføre enqueue- og dequeue-operationer

Alt i alt, dette er meget nyttigt ved implementeringen af kødatastrukturen.

Præstationsmæssigt er det det samme som andre linkede implementeringer bortset fra én ting: Kørsel fra den sidste knude til hovedknuden kan ske i konstant tid. Med konventionelle sammenkædede lister er dette en lineær operation.

3. Implementering i Java

Lad os starte med at oprette en hjælpestøtte Node klasse, der gemmer int værdier og en markør til den næste node:

klasse Node {int værdi; Node næsteNode; offentlig knude (int-værdi) {this.value = værdi; }}

Lad os nu oprette de første og sidste noder på den cirkulære sammenkædede liste, der normalt kaldes hoved og hale:

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

I de næste underafsnit vil vi se på de mest almindelige operationer, vi kan udføre på en cirkulær sammenkædet liste.

3.1. Indsættelse af elementer

Den første operation, vi skal dække, er indsættelse af nye noder. Mens vi indsætter et nyt element, skal vi håndtere to sager:

Det hoved node er nul, det vil sige, at der ikke allerede er tilføjet nogen elementer. I dette tilfælde laver vi den nye node, vi tilføjer, som både hoved og hale på listen, da der kun er en node
Det hoved node er ikke nul, det vil sige, at der allerede er føjet et eller flere elementer til listen. I dette tilfælde er den eksisterende hale skal pege på den nye knude, og den nyligt tilføjede knude bliver til hale

I begge ovennævnte tilfælde er næsteNode til hale vil pege på hoved

Lad os oprette en addNode metode, der tager værdi skal indsættes som en parameter:

public void addNode (int-værdi) {Node newNode = ny Node (værdi); hvis (head == null) {head = newNode; } andet {tail.nextNode = newNode; } hale = newNode; tail.nextNode = hoved; }

Nu kan vi tilføje et par tal til vores cirkulære sammenkædede 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. At finde et element

Den næste operation, vi ser på, søger efter, om et element er til stede på listen.

For det, vi løser en knude på listen (normalt hoved) som nuværendeNode og krydse hele listen ved hjælp af næsteNode af denne knude, indtil vi finder det krævede element.

Lad os tilføje en ny metode indeholderNode der tager searchValue som parameter:

offentlig boolsk containNode (int searchValue) {Node currentNode = head; hvis (head == null) {return false; } andet {gør {hvis (currentNode.value == searchValue) {returner sand; } nuværendeNode = nuværendeNode.nextNode; } mens (nuværendeNode! = hoved); returner falsk; }}

Lad os nu tilføje et par tests for at verificere, at den ovenfor oprettede liste indeholder de elementer, vi har tilføjet, og ingen nye:

@Test offentlig ugyldighed givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements () {CircularLinkedList cll = createCircularLinkedList (); assertTrue (cll.containsNode (8)); assertTrue (cll.containsNode (37)); } @ Test offentligt ugyldigt givet ACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse () {CircularLinkedList cll = createCircularLinkedList (); assertFalse (cll.containsNode (11)); }

3.3. Sletning af et element

Dernæst ser vi på sletningen. Svarende til indsættelse har vi et par tilfælde (undtagen det tilfælde, hvor selve listen er tom), som vi skal se på.

Element, der skal slettes, er hoved sig selv. I dette tilfælde skal vi opdatere hoved som den næste knude på det aktuelle hoved, og den næste knude på hale som det nye hoved
Element, der skal slettes, er ethvert andet element end hoved. I dette tilfælde skal vi bare opdatere den næste node i den forrige node som den næste node i den node, der skal slettes

Vi tilføjer nu en ny metode deleteNode der tager valueToDelete som parameter:

public void deleteNode (int valueToDelete) {Node currentNode = head; if (head! = null) {if (currentNode.value == valueToDelete) {head = head.nextNode; tail.nextNode = hoved; } andet {gør {Node nextNode = currentNode.nextNode; hvis (nextNode.value == valueToDelete) {currentNode.nextNode = nextNode.nextNode; pause; } nuværendeNode = nuværendeNode.nextNode; } mens (nuværendeNode! = hoved); }}}

Lad os nu tilføje en simpel test for at kontrollere, at sletning fungerer som forventet i alle sager:

@Test offentlig ugyldighed givetACircularLinkedList_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. Krydser listen

Vi skal se på gennemgangen af vores cirkulære sammenkædede liste i dette sidste afsnit. Svarende til søge- og sletningsoperationer, til traversal reparerer vi nuværendeNode som hoved og krydse hele listen ved hjælp af næsteNode af denne knude.

Lad os tilføje en ny metode traverseList der udskriver de elementer, der føjes til listen:

public void traverseList () {Node currentNode = head; hvis (head! = null) {gør {LOGGER.info (currentNode.value + ""); currentNode = currentNode.nextNode; } mens (nuværendeNode! = hoved); }}

Som vi kan se, i eksemplet ovenfor, under gennemgangen, udskriver vi simpelthen værdien af hver af noderne, indtil vi kommer tilbage til hovednoden.

4. Konklusion

I denne vejledning har vi set, hvordan man implementerer en cirkulær linket liste i Java og udforsket nogle af de mest almindelige operationer.

For det første lærte vi, hvad en cirkulær sammenkædet liste er, herunder nogle af de mest almindelige træk og forskelle med en konventionel sammenkædet liste. Derefter så vi, hvordan vi indsætter, søger, sletter og krydser elementer i vores implementering af en cirkulær sammenkædet liste.

Som sædvanligt er alle eksemplerne i denne artikel tilgængelige på GitHub.

streamalism.org