Circular Linked List Java-Implementierung

1. Einleitung

In diesem Tutorial werden wir uns die Implementierung einer zirkulären verknüpften Liste in Java ansehen.

2. Zirkuläre verknüpfte Liste

Eine kreisförmige verknüpfte Liste ist eine Variation einer verknüpften Liste, in der der letzte Knoten auf den ersten Knoten zeigt und einen vollständigen Knotenkreis schließt . Mit anderen Worten, diese Variante der verketteten Liste ist noch kein Nullelement am Ende.

Mit dieser einfachen Änderung erhalten wir einige Vorteile:

  • Jeder Knoten in der zirkular verknüpften Liste kann ein Ausgangspunkt sein
  • Folglich kann die gesamte Liste ausgehend von einem beliebigen Knoten durchlaufen werden
  • Da der letzte Knoten der zirkular verknüpften Liste den Zeiger auf den ersten Knoten hat, ist es einfach, Enqueue- und Dequeue-Operationen durchzuführen

Alles in allem ist dies sehr nützlich bei der Implementierung der Warteschlangendatenstruktur.

In Bezug auf die Leistung ist es dasselbe wie bei anderen Implementierungen von verknüpften Listen, mit einer Ausnahme: Das Überqueren vom letzten Knoten zum Hauptknoten kann in konstanter Zeit erfolgen . Bei herkömmlichen verknüpften Listen ist dies eine lineare Operation.

3. Implementierung in Java

Beginnen wir mit der Erstellung einer zusätzlichen Knotenklasse , in der int- Werte und ein Zeiger auf den nächsten Knoten gespeichert werden :

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

Erstellen wir nun den ersten und den letzten Knoten in der zirkular verknüpften Liste, die normalerweise als Kopf und Schwanz bezeichnet werden:

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

In den nächsten Unterabschnitten werden wir uns die häufigsten Operationen ansehen, die wir für eine zirkuläre verknüpfte Liste ausführen können.

3.1. Elemente einfügen

Die erste Operation, die wir behandeln werden, ist das Einfügen neuer Knoten. Beim Einfügen eines neuen Elements müssen zwei Fälle behandelt werden:

  • Der Kopfknoten ist null , das heißt es gibt keine Elemente sind bereits hinzugefügt. In diesem Fall werden wir den neuen Knoten machen wir sowohl als Add Kopf und Schwanz der Liste , da nur ein Knoten
  • Der Kopfknoten ist nicht null , das heißt, es gibt ein oder mehr Elemente , die bereits in die Liste aufgenommen. In diesem Fall wird der bestehende Schweif sollte an den neuen Knotenpunkt und der neu hinzugefügte Knoten wird sich der Schwanz

In beiden oben genannten Fällen zeigt der nextNode für tail auf head

Erstellen wir eine addNode- Methode, die den einzufügenden Wert als Parameter verwendet:

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

Jetzt können wir unserer zirkulären verknüpften Liste einige Zahlen hinzufügen:

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

3.2. Ein Element finden

Die nächste Operation, die wir uns ansehen werden, ist die Suche, um festzustellen, ob ein Element in der Liste vorhanden ist.

Dazu fixieren wir einen Knoten in der Liste (normalerweise den Kopf ) als den aktuellen Knoten und durchlaufen die gesamte Liste mit dem nächsten Knoten dieses Knotens , bis wir das erforderliche Element gefunden haben.

Lassen Sie uns eine neue Methode hinzufügen containsNode , die das nimmt search als 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); return false; } }

Fügen wir nun einige Tests hinzu, um zu überprüfen, ob die oben erstellte Liste die Elemente enthält, die wir hinzugefügt haben, und keine neuen:

@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. Ein Element löschen

Als nächstes betrachten wir den Löschvorgang. Ähnlich wie beim Einfügen haben wir einige Fälle (mit Ausnahme des Falls, in dem die Liste selbst leer ist), die wir betrachten müssen.

  • Das zu löschende Element ist der Kopf selbst . In diesem Fall müssen wir die aktualisieren Kopf als den nächsten Knoten des aktuellen Kopf , und den nächsten Knoten des Schwanzes als neuer Leiter
  • Das zu löschende Element ist ein anderes Element als der Kopf . In diesem Fall müssen wir nur den nächsten Knoten des vorherigen Knotens als den nächsten Knoten des Knotens aktualisieren, der gelöscht werden muss

Wir werden jetzt eine neue Methode deleteNode hinzufügen , die den WertToDelete als Parameter verwendet:

public void deleteNode(int valueToDelete) { Node currentNode = head; if (head != null) { if (currentNode.value == valueToDelete) { head = head.nextNode; tail.nextNode = head; } else { do { Node nextNode = currentNode.nextNode; if (nextNode.value == valueToDelete) { currentNode.nextNode = nextNode.nextNode; break; } currentNode = currentNode.nextNode; } while (currentNode != head); } } }

Fügen wir nun einen einfachen Test hinzu, um zu überprüfen, ob das Löschen in allen Fällen wie erwartet funktioniert:

@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. Durchlaufen der Liste

Wir werden uns in diesem letzten Abschnitt die Durchquerung unserer zirkulären verknüpften Liste ansehen . Ähnlich wie bei den Such- und Löschvorgängen legen wir beim Durchlaufen den aktuellen Knoten als Kopf fest und durchlaufen die gesamte Liste mit dem nächsten Knoten dieses Knotens.

Fügen wir eine neue Methode traverseList hinzu, die die Elemente druckt, die der Liste hinzugefügt werden:

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

Wie wir im obigen Beispiel sehen können, drucken wir während des Durchlaufs einfach den Wert jedes Knotens, bis wir zum Kopfknoten zurückkehren.

4. Fazit

In diesem Tutorial haben wir gesehen, wie eine zirkuläre verknüpfte Liste in Java implementiert wird, und einige der häufigsten Vorgänge untersucht.

Zuerst haben wir gelernt, was genau eine zirkuläre verknüpfte Liste enthält, die einige der häufigsten Merkmale und Unterschiede zu einer herkömmlichen verknüpften Liste enthält. Dann haben wir gesehen, wie Elemente in unsere zirkuläre verknüpfte Listenimplementierung eingefügt, gesucht, gelöscht und durchlaufen werden.

Wie üblich sind alle in diesem Artikel verwendeten Beispiele auf GitHub verfügbar.