In this tutorial, we will see all about the insert operation in a circular linked list. In the insert operation, we will add a new node to the circular linked list at any position.
In a Circular Linked List, we can insert a node at the following positions:
At the beginning of the list.
At the end of the list.
At the specific position of the list.
1. Insert a node at the beginning of the list.
To insert a new node at the beginning or front position in the list, we need to follow these steps:
- Create a newNode with given value.
- Check whether list is Empty (head == NULL)
- If it is Empty then, set head = newNode and newNode→next = head .
- If it is Not Empty then, define a Node pointer 'temp' and initialize with 'head'.
- Keep moving the 'temp' to its next node until it reaches to the last node (until 'temp → next == head').
- Set 'newNode → next =head', 'head = newNode' and 'temp → next = head'.
In the below given example we will see how to insert a new node in the beginning or front the linked list.
//Java Program to insert a new node at the beginning of List
public class InsertAtBeginningInCLL {
// Function to insert a new node at the beginning
static Node insertAtBeginning(Node last, int value) {
// Create a node
Node newNode = new Node(value);
// If the list is empty
// Make the new node point to itself and set it as last
if (last == null) {
newNode.next = newNode;
return newNode;
}
// If the list is not empty
// Insert the new node at the beginning of the list
newNode.next = last.next;
last.next = newNode;
return last;
}
// Function to print the list
static void printList(Node last) {
// Returns if list is empty
if (last == null)
return;
Node head = last.next;
while (true) {
System.out.print(head.data + " ");
head = head.next;
if (head == last.next)
break;
}
System.out.println();
}
public static void main(String[] args) {
// Create a circular linked list
Node first = new Node(20);
first.next = new Node(30);
first.next.next = new Node(40);
first.next.next.next = new Node(50);
Node last = first.next.next.next;
last.next = first;
System.out.println("Original list: ");
printList(last);
// Inserting 10 at the beginning
last = insertAtBeginning(last, 10);
System.out.println("List after inserting 10 at the beginning: ");
printList(last);
}
} Output
Original list: 20 30 40 50 List after inserting 10 at the beginning: 10 20 30 40 50
2. Insert a node at the end of the circular linked list.
To insert a new node at the end or last position in the circular linked list, we need to follow these steps:
- Create a newNode with given value.
- Check whether list is Empty (head == NULL).
- If it is Empty then, set head = newNode and newNode → next = head.
- If it is Not Empty then, define a node pointer temp and initialize with head.
- Keep moving the temp to its next node until it reaches to the last node in the list (until temp → next == head).
- Set temp → next = newNode and newNode → next = head.
In the below given example we will see how to insert a new node at the end of the circular linked list.
//Java Program to Insert a Node at the End of List
public class InsertAtEndInCLL {
// Function to insert a node at the end
static Node insertAtEnd(Node tail, int value) {
// Create a new node
Node newNode = new Node(value);
if (tail == null) {
// If the list is empty, initialize it with the
// new node
tail = newNode;
newNode.next = newNode;
} else {
// Insert new node after the current tail and
// update the tail pointer
newNode.next = tail.next;
tail.next = newNode;
tail = newNode;
}
return tail;
}
// Function to print the list
static void printList(Node last) {
// Returns if list is empty
if (last == null)
return;
Node head = last.next;
while (true) {
System.out.print(head.data + " ");
head = head.next;
if (head == last.next)
break;
}
System.out.println();
}
public static void main(String[] args) {
// Create a circular linked list
Node first = new Node(20);
first.next = new Node(30);
first.next.next = new Node(40);
first.next.next.next = new Node(50);
Node last = first.next.next.next;
last.next = first;
System.out.println("Original list: ");
printList(last);
// Inserting 80 at the end of the list
last = insertAtEnd(last, 80);
System.out.println("List after inserting 80 at the end of the list: ");
printList(last);
}
} Output
Original list: 20 30 40 50 List after inserting 80 at the end of the list: 20 30 40 50 80
3. Insert a node at a specific position of the list
To insert a new node at the specific position of the circular linked list, we need to follow the given steps.
- Create a newNode with given value.
- Check whether list is Empty (head == NULL)
- If it is Empty then, set head = newNode and newNode → next = head.
- If it is Not Empty then, define a node pointer temp and initialize with head.
- Keep moving the temp to its next node until it reaches to the node after which we want to insert the newNode (until temp1 → data is equal to location, here location is the node value after which we want to insert the newNode).
- Every time check whether temp is reached to the last node or not. If it is reached to last node then display 'Given node is not found in the list!!! Insertion not possible!!!' and terminate the function. Otherwise move the temp to next node.
- If temp is reached to the exact node after which we want to insert the newNode then check whether it is last node (temp → next == head).
- If temp is last node then set temp → next = newNode and newNode → next = head.
- If temp is not last node then set newNode → next = temp → next and temp → next = newNode.
In the below given example we will see how to insert a new node in the specific position in the circular linked list.
// Java Program to Insert a Node At a Specific Position in List
public class InsertAtSpecificPositionInCLL {
// Function to insert a node at a specific position in the list
static Node insertAtPosition(Node last, int data, int position) {
if (last == null) {
// If the list is empty
if (position != 1) {
System.out.println("Invalid position!");
return last;
}
// Create a new node and make it point to itself
Node newNode = new Node(data);
last = newNode;
last.next = last;
return last;
}
// Create a new node with the given data
Node newNode = new Node(data);
// currNode will point to head initially
Node currNode = last.next;
if (position == 1) {
// Insert at the beginning
newNode.next = currNode;
last.next = newNode;
return last;
}
// Traverse the list to find the insertion point
for (int i = 1; i < position - 1; ++i) {
currNode = currNode.next;
// If position is out of bounds
if (currNode == last.next) {
System.out.println("Invalid position!");
return last;
}
}
// Insert the new node at the given position
newNode.next = currNode.next;
currNode.next = newNode;
// Update last if the new node is inserted at the end
if (currNode == last)
last = newNode;
return last;
}
// Function to print the list
static void printList(Node last) {
// Returns if list is empty
if (last == null)
return;
Node head = last.next;
while (true) {
System.out.print(head.data + " ");
head = head.next;
if (head == last.next)
break;
}
System.out.println();
}
public static void main(String[] args) {
// Create a circular linked list
Node first = new Node(20);
first.next = new Node(30);
first.next.next = new Node(40);
first.next.next.next = new Node(50);
Node last = first.next.next.next;
last.next = first;
System.out.print("Original list: ");
printList(last);
// Insert elements at specific positions
int element = 99, position = 3;
last = insertAtPosition(last, element, position);
System.out.print("List after insertions: ");
printList(last);
}
} Output
Original list: 20 30 40 50 List after insertions: 20 30 99 40 50