Insertion at the nth node of a Circular Linked List
JAVA Program to Insert a Node at the nth node of a Circular Linked List
It is very easy to insert nodes in a circular linked list because every node is pointing towards another node and they are not at a contagious location. No shifting of elements is required for the insertion to happen. For insertion at the nth node of a Circular linked list, the address the (n-1) th node is pointing to should be changed to the address of the new node and the new node should point to the node (n-1)th node was pointing previously pointing towards.
Given below is the description of Insertion at the nth Node of a Circular Linked List
Insertion at nth position in a circular linked list –
- While inserting a new node in the anywhere between the head and the rails we need to consider the three nodes.
- The (n-1)th node must be pointing towards the current nth node, the current nth node must be pointing towards the current (n+1)th node.
- First of all the node (n-1)th address of the next node must be copied in the address part of the new node. Since it is referring to the node we will consider as n+1 after the insertion is successful.
- Change the address of (n-1)th node to the address of the new node.
- In this way, insertion at any position can be done in a circular linked list.
public void insertAfter(int n,int data)
{
int size = calcSize(head);
// Can only insert after 1st position
// Can't insert if position to insert is greater than size of Linked List
if(n < 1 || n > size)
{
System.out.println("Can't insert\n");
}
else
{
Node newNode = new Node(data);
// required to traverse
Node temp = head;
// traverse to the nth node
while(--n > 1)
temp=temp.next;
newNode.next= temp.next;
temp.next = newNode;
}
}
public int calcSize(Node node){
int size = 0;
while(node!=tail){
node = node.next;
size++;
}
return size+1;
}
Algorithm for insertion at nth node of a circular linked list
- addLast(element)
- IF Head==Null
- Head -> newNode
- Tail -> newNode
- newNode->next = Head
- EXIT
- ELSE
- tail->next = newNode
- tail = newNode
- tail->next = Head
- EXIT
Code for insertion at Nth node of a circular Linked List in Java
Method 1
Method 2
Method 1
Run
import java.lang.*;
public class Main {
public static void main(String[] args) {
Main Obj = new Main();
Obj.insertBegin(11);
Obj.insertBegin(22);
Obj.insertAfter(2,77);
Obj.insertAfter(3,88);
Obj.print();
}
public class Node{
int element;
Node next;
public Node(int element) {
this.element = element;
}
}
public Node head = null;
public Node tail = null;
int size=0;
public void insertBegin(int element){
Node newEle = new Node(element);
if(head == null) {
head = newEle;
tail = newEle;
newEle.next = head;
}
else {
newEle.next=head;
head=newEle;
tail.next = head;
}
size++;
}
public void insertAfter(int n,int data)
{
int size = calcSize(head);
// Can only insert after 1st position
// Can't insert if position to insert is greater than size of Linked List
if(n < 1 || n > size)
{
System.out.println("Can't insert\n");
}
if(n==1){
insertBegin(data);
return;
}
Node newNode = new Node(data);
// required to traverse
Node temp = head;
// traverse to the nth node
while(--n > 1)
temp=temp.next;
newNode.next= temp.next;
temp.next = newNode;
}
public int calcSize(Node node){
int size = 0;
while(node!=tail){
node = node.next;
size++;
}
return size+1;
}
public void print() { //print function
Node current = head;
if(head == null) {
System.out.println("List is empty");
}
else {
System.out.println("Nodes of the circular linked list: ");
do{
System.out.print(" "+ current.element);
current = current.next;
}while(current != head);
System.out.println();
}
}
}
Output
Nodes of the circular linked list: 22 77 88 11
Method 2
Run
import java.lang.*;
public class Main {
public static void main(String[] args) {
Main Obj = new Main();
Obj.insertBegin(11);
Obj.insertBegin(22);
Obj.insertBegin(33);
Obj.insertAfterPosition(2,77);
Obj.insertAfterPosition(3,88);
Obj.print();
}
public 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 insertBegin(int element){
Node newEle = new Node(element);
if(head == null) {
head = newEle;
tail = newEle;
newEle.next = head;
newEle.prev=head;
}
else {
head.prev = newEle;
newEle.prev=tail;
newEle.next = head;
tail.next = newEle;
head=newEle;
}
size++;
}
public void insertAfterPosition(int n, int data) {
int len = getLength();
// if insertion position is 0 means entering at start
if (n == 0) {
insertBegin(data);
return;
}
// else insertion will happen somewhere in the middle
if (n < 1 || len < n)
System.out.println("Invalid position");
else {
Node freshNode = new Node(data);
// can remove null assignments also (constructor takes care of these)
// added just for explanation purpose
freshNode.next = null;
freshNode.prev = null;
// nthNode used to traverse the Linked List
Node nthNode = head;
// traverse till the nth node
while (--n > 1) {
nthNode = nthNode.next;
}
Node nextNode = nthNode.next; // (n+1)th node
// assigning (n+1)th node's previous to this new node
nextNode.prev = freshNode;
// new_node's next assigned to (n+1)th node
freshNode.next = nextNode;
// new_node's previous assigned to nth node
freshNode.prev = nthNode;
// assign nth node's next to new_node
nthNode.next = freshNode;
}
}
public int getLength() {
int size = 0;
Node temp=head;
// traverse to the last node each time incrementing the size
while (temp != tail) {
temp = temp.next;
size++;
}
return size;
}
public void print() { //print function
Node current = head;
if(head == null) {
System.out.println("List is empty");
}
else {
do{
System.out.print(" "+ current.element);
current = current.next;
}while(current != head);
System.out.println();
}
}
}
Output
Nodes of circular Linked List : 33 77 88 22 11
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