Circular Linked List Insertion in the middle in Java

Java Program to Insert in the middle in Circular Linked List

Write a program to Insert in the middle in a Circular Linked List in Java

insert

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
Run
import java.lang.*;

class Main {
    Node head;
    int size = 0;
    // Node Class
    class Node{
        int data;
        Node next, prev;

        Node(int x) // parameterized constructor
        {
            data = x;
            next = null;
            prev = null;
        }
    }
    public void insert(int data)
    {
        Node newNode = new Node(data);

        // if its the first node being entered
        if(head == null){
            head = newNode;
            head.next = head;
            size++;
            return;
        }

        // if Circular Linked List had >=1 node
        Node curr = head;

        // traverse till last node in Circular Linked List
        while(curr.next != head){
            curr = curr.next;
        }
        curr.next = newNode;
        newNode.next = head;
        head = newNode;
        size++;
    }
    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++;
    }

    public void display()
    {
        // if there are no node in LL
        if(head == null)
            return;
        System.out.print("Linked List: ");
        Node temp = head;

        //need to take care of circular structure of LL
        do{
            System.out.print(temp.data + " ");
            temp = temp.next;

        }while(temp!=head);
        System.out.println();
    }


    public static void main(String args[])
    {
        Main ll = new Main();

        ll.insert(500);
        ll.insert(100);

        ll.display();

        ll.insertMiddle(200);
        ll.display();

        ll.insertMiddle(400);
        ll.display();

        ll.insertMiddle(300);
        ll.display();
    }


}

Output

Linked List: 100 500 
Linked List: 100 200 500 
Linked List: 100 200 400 500 
Linked List: 100 200 300 400 500
Run
import java.lang.*;

class Main {
    Node head;
    // Node Class
    class Node{
        int data;
        Node next, prev;

        Node(int x) // parameterized constructor
        {
            data = x;
            next = null;
            prev = null;
        }
    }
    public void insert(int data)
    {
        Node newNode = new Node(data);

        // if its the first node being entered
        if(head == null){
            head = newNode;
            head.next = head;
            return;
        }

        // if Circular Linked List had >=1 node
        Node curr = head;

        // traverse till last node in Circular Linked List
        while(curr.next != head){
            curr = curr.next;
        }
        curr.next = newNode;
        newNode.next = head;
        head = newNode;
    }
    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;
        int size = calcSize();


        // 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;
    }

    public int calcSize(){
        int size = 0;

        Node node = head;
        do{
            node = node.next;
            size++;

        }while(node!=head);
        return size;
    }
    public void display()
    {
        // if there are no node in LL
        if(head == null)
            return;
        System.out.print("Linked List: ");
        Node temp = head;

        //need to take care of circular structure of LL
        do{
            System.out.print(temp.data + " ");
            temp = temp.next;

        }while(temp!=head);
        System.out.println();
    }


    public static void main(String args[])
    {
        Main ll = new Main();

        ll.insert(500);
        ll.insert(100);

        ll.display();

        ll.insertMiddle(200);
        ll.display();

        ll.insertMiddle(400);
        ll.display();

        ll.insertMiddle(300);
        ll.display();
    }


}

Output

Linked List: 100 500 
Linked List: 100 200 500 
Linked List: 100 200 400 500 
Linked List: 100 200 300 400 500

Circular Linked List

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