BAEL-3453 - Circular linked list Java implementation

radhe-sravan · radhe-sravan · commit 9dc001ae337b · 2019-11-23T16:50:26.000+05:30
diff --git a/data-structures/src/main/java/com/baeldung/list/CircularLinkedList.java b/data-structures/src/main/java/com/baeldung/list/CircularLinkedList.java
@@ -0,0 +1,102 @@
+package com.baeldung.list;
+
+public class CircularLinkedList {
+
+    Node head = null;
+    Node tail = null;
+
+    public void addNode(int value) {
+
+        Node newNode = new Node(value);
+
+        // If no elements are present, make the newly addNodeed node as head
+        if (head == null) {
+            head = newNode;
+        }
+        // If there are elements already present, the existing tail should point to new node
+        else {
+            tail.nextNode = newNode;
+        }
+
+        // Irrespective of whether or not elements are addNodeed, assign the
+        // tail to newNode and the nextNode for tail as head
+        tail = newNode;
+        tail.nextNode = head;
+    }
+
+    public boolean containsNode(int searchValue) {
+
+        // Start traversing from the head
+        Node currentNode = head;
+
+        // If list is empty no need of traversal and can return false
+        if (head == null) {
+            return false;
+        } else {
+            do {
+                // Compares the search value with each node value present in the list
+                if (currentNode.value == searchValue) {
+                    return true;
+                }
+                currentNode = currentNode.nextNode;
+            } while (currentNode != head);
+            return false;
+        }
+    }
+
+    public void deleteNode(int valueToDelete) {
+
+        // Start traversing from the head
+        Node currentNode = head;
+
+        // If list is non empty
+        if (head != null) {
+            // If the node to delete is the head node itself,
+            // update the head as the next node of current head
+            // and the nextNode of tail as new head
+            if (currentNode.value == valueToDelete) {
+                head = head.nextNode;
+                tail.nextNode = head;
+                currentNode = null;
+            } else {
+                do {
+                    // Fetch the next node of current node
+                    Node nextNode = currentNode.nextNode;
+                    // If the value to delete matches the next node's value,
+                    // update the next node of current node as the next node of present next node
+                    if (nextNode.value == valueToDelete) {
+                        currentNode.nextNode = nextNode.nextNode;
+                        nextNode = null;
+                        break;
+                    }
+                    currentNode = currentNode.nextNode;
+                } while (currentNode != head);
+            }
+        }
+    }
+
+    public void traverseList() {
+
+        // Start traversing from the head
+        Node currentNode = head;
+
+        if (head != null) {
+            do {
+                System.out.print(currentNode.value + " ");
+                currentNode = currentNode.nextNode;
+            } while (currentNode != head);
+        }
+    }
+
+}
+
+class Node {
+
+    int value;
+    Node nextNode;
+
+    public Node(int value) {
+        this.value = value;
+    }
+
+}
diff --git a/data-structures/src/test/java/com/baeldung/list/CircularLinkedListUnitTest.java b/data-structures/src/test/java/com/baeldung/list/CircularLinkedListUnitTest.java
@@ -0,0 +1,60 @@
+package com.baeldung.list;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import org.junit.Test;
+
+public class CircularLinkedListUnitTest {
+
+    @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));
+    }
+    
+    @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));  
+    }
+
+    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;
+    }
+
+}
