Circular Linked List Insertion in the middle in Java
February 21, 2023
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++;
}
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
Login/Signup to comment