streamalism.org

1. Úvod

V tomto tutoriále sa pozrieme na implementáciu kruhového prepojeného zoznamu v Jave.

2. Kruhový prepojený zoznam

Kruhový prepojený zoznam je variáciou prepojeného zoznamu, v ktorom posledný uzol smeruje k prvému uzlu a dokončuje celý kruh uzlov.. Inými slovami, táto variácia prepojeného zoznamu nemá a nulový prvok na konci.

Touto jednoduchou zmenou získavame niekoľko výhod:

• Východiskovým bodom môže byť akýkoľvek uzol v kruhovo prepojenom zozname
• Následne je možné prechádzať celým zoznamom počnúc ktorýmkoľvek uzlom
• Pretože posledný uzol kruhového prepojeného zoznamu má ukazovateľ na prvý uzol, je ľahké vykonávať operácie zaradenia a vyradenia z frontu.

Všetko vo všetkom, toto je veľmi užitočné pri implementácii dátovej štruktúry frontu.

Z hľadiska výkonu je to rovnaké ako iné implementácie prepojeného zoznamu, okrem jednej veci: Posuv z posledného uzla do hlavného uzla je možné vykonať v konštantnom čase. Pri konvenčných prepojených zoznamoch ide o lineárnu operáciu.

3. Implementácia v Jave

Začnime vytvorením pomocného nástroja Uzol trieda, ktorá bude skladovať int hodnoty a ukazovateľ na nasledujúci uzol:

trieda Uzol {int hodnota; Uzol nextNode; public Node (int value) {this.value = value; }}

Teraz vytvorme prvý a posledný uzol v kruhovom prepojenom zozname, ktorý sa zvyčajne nazýva hlava a chvost:

public class CircularLinkedList {private Node head = null; private Node tail = null; // ....}

V nasledujúcich podkapitolách sa pozrieme na najbežnejšie operácie, ktoré môžeme vykonávať v kruhovo prepojenom zozname.

3.1. Vkladanie prvkov

Prvou operáciou, ktorú sa budeme zaoberať, je vkladanie nových uzlov. Pri vkladaní nového prvku budeme musieť zvládnuť dva prípady:

• The hlava uzol je neplatný, to znamená, že už nie sú pridané žiadne prvky. V tomto prípade urobíme nový uzol, ktorý pridáme, ako obidva hlava a chvost zoznamu, pretože existuje iba jeden uzol
• The hlava uzol nie je neplatný, to znamená, že do zoznamu je už pridaný jeden alebo viac prvkov. V tomto prípade existujúce chvost by mal smerovať na nový uzol a novo pridaný uzol sa stane chvost

V obidvoch vyššie uvedených prípadoch nextNode pre chvost ukáže na hlava

Vytvorme addNode metóda, ktorá vyžaduje hodnotu sa má vložiť ako parameter:

public void addNode (int hodnota) {Node newNode = new Node (value); if (head == null) {head = newNode; } else {tail.nextNode = newNode; } chvost = novyNode; tail.nextNode = hlava; }

Teraz môžeme do nášho kruhového prepojeného zoznamu pridať niekoľko čísel:

private CircularLinkedList createCircularLinkedList () {CircularLinkedList cll = nový CircularLinkedList (); cll.addNode (13); cll.addNode (7); cll.addNode (24); cll.addNode (1); cll.addNode (8); cll.addNode (37); cll.addNode (46); vrátiť cll; }

3.2. Nájdenie prvku

Ďalšou operáciou, na ktorú sa pozrieme, je hľadanie, aby sa zistilo, či je v zozname prvok.

Pre to, opravíme uzol v zozname (zvyčajne hlava) ako currentNode a prechádzať celým zoznamom pomocou nextNode tohto uzla, kým nenájdeme požadovaný prvok.

Pridajme novú metódu obsahujeNode to berie searchValue ako parameter:

public boolean containsNode (int searchValue) {Node currentNode = head; if (head == null) {return false; } else {do ​​{if (currentNode.value == searchValue) {return true; } currentNode = currentNode.nextNode; } while (currentNode! = head); návrat nepravdivý; }}

Teraz pridajme niekoľko testov na overenie, či vyššie vytvorený zoznam obsahuje prvky, ktoré sme pridali, a žiadne nové:

@Test public void givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements () {CircularLinkedList cll = createCircularLinkedList (); assertTrue (cll.containsNode (8)); assertTrue (cll.containsNode (37)); } @Test public void givenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse () {CircularLinkedList cll = createCircularLinkedList (); assertFalse (cll.containsNode (11)); }

3.3. Odstraňuje sa prvok

Ďalej sa pozrieme na operáciu odstránenia. Podobne ako pri vkladaní máme aj niekoľko prípadov (okrem prípadov, keď je samotný zoznam prázdny), na ktoré sa musíme pozrieť.

• Prvkom na odstránenie je hlava sám. V takom prípade musíme aktualizovať hlava ako ďalší uzol aktuálnej hlavy, a ďalší uzol chvost ako nová hlava
• Prvok na odstránenie je akýkoľvek iný prvok ako hlava. V tomto prípade stačí aktualizovať ďalší uzol predchádzajúceho uzla ako ďalší uzol uzla, ktorý je potrebné vymazať

Teraz pridáme novú metódu deleteNode to trvá valueToDelete ako parameter:

public void deleteNode (int valueToDelete) {Uzol currentNode = head; if (head! = null) {if (currentNode.value == valueToDelete) {head = head.nextNode; tail.nextNode = hlava; } else {do ​​{Node nextNode = currentNode.nextNode; if (nextNode.value == valueToDelete) {currentNode.nextNode = nextNode.nextNode; prestávka; } currentNode = currentNode.nextNode; } while (currentNode! = head); }}}

Teraz pridajme jednoduchý test na overenie, či odstránenie funguje vo všetkých prípadoch podľa očakávaní:

@Test public void 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.containsNode (46)); }

3.4. Traversing the List

V tejto poslednej časti sa pozrieme na prechod nášho kruhového prepojeného zoznamu. Podobne ako pri operáciách vyhľadávania a mazania, aj pri prechode opravujeme currentNode ako hlava a prechádzať celým zoznamom pomocou nextNode tohto uzla.

Pridajme novú metódu traverseList ktorý vytlačí prvky pridané do zoznamu:

public void traverseList () {Node currentNode = head; if (head! = null) {do {LOGGER.info (currentNode.value + ""); currentNode = currentNode.nextNode; } while (currentNode! = head); }} 

Ako vidíme, vo vyššie uvedenom príklade počas prechodu jednoducho vytlačíme hodnotu každého z uzlov, kým sa nedostaneme späť do hlavného uzla.

4. Záver

V tomto tutoriáli sme videli, ako implementovať kruhový prepojený zoznam v Jave, a preskúmali sme niektoré z najbežnejších operácií.

Najprv sme sa dozvedeli, čo presne kruhový prepojený zoznam obsahuje niektoré z najbežnejších vlastností a rozdielov oproti konvenčnému prepojenému zoznamu. Potom sme videli, ako vkladať, vyhľadávať, mazať a prechádzať položky v našej implementácii kruhového prepojeného zoznamu.

Ako obvykle sú všetky príklady použité v tomto článku dostupné na GitHub.