streamalism.org

1. Uvod

U ovom uputstvu pogledat ćemo provedbu kružno povezanog popisa u Javi.

2. Kružno povezani popis

Kružno povezani popis varijacija je povezanog popisa u kojem posljednji čvor pokazuje na prvi čvor, završavajući puni krug čvorova. Drugim riječima, ova varijacija povezanog popisa nema null element na kraju.

Ovom jednostavnom promjenom postižemo neke pogodnosti:

• Bilo koji čvor na kružno povezanom popisu može biti početna točka
• Slijedom toga, cijeli popis može se prelaziti počevši od bilo kojeg čvora
• Budući da posljednji čvor kružno povezanog popisa ima pokazivač na prvi čvor, lako je izvesti operacije čekanja i uklanjanja reda

Sve u svemu, ovo je vrlo korisno u implementaciji strukture podataka o redu čekanja.

Što se tiče izvedbe, to je isto kao i ostale implementacije povezanog popisa, osim jedne stvari: Prelazak s posljednjeg čvora na glavni čvor može se obaviti u stalnom vremenu. Kod konvencionalnih povezanih popisa ovo je linearna operacija.

3. Implementacija u Javi

Krenimo od stvaranja pomoćnog Čvor razred koji će pohraniti int vrijednosti i pokazivač na sljedeći čvor:

class Node {int vrijednost; Čvor nextNode; javni čvor (int vrijednost) {this.value = vrijednost; }}

Ajmo sada stvoriti prvi i zadnji čvor na kružno povezanom popisu, koji se obično naziva glava i rep:

javna klasa CircularLinkedList {private Node head = null; private Node tail = null; // ....}

U sljedećim pododjeljcima pogledat ćemo najčešće operacije koje možemo izvesti na kružno povezanom popisu.

3.1. Umetanje elemenata

Prva operacija koju ćemo pokriti je umetanje novih čvorova. Tijekom umetanja novog elementa trebat ćemo riješiti dva slučaja:

• The glava čvor je null, to jest nema već dodanih elemenata. U ovom ćemo slučaju novi čvor dodati kao glava i rep popisa jer postoji samo jedan čvor
• The glava čvor nije null, što znači da je na popisu već dodan jedan ili više elemenata. U ovom slučaju postojeće rep treba ukazivati ​​na novi čvor i novo dodani čvor postat će rep

U oba gore navedena slučaja nextNode za rep ukazat će na glava

Stvorimo addNode metoda koja uzima vrijednost koji treba umetnuti kao parametar:

javna void addNode (int vrijednost) {Čvor newNode = novi čvor (vrijednost); if (head == null) {head = newNode; } else {rep.nextNode = newNode; } rep = noviČvor; tail.nextNode = glava; }

Sada na naš kružno povezani popis možemo dodati nekoliko brojeva:

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); povrat cll; }

3.2. Pronalaženje elementa

Sljedeća operacija koju ćemo razmotriti je traženje kako bi se utvrdilo je li element prisutan na popisu.

Za ovo, popravit ćemo čvor na popisu (obično glava) kao currentNode i pređite preko cijelog popisa pomoću nextNode ovog čvora, dok ne pronađemo traženi element.

Dodajmo novu metodu containsNode to traje searchValue kao parametar:

javni boolean containsNode (int searchValue) {Čvor currentNode = head; if (head == null) {return false; } else {do ​​{if (currentNode.value == searchValue) {return true; } currentNode = currentNode.nextNode; } while (currentNode! = glava); return false; }}

Sad, dodajmo nekoliko testova kako bismo provjerili sadrži li gore stvoreni popis elemente koje smo dodali, a ne nove:

@Test javna praznina givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements () {CircularLinkedList cll = createCircularLinkedList (); assertTrue (cll.containsNode (8)); assertTrue (cll.containsNode (37)); } @Test javna praznina danaACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse () {CircularLinkedList cll = createCircularLinkedList (); assertFalse (cll.containsNode (11)); }

3.3. Brisanje elementa

Dalje ćemo pogledati operaciju brisanja. Slično umetanju, imamo nekoliko slučajeva (izuzimajući slučaj kada je sam popis prazan) koje moramo pogledati.

• Element za brisanje je glava sebe. U ovom slučaju moramo ažurirati glava kao sljedeći čvor trenutne glave, i sljedeći čvor rep kao nova glava
• Element za brisanje je bilo koji element koji nije glava. U ovom slučaju, trebamo samo ažurirati sljedeći čvor prethodnog čvora kao sljedeći čvor čvora koji treba izbrisati

Sada ćemo dodati novu metodu deleteNode to traje valueToDelete kao parametar:

javna void deleteNode (int valueToDelete) {Čvor currentNode = head; if (head! = null) {if (currentNode.value == valueToDelete) {head = head.nextNode; tail.nextNode = glava; } else {do ​​{Node nextNode = currentNode.nextNode; if (nextNode.value == valueToDelete) {currentNode.nextNode = nextNode.nextNode; pauza; } currentNode = currentNode.nextNode; } while (currentNode! = glava); }}}

Dodajmo sada jednostavan test kako bismo provjerili funkcionira li brisanje prema svim očekivanjima:

@Test javna praznina givenACircularLinkedList_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.contensNode (46)); }

3.4. Obilazeći popis

U ovom ćemo završnom odjeljku pogledati preokret našeg kružno povezanog popisa. Slično operacijama pretraživanja i brisanja, za prelazak popravljamo currentNode kao glava i pređite preko cijelog popisa pomoću nextNode ovog čvora.

Dodajmo novu metodu traverseList koji ispisuje elemente dodane na popis:

javna praznina traverseList () {Čvor currentNode = head; if (head! = null) {do {LOGGER.info (currentNode.value + ""); currentNode = currentNode.nextNode; } while (currentNode! = glava); }} 

Kao što vidimo, u gornjem primjeru, tijekom prelaska jednostavno ispisujemo vrijednost svakog od čvorova, dok se ne vratimo na glavni čvor.

4. Zaključak

U ovom uputstvu vidjeli smo kako implementirati kružno povezani popis u Javi i istražili neke od najčešćih operacija.

Prvo smo saznali što točno kružni povezani popis uključuje neke od najčešćih značajki i razlika s konvencionalnim povezanim popisom. Zatim smo vidjeli kako umetnuti, pretraživati, brisati i prelaziti stavke u našu implementaciju kružnog povezanog popisa.

Kao i obično, svi primjeri korišteni u ovom članku dostupni su na GitHubu.