Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
0
Notifications Mark All Read
- Login
- Get Prime
0
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
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