Insertion in Circular Linked List in java

insertion in circular linked list

Insertion in circular linked in Java  programming?

 The circular linked list is another type of linked list. The node is an element of the list, and it has two parts that are, data and next. Data represents the data stored in the node and next is the pointer that will point to next node. Head will point to the first element of the list, and tail will also point to the first element in the list.. We can perform three different types of insertion in circular linked list, these different types of insertion are:-

  • Insertion at beginning .
  • Insertion at specific position .
  • Insertion at end .

In this article, we will discuss what are different types of insertion and how to perform them .

ALGORITHM FOR INSERTION AT BEGINING:

  • Make a Node class which represents a node in the list. It consists two properties data and next which will point to the next node.
  • Create another class for creating the circular linked list and it has two nodes: head and tail. It has two methods: addAtStart() and show() .
  • addAtStart() will add the node to the beginning of the list:
    •  first checks whether the head is null (empty list), then it will make the node as the head.
    • Both head and tail will point to newly added node.
    • If the list is not empty, then the newly added node will become the new head, and it will point to previous head.

Insertion at begining Java code :

public class InsertAtstart {  
    //node declaration.  
        public class Node{  
            int data;  
            Node next;  
            public Node(int data) {  
                this.data = data;  
            }  
        }  
  
        //Declaring head and tail pointer as null.  
        public Node head = null;  
        public Node tail = null;  
  
        //add new node at the end of the list.  
        public void addAtStart(int data){  
            //Create new node  
            Node newNode = new Node(data);  
            //Checks if the list is empty.  
            if(head == null) {  
                 
                head = newNode;  
                tail = newNode;  
                newNode.next = head;  
            }  
            else {  
                
                Node temp = head;  
                
                newNode.next = temp;  
                
                head = newNode;  
                //Since, it is circular linked list tail will point to head.  
                tail.next = head;  
            }  
        }  
  
        //Displays all the nodes in the list  
        public void show() {  
            Node current = head;  
            if(head == null) {  
                System.out.println(“empty list”);  
            }  
            else {  
                System.out.println(“”)
                 do{  
                    
                    System.out.print(” “current.data);  
                    current = current.next;  
                }while(current != head);  
                System.out.println();  
            }  
        }  
  
        public static void main(String[] args) {  
            InsertAtStart cl = new InsertAtStart();  
  
            //Adding 2 to the list  
            cl.addAtStart(2);  
            cl.show();  
            //Adding 4 to the list  
            cl.addAtStart(4);  
            cl.show();  
            //Adding 6 to the list  
            cl.addAtStart(6);  
            cl.show();  
            //Adding 8 to the list  
            cl.addAtStart(8);  
            cl.show();  
        }  
}  
OUTPUT

2

4 2

6 4 2

8 6 4 2

ALGORITHM FOR INSERTION AT END:

  • Make a Node class which represents a node in the list. It consist two properties data and next which will point to the next node.
  • Make another class for creating the circular linked list and it has two nodes: head and tail. It has two methods: addAtEnd() and show() .
  • addAtEnd() will add the node to the end of the list:
    • It first checks whether the head is null (empty list), then it will add the node as the head.
    • Both head and tail will point to the newly added node.
    • If the list is not empty, then the newly added node will become the new tail, and previous tail will point to new node as its next node. The new tail will point to the head.

Insertion at End :

public class InsertAtEnd {    
    // node of list.    
        public class Node{    
            int data;    
            Node next;    
            public Node(int data) {    
                this.data = data;    
            }    
        }    
            
        
        public Node head = null;    
        public Node tail = null;    
            
        //This will add the new node at the end .    
        public void addAtEnd(int data){    
            //Create new node    
            Node newNode = new Node(data);    
            
            if(head == null) {    
                 //If list is empty, both head and tail would point to new node.    
                head = newNode;    
                tail = newNode;    
                newNode.next = head;    
            }    
            else {    
                
                tail.next = newNode;    
               
                tail = newNode;    
                //Since, it is circular linked list tail will points to head.    
                tail.next = head;    
            }    
        }    
            
        //Displays all the nodes in the list    
        public void show() {    
            Node current = head;    
            if(head == null) {    
                System.out.println(“empty list”);    
            }    
            else {    
                System.out.println(“”);    
                 do{    
                    
                    System.out.print(” “current.data);    
                    current = current.next;    
                }while(current != head);    
                System.out.println();    
            }    
        }    
            
        public static void main(String[] args) {    
            InsertAtEnd a = new InsertAtEnd();    
                
            //Adding 2 to the list    
            a.addAtEnd(2);    
            a.show();    
            //Adding 4 to the list    
            a.addAtEnd(4);    
            a.show();    
            //Adding 6 to the list    
            a.addAtEnd(6);    
            a.show();    
            //Adding 8 to the list    
            a.addAtEnd(8);    
            a.show();    
        }    
}    
OUTPUT:

2

2 4

2 4 6

2 4 6 8

ALGORITHM FOR INSERTION AT SPECIFIC POSITION:

  • START
  • Make a node class 
  • Store the data to create linked list.
  • Store the element to be at any position of list.
  • Store position and start counter.
  • Check if head is null not possible else goto step 6.
  • Store data at specific position.
  •  Create new link for data stored and point towards next position.
  • Change the  address of next and previous node where new node is made.
  • END

Insertion at specific position :


class prepinsta {
    //  Node
    static class Node {
        public int data;
        public Node nextNode;

        
        public Node(int data) {
            this.data = data;

        }
    }

    
    static Node GetNode(int data) {
        return new Node(data);
    }

    // function to insert a Node at specific position
    static Node Insert(Node headNodeint positionint data) {
        Node head = headNode;
        if (position < 1)
            System.out.print(“Wrong position”);

        
        if (position == 1) {
            Node newNode = new Node(data);
            newNode.nextNode = headNode;
            head = newNode;
        } else {
            while (position– != 0) {
                if (position == 1) {
                    // adding Node at required position
                    Node newNode = GetNode(data);


                    newNode.nextNode = headNode.nextNode;

                    
                    headNode.nextNode = newNode;
                    break;
                }
                headNode = headNode.nextNode;
            }
            if (position != 1)
                System.out.print(“Out of range”);
        }
        return head;
    }

    static void show(Node node) {
        while (node != null) {
            System.out.print(node.data);
            node = node.nextNode;
            if (node != null)
                System.out.print(“,”);
        }
        System.out.println();
    }

    
    public static void main(String[] args) {
        Node head = GetNode(2);
        head.nextNode = GetNode(4);
        head.nextNode.nextNode = GetNode(6);
        head.nextNode.nextNode.nextNode = GetNode(8);

        System.out.print(“before insertion: “);
        show(head);

        int data = 3, pos = 2;
        head = Insert(head, pos, data);
        System.out.print(“Linked list after” + ” insertion of 3 at position 2: “);
        show(head);

        
    }
}


Output :

before insertion

2 4 6 8 

Linked list after insertion of 3 at position 2:

2 3 4 6 8