streamalism.org

1. Inleiding

In deze tutorial kijken we naar de implementatie van een circulaire gekoppelde lijst in Java.

2. Circulaire gekoppelde lijst

Een circulaire gekoppelde lijst is een variatie op een gekoppelde lijst waarin het laatste knooppunt naar het eerste knooppunt wijst en een volledige cirkel van knooppunten voltooit. Met andere woorden, deze variant van de gekoppelde lijst heeft geen nul element aan het einde.

Met deze eenvoudige wijziging behalen we enkele voordelen:

• Elk knooppunt in de circulaire gekoppelde lijst kan een startpunt zijn
• Bijgevolg kan de hele lijst worden doorlopen vanaf elk knooppunt
• Aangezien het laatste knooppunt van de circulaire gekoppelde lijst de aanwijzer naar het eerste knooppunt heeft, is het eenvoudig om bewerkingen uit te voeren en uit de wachtrij te halen

Globaal genomen, dit is erg handig bij de implementatie van de wachtrij datastructuur.

Qua prestaties is het hetzelfde als andere implementaties van gekoppelde lijsten, behalve één ding: Het oversteken van het laatste knooppunt naar het hoofdknooppunt kan in constante tijd worden gedaan. Bij conventionele gekoppelde lijsten is dit een lineaire bewerking.

3. Implementatie in Java

Laten we beginnen met het maken van een hulpfunctie Knooppunt klasse die zal worden opgeslagen int waarden en een aanwijzer naar het volgende knooppunt:

class Node {int waarde; Knooppunt nextNode; public Node (int waarde) {this.value = value; }}

Laten we nu de eerste en laatste knooppunten maken in de circulaire gekoppelde lijst, meestal de hoofd en staart:

openbare klasse CircularLinkedList {privéknooppunt hoofd = null; private Node tail = null; // ....}

In de volgende paragrafen zullen we de meest voorkomende bewerkingen bekijken die we kunnen uitvoeren op een circulaire gekoppelde lijst.

3.1. Elementen invoegen

De eerste operatie die we gaan behandelen, is het invoegen van nieuwe knooppunten. Bij het invoegen van een nieuw element moeten we twee gevallen behandelen:

• De hoofd knooppunt is nul, dat wil zeggen dat er nog geen elementen zijn toegevoegd. In dit geval maken we het nieuwe knooppunt dat we toevoegen als zowel het hoofd en staart van de lijst omdat er maar één knooppunt is
• De hoofd knooppunt is niet nul, dat wil zeggen dat er al een of meer elementen aan de lijst zijn toegevoegd. In dit geval is het bestaande staart moet naar het nieuwe knooppunt wijzen en het nieuw toegevoegde knooppunt wordt het staart

In beide bovenstaande gevallen is de nextNode voor staart zal wijzen naar hoofd

Laten we een addNode methode die de waarde in te voegen als parameter:

public void addNode (int waarde) {Node newNode = new Node (waarde); if (head == null) {head = newNode; } else {tail.nextNode = newNode; } tail = newNode; tail.nextNode = hoofd; }

Nu kunnen we een paar cijfers toevoegen aan onze circulaire gekoppelde lijst:

privé CircularLinkedList createCircularLinkedList () {CircularLinkedList cll = nieuwe CircularLinkedList (); cll.addNode (13); cll.addNode (7); cll.addNode (24); cll.addNode (1); cll.addNode (8); cll.addNode (37); cll.addNode (46); retourneer cll; }

3.2. Een element zoeken

De volgende bewerking die we zullen bekijken, is zoeken om te bepalen of een element aanwezig is in de lijst.

Voor deze, we repareren een knooppunt in de lijst (meestal de hoofd) als de currentNode en doorloop de hele lijst met de nextNode van dit knooppunt, totdat we het vereiste element hebben gevonden.

Laten we een nieuwe methode toevoegen bevatNode dat kost de zoekwaarde als parameter:

openbare 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); teruggeven false; }}

Laten we nu een paar tests toevoegen om te controleren of de hierboven gemaakte lijst de elementen bevat die we hebben toegevoegd en geen nieuwe:

@Test openbare ongeldig gegevenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements () {CircularLinkedList cll = createCircularLinkedList (); assertTrue (cll.containsNode (8)); assertTrue (cll.containsNode (37)); } @Test openbare ongeldig gegevenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse () {CircularLinkedList cll = createCircularLinkedList (); assertFalse (cll.containsNode (11)); }

3.3. Een element verwijderen

Vervolgens kijken we naar de verwijderbewerking. Net als bij invoegen hebben we een aantal gevallen (met uitzondering van het geval waarin de lijst zelf leeg is) waar we naar moeten kijken.

• Element dat moet worden verwijderd, is het hoofd zelf. In dit geval moeten we het hoofd als het volgende knooppunt van het huidige hoofd, en het volgende knooppunt van de staart als het nieuwe hoofd
• Element dat moet worden verwijderd, is elk ander element dan het hoofd. In dit geval hoeven we alleen het volgende knooppunt van het vorige knooppunt bij te werken als het volgende knooppunt van het knooppunt dat moet worden verwijderd

We gaan nu een nieuwe methode toevoegen deleteNode dat kost de valueToDelete als parameter:

openbare ongeldige deleteNode (int valueToDelete) {Node currentNode = head; if (head! = null) {if (currentNode.value == valueToDelete) {head = head.nextNode; tail.nextNode = hoofd; } else {do ​​{Node nextNode = currentNode.nextNode; if (nextNode.value == valueToDelete) {currentNode.nextNode = nextNode.nextNode; breken; } currentNode = currentNode.nextNode; } while (currentNode! = head); }}}

Laten we nu een eenvoudige test toevoegen om te controleren of het verwijderen werkt zoals verwacht voor alle gevallen:

@Test openbare leegte gegevenACircularLinkedList_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. De lijst doorkruisen

In deze laatste sectie gaan we de doorloop van onze circulaire gelinkte lijst bekijken. Net als bij de zoek- en verwijderbewerkingen, repareren we voor traversal de currentNode net zo hoofd en doorloop de hele lijst met de nextNode van dit knooppunt.

Laten we een nieuwe methode toevoegen traverseList die de elementen afdrukt die aan de lijst zijn toegevoegd:

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

Zoals we in het bovenstaande voorbeeld kunnen zien, drukken we tijdens het doorlopen eenvoudig de waarde van elk van de knooppunten af, totdat we terugkomen bij het hoofdknooppunt.

4. Conclusie

In deze zelfstudie hebben we gezien hoe we een circulaire gekoppelde lijst in Java kunnen implementeren en hebben we enkele van de meest voorkomende bewerkingen onderzocht.

Ten eerste hebben we geleerd wat een circulaire gekoppelde lijst precies is, inclusief enkele van de meest voorkomende kenmerken en verschillen met een conventionele gekoppelde lijst. Vervolgens hebben we gezien hoe we items kunnen invoegen, zoeken, verwijderen en doorlopen in onze implementatie van circulaire gekoppelde lijsten.

Zoals gewoonlijk zijn alle voorbeelden die in dit artikel worden gebruikt, beschikbaar op GitHub.