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.
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
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
Method 1
Method 2
Method 1
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
Method 2
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
Circular Linked List
- Introduction to Circular Linked List
Click Here - Circular Linked List Applications
Click Here - Circular Linked List in –
- Insertion in Circular Linked List –
- Insertion at the beginning–
- Insertion at the end –
- Insertion at nth position –
- Deletion in Circular Linked List –
- Deletion from beginning in Circular Linked List –
- Deletion from nth position in Circular Linked List –
- Deletion from end in Circular Linked List –
- Insertion and Deletion in Circular Linked List – C | C++ | Java
- Split a Circular Linked List in two halves –
- Count nodes in Circular Linked List –
- Sorted Insert In Circular Linked List –
- Insertion in the middle in Circular Linked List –
Circular Linked List
- Introduction to Circular Linked List
- Circular Linked List Applications
- Circular Linked List in – C | C++ | Java
- Insertion in Circular Linked List – C | C++ | Java
- Deletion in Circular Linked List – C | C++ | Java
- Insertion and Deletion in a 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
Login/Signup to comment