Insertion at the nth node of a Circular Linked List

July 9, 2020

Insertion of a New Node at the nth position of a circular linked list

JAVA Program to Insert a Node at the nth node of a Circular Linked List

It is very easy to insert nodes in a circular linked list because every node is pointing towards another node and they are not at a contagious location. No shifting of elements is required for the insertion to happen. For insertion at the nth node of a Circular linked list, the address the (n-1) th node is pointing to should be changed to the address of the new node and the new node should point to the node (n-1)th node was pointing previously pointing towards.

Data Structures

Given below is the description of Insertion at the nth Node of a Circular Linked List 

Insertion at nth position in a circular linked list –

  • While inserting a new node in the anywhere between the head and the rails we need to consider the three nodes.
  • The (n-1)th node must be pointing towards the current nth node, the current nth node must be pointing towards the current (n+1)th node.
  • First of all the node (n-1)th address of the next node must be copied in the address part of the new node. Since it is referring to the node we will consider as n+1 after the insertion is successful.
  • Change the address of (n-1)th node to the address of the new node.
  • In this way, insertion at any position can be done in a circular linked list.

To add a element at the nth Position of a Circular Linked List following Algorithm is to be followed

  • addLast(element)
  • IF Head==Null
    • Head -> newNode
    • Tail -> newNode
    • newNode->next = Head
    • EXIT
  • ELSE
    • tail->next = newNode
    • tail = newNode
    • tail->next = Head
    • EXIT

Code for insertion in JAVA

public class Main {             
    public static void main(String[] args) {  
        Main Obj = new Main();  
        Obj.addFirst(1);  
        Obj.print();  
        Obj.addFirst(2);  
        Obj.print();  
        Obj.addFirst(3);  
        Obj.print();  
        Obj.addFirst(4);  
        Obj.print();  
        } 
    public class Node{  
        int element;  
        Node next; 
        
        public Node(int element) {  
            this.element = element;  
        }  
    } 

    public Node head = null;  
    public Node tail = null;
    
    public void print() {  
        Node current = head;    
        if(head == null) {  
            System.out.println("Empty List");  
        }  
        else {  
            System.out.println("After adding node at the beginning");  
            do{     
                //Prints each node by incrementing pointer.  
                System.out.print(" "+ current.element);  
                current = current.next;  
            }while(current != head);  
                        System.out.println();  
                    }  
                }
                
    public void addFirst(int data){  
        Node newNode = new Node(data);  
        if(head == null) {  
            head = newNode;  
            tail = newNode;  
            newNode.next = head;  
        }  
        else {  
            Node temp = head;  
            newNode.next = temp;  
            head = newNode;  
            tail.next = head;  
        }  
    }    
}    

After adding node at the beginning
 1
After adding node at the beginning
 2 1
After adding node at the beginning
 3 2 1
After adding node at the beginning
 4 3 2 1