Question

We are working with a circular linked list that is referenced by a tail reference, i.e., a reference to the last node of the linked list.  There is no head or size information about the linked list.

Node is declared as:

Node {

      int value;

      Node next;

}

There are four parts in this problem. Don't forget to deal with special cases for each part.

1. Write instructions to insert a node newNode at the beginning of the circular linked list.
2. Write instructions to insert a node newNode at the end of the circular linked list.
3. Write instructions to delete the first node of the circular linked list.
4. Write instructions to delete the last node of the circular linked list.

Answer 1

Please upvote of you like the solution

CircularLL.java

public class CircularLL {

        public class Node {
                int data;
                Node next;

        }

        // Declaring headNode and tailNode Nodes 
        public Node headNode = null;
        public Node tailNode = null;

        // method to add Nodes at end of CLL
        public void addToLastOfCLL(int data) {
                // Creating new node
                Node newNode = new Node();
                newNode.data = data;
                // Checking if CLL is empty or not
                if (headNode == null) {
                        // If CLL is empty, both headNode and tailNode would point to new node.
                        headNode = newNode;
                        tailNode = newNode;
                        newNode.next = headNode;
                } else {
                        // tailNode will point to new node.
                        tailNode.next = newNode;
                        // New node will become new tailNode.
                        tailNode = newNode;
                        // Since, it is circular linked list tailNode will point to headNode.
                        tailNode.next = headNode;
                }
        }

         //This function will add the new node at the end of the list.  
    public void addAtStartOfCLL(int data){  
        //Create new node  
        Node newNode = new Node();
        newNode.data = data;
        //Checks if the list is empty.  
        if(headNode == null) {  
             //If list is empty, both headNode and tailNode would point to new node.  
            headNode = newNode;  
            tailNode = newNode;  
            newNode.next = headNode;  
        }  
        else {  
            //Store data into temporary node  
            Node temp = headNode;  
            //New node will point to temp as next node  
            newNode.next = temp;  
            //New node will be the headNode node  
            headNode = newNode;  
            //Since, it is circular linked list tailNode will point to headNode.  
            tailNode.next = headNode;  
        }  
    }  
        //Deletes node from the beginning of the list  
    public void deleteFromStartOfCLL() {  
        //Checks whether list is empty  
        if(headNode == null) {  
            return;  
        }  
        else {  
            //Checks whether contain only one element  
            //If not, headNode will point to next element in the list and tailNode will point to new headNode.  
            if(headNode != tailNode ) {  
                headNode = headNode.next;  
                tailNode.next = headNode;  
            }  
            //If the list contains only one element   
            //then it will remove it and both headNode and tailNode will point to null  
            else {  
                headNode = tailNode = null;  
            }  
        }  
    }  
      

  //Deletes node from end of the list  
    public void deleteFromEndOfCLL() {  
        //Checks whether list is empty  
        if(headNode == null) {  
            return;  
        }  
        else {  
            //Checks whether contain only one element  
            if(headNode != tailNode ) {  
                Node currentNode = headNode;  
                //Loop will iterate till the second last element as currentNode.next is pointing to tailNode  
                while(currentNode.next != tailNode) {  
                    currentNode = currentNode.next;  
                }  
                //Second last element will be new tailNode  
                tailNode = currentNode;  
                //tailNode will point to headNode as it is a circular linked list  
                tailNode.next = headNode;  
            }  
            //If the list contains only one element  
            //Then it will remove it and both headNode and tailNode will point to null  
            else {  
                headNode = tailNode = null;  
            }  
        }
    }


        // Displays all the nodes in the list
        public void printCLL() {
                
                Node currentNode = headNode;
                
                if (headNode == null) {
                        System.out.println("List is empty");
                } else {
                        System.out.println("Nodes of the circular linked list: ");
                        
                        do {
                                // Prints each node by incrementing pointer.
                                System.out.print(" " + currentNode.data);
                                currentNode = currentNode.next;
                                
                        } while (!currentNode.equals(headNode));
                        System.out.println();
                }
        }

        public static void main(String[] args) {
                CircularLL cl = new CircularLL();
                // Adds data to the list
                cl.addAtStartOfCLL(10);
                cl.addToLastOfCLL(20);
                cl.addToLastOfCLL(30);
                cl.addToLastOfCLL(40);
                cl.addToLastOfCLL(50);
                cl.addToLastOfCLL(60);
                
                
                
                cl.deleteFromStartOfCLL();
                cl.deleteFromEndOfCLL();
                
                cl.printCLL();
        }
}

Output without calling delete mehods

Output after calling calling delete methods

End of Solution