Circular Linked List Insertion in the middle in Java

Java Program to Insert in the middle in Circular Linked List

We will be looking at a couple of methods to Do Insertion in the middle of a Circular Linked List in Java.

First we need to find the middle of the linked list then insert a node.

insert in the middle of circular linked list

Approaches Discussed

  • Approach 1: Using Size variable to keep track of the size of Circular Linked List
  • Approach 2: Using Function to calculate size of Circular Linked List at any point in time
Circular Linked List Insertion in the middle in Java
public void insertMiddle(int data) {
        Node newNode = new Node(data);

        // if the LL was empty
        if(head == null){
            // use insert function to insert
            insert(data);
            return;
        }

        // otherwise
        Node temp = head;

        // find correct insertion position for middle
        int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;

        // Unique case when there is only one node in CLL
        // we will be inserting at the last,
        // inserting 2nd node at the last
        // Example size = 1 will result in mid = 1 so entering after 1st node
        // where size itself is 1 so entering last node
        if(mid == size){
            newNode.next = head;
            head.next = newNode;
            return;
        }
        // traverse to current mid position
        while(--mid > 0){
            temp = temp.next;
        }

        newNode.next = temp.next;
        temp.next = newNode;
        size++;
    }

Code for Sorted Insert In Circular Linked List in JAVA

Run
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Main Obj = new Main();
        Obj.sortedInsert(10);
        Obj.sortedInsert(20);
        Obj.sortedInsert(30);
        Obj.sortedInsert(40);
        Obj.sortedInsert(50);
        Obj.sortedInsert(60);

        Obj.print();

        System.out.println("Linked List after insertion : ");
        Obj.sortedInsert(33);
        Obj.print();
    }
    public static class Node{
        int element;
        Node next;

        public Node(int element) {
            this.element = element;
        }
    }
    int cnt;
    static Node list1, list2;
    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("Circular Linked List is");
            do{
                //Prints each node by incrementing pointer.
                System.out.print(" "+ current.element);
                current = current.next;
            }while(current != head);
            System.out.println("\n");
        }
    }

    void sortedInsert(int n)
    {
        Node nextNode=new Node(n);
        Node thisNode = head;
        if (thisNode == null)
        {
            nextNode.next = nextNode;
            head = nextNode;
        }
        else if (thisNode.element >= nextNode.element)
        {
            for (int i=0; thisNode.next != head; i++)
                thisNode = thisNode.next;
            thisNode.next = nextNode;
            nextNode.next = head;
            head = nextNode;
        }
        else
        {
            while (thisNode.next != head && thisNode.next.element < nextNode.element)
                thisNode = thisNode.next;
            nextNode.next = thisNode.next;
            thisNode.next = nextNode;
        }
    }
}

Output

Circular Linked List is
 10 20 30 40 50 60

Linked List after insertion : 
Circular Linked List is
 10 20 30 33 40 50 60
Run
import java.lang.*;
public class Main {
    public static void main(String[] args) {
        Main Obj = new Main();
        Obj.insert(10);
        Obj.insert(20);
        Obj.insert(30);
        Obj.insert(40);
        Obj.insert(50);
        Obj.insert(60);

        System.out.println("Original List");
        Obj.print();

        Obj.insertMiddle(70);
        System.out.println("List after insertion");
        Obj.print();
    }
    class Node{
        int element;
        Node next;
        Node prev;

        public Node(int element) {
            this.element = element;
        }
    }

    public Node head = null;
    public Node tail = null;
    int size=0;

    public void insert(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        newNode.prev = null;

        if (head != null)
            head.prev = newNode;

        head = newNode;
    }

    public void insertMiddle(int data) {
        Node newNode = new Node(data);

        // if the LL was empty
        if (head == null) {
            // using insert function to insert at start
            insert(data);
            return;
        }

        // otherwise
        // find correct insertion position for middle
        int size = findSize();
        int mid = (size % 2 == 0) ? (size / 2) : (size + 1) / 2;

        // will only happen when there is one node in Doubly Linked List
        // we will have to insert at the last,
        // inserting 2nd node at the last
        // Example size = 1 will result in mid = 1 so entering after 1st node
        // where size itself is 1 so entering last node
        if (mid == size) {
            newNode.next = null;
            newNode.prev = head;
            head.next = newNode;
            size++;
            return;
        }

        Node temp = head;
        // traverse to current mid position
        while (--mid > 0) {
            temp = temp.next;
        }

        // (mid+1)th node prev to this newNode
        (temp.next).prev = newNode;
        // newNode's prev to this current middle node
        newNode.prev = temp;
        // newNode's next to (mid+1)th node
        newNode.next = temp.next;
        // current mid node's next becomes this newNode
        temp.next = newNode;
        size++;
    }

    public int findSize() {
        int size = 0;

        Node node = head;

        while (node != null) {
            node = node.next;
            size++;
        }
        return size;
    }

    public void print() {

        Node node = head;
        Node end = null;

        while (node != null) {
            System.out.print(node.element + " ");
            end = node;
            node = node.next;
        }
        System.out.println();
    }
}

Output

Original List
60 50 40 30 20 10 
List after insertion
60 50 40 70 30 20 10 

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Circular Linked List

  • Introduction to Circular Linked List
    Click Here
  • Circular Linked List Applications
    Click Here
  • Circular Linked List in –
    C | C++ | Java
  • Insertion in Circular Linked List –
    C | C++ | Java
  • Insertion at the beginning–
    C | C++ | Java
  • Insertion at the end –
    C | C++ | Java
  • Insertion at nth position –
    C | C++ | Java
  • Deletion in Circular Linked List –
    C | C++ | Java
  • Deletion from beginning in Circular Linked List –
    C | C++ | Java
  • Deletion from nth position in Circular Linked List –
  • Deletion from end in Circular Linked List –
    C | C++ | Java
  • Insertion and Deletion in Circular Linked List – C | C++ | Java
  • Split a Circular Linked List in two halves –
    C | C++ | Java
  • Count nodes in Circular Linked List –
    C | C++ | Java
  • Sorted Insert In Circular Linked List –
    C | C++ | Java
  • Insertion in the middle in Circular Linked List –
    C | C++ | Java

Circular Linked List