Circular Linked List Brush Up and Programming Technique

Circular lists are like singly linked lists, except that the last node contains a  pointer back to the first node rather than the null pointer. From any point in such a list, it is possible to reach any other point in the list. If we begin at a given node and travel the entire list, we ultimately end up at the starting point.


Why do we need Circular Linked List ?
In Singly Linked List traversing is very tough and time consuming.Suppose we are at last node and we have to come at first node . To do this we will have traverse the whole single linked list back whereas in the circular linked list moving to next node form the last node takes us to the first node.
What to change in the code of linked list to make it a circular linked list. ?
Instead of pointing the last node to null we have to point the last node to root(first)  node.

public void insert_at_end(int d)
    {
    newnode = new Node(d);
    if(root==null)
    {
     root=newnode;
     newnode.next=root; // connect the last node pointer to the first node
    }
    else 
    {
    temp=root;
    while(temp.next!=root)
    {
    temp=temp.next;
    }
    temp.next=newnode;
    newnode.next=root;//connect the last node pointer to the first node
    }
    }

Deletion in a Circular Linked List:
Deletion in a  circular linked list is very tricky unlike single linked list . Here we have to take care of every part separately .
Case 1: If we have to delete the root element :
Then we will create a temp node and assign the root.next to temp node and and then assign the next node  data to the root node using temp node and then point the root node to the next to next node.

if(root.data==num)
    {
       Node temp;
       temp=root.next;
       root.data=temp.data;
       root.next=temp.next;
    }

if you are not able to understand what is happening in the above code then please see the deletion part of this post.

Case 2: If we have to delete the element other than the  root node

Node del_node=root;
while(del_node.next!=root  )
{
if(del_node.next.data==num)
{
del_node.next=del_node.next.next;
}
del_node=del_node.next;
}

Implementation of Circular Linked List Program:

class Node 
{
    int data ;
    Node next;
    Node(int d)
    {
        data =d;
        next=null;
    }
}
class LinkedList
{
    Node root=null;
    Node newnode;
    Node temp;
    /*function to insert the element at the end */
    public void insert_at_end(int d)
    {
    newnode = new Node(d);
    //if list is empty 
    if(root==null)
    {
        root=newnode;
        newnode.next=root;
        
    }
    // if list is not empty
    else 
    {
        temp=root;
        while(temp.next!=root)
        {
            temp=temp.next;
        }
        temp.next=newnode;
        newnode.next=root;
    }
    }
    
    /*function to delete the element   */
    public void delete(int num)
    {
    //if the list is empty
    if(root==null)
    {
    System.out.println("list is empty");
    return ;
    }
            
    /*if num to be deleted is root  */
    if(root.data==num)
    {
       Node temp;
       temp=root.next;
       root.data=temp.data;
       root.next=temp.next;
    }
    
    /*if the number to be deleted is other than the  root element   */
    else
    {
    Node del_node=root;
    while(del_node.next!=root  )
    {
        if(del_node.next.data==num)
        {
         del_node.next=del_node.next.next;
        }
     del_node=del_node.next;
    }
    }
    }
    
    /*function to display the list   */
    public void display()
    {temp=root;
     if(root!=null)
     {  
    do{
     System.out.print(temp.data+"->");
     temp=temp.next;
     }while(temp!=root);
    }
    }
}
 
    public class Main {
    public static void main (String[] args)     {
    LinkedList list=new LinkedList();
    list.insert_at_end(9);
    list.insert_at_end(1);
    list.insert_at_end(3);
    list.insert_at_end(2);
    System.out.println("Traversing the linked List");
    list.display();
    list.delete(1);
    System.out.println("\nTraversing linked list after deletion of node");
    list.display();
    
  }
 
}

Time Complexity of deletion part : O(n).

Test Cases for the deletion part of the list :
1.List may be empty in that case we have nothing to delete .
2.List may contain the duplicate element . Above program delete the first duplicate element in the list.
3.Element may not be there in list.In that case above program does not delete anything and print the list as it is.

Please comment if you find any mistake .