Insertion at the End in Circular Linked List in Java
Java Program for Insertion at the end in Circular Linked List
Insertion at the end in Circular Linked List in Java is one of the most common operations performed on linked lists. It allows us to add a new node after the last node, while maintaining the circular structure of the list.
Understanding this concept is essential for beginners learning Data Structures and Algorithms in Java, especially when working with dynamic data where the number of elements is not fixed.
Insertion at the end in Circular Linked List in Java
Understanding Insertion at the End in Circular Linked List
Insertion at the end means adding a new node after the last node and then updating the last node’s next pointer to point to the head, maintaining the circular structure.
Insertion at the end in a circular singly linked list means adding a new node after the current last node, while maintaining the circular structure.
After insertion:
- The new node becomes the new last node.
- The next of the new node points to the head.
- The next of the previous last node points to the new node.
Node Structure:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}To implement and perform operations (like insertion, deletion, or traversal) efficiently, we typically maintain:
- head → Reference to the first node in the list.
- tail → Reference to the last node in the list.
In a circular linked list, tail.next always points to head.
Methods for Insertion at the End in Circular Linked List in Java
There are multiple ways to insert a node at the end in a circular linked list:
Method 1: Traversing from the Head until the Last Node
Method 2: Using a Tail Pointer
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Methods for Insertion at the End in Circular Linked List in Java
Method 1: Using Traversal from Head
Algorithm for Insertion at the End:
Create a new node with the given data.
If the list is empty, make the new node point to itself and mark it as the head.
Otherwise, start from the head and traverse until you find the last node (whose next is head).
Set the next of the last node to the new node.
Set the new node’s next pointer to the head.
The circular structure is maintained.
Java Code:
// Insertion at End in Circular Linked List using Traversal
class CircularLinkedList {
Node head;
// Node structure
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// Function to insert node at end
public void insertAtEnd(int data) {
Node newNode = new Node(data);
// Case 1: If list is empty
if (head == null) {
head = newNode;
newNode.next = head; // Point to itself
return;
}
// Case 2: Traverse to last node
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
// Insert at end
temp.next = newNode;
newNode.next = head;
}
// Display the circular linked list
public void display() {
if (head == null) {
System.out.println("List is empty");
return;
}
Node temp = head;
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
System.out.println();
}
// Main function to test
public static void main(String[] args) {
CircularLinkedList cll = new CircularLinkedList();
cll.insertAtEnd(10);
cll.insertAtEnd(20);
cll.insertAtEnd(30);
System.out.println("Circular Linked List after insertion:");
cll.display();
}
}
Output:
Circular Linked List after insertion: 10 20 30
Space Complexity: O(1)
Methods for Insertion at the End in Circular Linked List
Method 2: Using a Tail Pointer (Optimized Method)
Algorithm for Insertion at the End:
To avoid traversing the entire list every time, we maintain a tail pointer that always points to the last node.
This allows insertion at the end in O(1) time.
Maintain a tail pointer that points to the last node.
Create a new node with the given data.
If the list is empty:
Make the new node point to itself.
Set both head and tail to the new node.
- Otherwise:
Set the new node’s next pointer to head.
Set tail’s next pointer to the new node.
Update tail to point to the new node.
Java Code:
// Insertion at End in Circular Linked List using Tail Pointer
class CircularLinkedListOptimized {
Node head, tail;
// Node structure
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
// Function to insert at end using tail pointer
public void insertAtEnd(int data) {
Node newNode = new Node(data);
// Case 1: Empty list
if (head == null) {
head = newNode;
tail = newNode;
newNode.next = head;
return;
}
// Case 2: Insert directly using tail
newNode.next = head;
tail.next = newNode;
tail = newNode;
}
// Display the circular linked list
public void display() {
if (head == null) {
System.out.println("List is empty");
return;
}
Node temp = head;
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
System.out.println();
}
// Main function to test
public static void main(String[] args) {
CircularLinkedListOptimized cll = new CircularLinkedListOptimized();
cll.insertAtEnd(5);
cll.insertAtEnd(15);
cll.insertAtEnd(25);
cll.insertAtEnd(35);
System.out.println("Circular Linked List after optimized insertion:");
cll.display();
}
}
Output:
Circular Linked List after optimized insertion: 5 15 25 35
Space Complexity: O(1)
Comparison between Methods
| Criteria | Method 1: Traversal | Method 2: Tail Pointer |
|---|---|---|
| Approach | Traverse from head till last node | Maintain direct pointer to last node |
| Time Complexity | O(n) | O(1) |
| Space Complexity | O(1) | O(1) |
| Ease of Implementation | Simple | Slightly advanced |
| Suitable For | Small lists | Frequent insertions at end |
Insertion at the end in a Circular Linked List in Java is a foundational concept in data structures that helps build efficient and flexible programs.
While the traversal method is simpler and suitable for small lists, the tail pointer method offers better efficiency for frequent insertions. Understanding both approaches ensures you can choose the right method based on the application’s needs.
FAQ's Related to Insertion at the end in circular linked list
Answer:
It is the process of adding a new node after the last node while maintaining the circular connection where the last node points to the head.
Answer:
In a singly linked list, the last node’s next pointer is null, while in a circular linked list it points back to the head node.
Answer:
The tail pointer method is faster as it performs insertion in O(1) time compared to O(n) in traversal.
Answer:
While possible, recursion is not efficient or common for circular lists because it adds extra stack space and complexity.
Answer:
Yes, by setting the last node’s next pointer to the head node, a singly linked list can be converted into a circular linked list.
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
Login/Signup to comment