Insertion at the Beginning in Circular Linked List in Java
Java Program for Insertion at the Beginning in Circular Linked List
Insertion at the Beginning in Circular Linked List in Java is a common operation when working with circular (singly) linked lists.
This article explains what that operation means, multiple ways to implement it, the algorithmic logic with step by step variable level explanations, runnable Java code, example input/output, time and space complexity.
Insertion at the Beginning in Circular Linked List in Java
Circular singly linked list is a linked list where every node points to the next node, and the last node points back to the first node (head), forming a circle. There is no null next pointer in a non empty circular list.
- Keep a pointer/reference to the head (first element).
- Or keep a pointer/reference to the tail (last element). If you have tail, then tail.next is the head.
Insertion at the beginning means that after the operation, the new node must be the first node (head) of the circular list, and the circular property must still hold.
Node Structure:
class Node {
int data;
Node next;
Node(int data) { this.data = data; this.next = null; }
}Variables used in algorithms:
head: reference to the first node (may be null for empty list)
tail: reference to last node (if used)
newNode: the node created to insert
temp / last: iteration pointers for traversing
Methods for Insertion at the Beginning in Circular Linked List
Now, we will study each method with algorithms, step by step logic, and complexity.
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 Beginning in Circular Linked List in Java
Method 1: Using Head Pointer Only (Traversal Approach)
Algorithm for Insertion at the beginning:
- Create a new node newNode.
- If the list is empty:
- Point newNode.next to itself.
- Set head = newNode.
- Otherwise:
- Traverse till last.next == head.
- Set newNode.next = head.
- Set last.next = newNode.
- Update head = newNode.
Java Code:
public class CircularListInsertionTraverse {
static class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
Node head = null;
public void insertAtBeginning(int value) {
Node newNode = new Node(value);
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
Node temp = head;
while (temp.next != head)
temp = temp.next;
newNode.next = head;
temp.next = newNode;
head = newNode;
}
public void printList() {
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("(back to head)");
}
public static void main(String[] args) {
CircularListInsertionTraverse list = new CircularListInsertionTraverse();
list.insertAtBeginning(30);
list.insertAtBeginning(20);
list.insertAtBeginning(10);
System.out.println("Circular Linked List after insertions:");
list.printList();
}
}
Output:
Circular Linked List after insertions: 10 -> 20 -> 30 -> (back to head)
Space Complexity: O(1)
Method 2: Using Tail Pointer
Algorithm for Insertion at the beginning:
- Create a new node newNode.
- If the list is empty:
newNode.next = newNode.
tail = newNode.
- Otherwise:
newNode.next = tail.next (current head).
tail.next = newNode.
- The new head is tail.next.
Java Code:
public class CircularListInsertionTail {
static class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
Node tail = null;
public void insertAtBeginning(int value) {
Node newNode = new Node(value);
if (tail == null) {
tail = newNode;
tail.next = tail;
return;
}
newNode.next = tail.next; // current head
tail.next = newNode; // link tail to new node
}
public void printList() {
if (tail == null) {
System.out.println("List is empty.");
return;
}
Node temp = tail.next; // start from head
do {
System.out.print(temp.data + " -> ");
temp = temp.next;
} while (temp != tail.next);
System.out.println("(back to head)");
}
public static void main(String[] args) {
CircularListInsertionTail list = new CircularListInsertionTail();
list.insertAtBeginning(30);
list.insertAtBeginning(20);
list.insertAtBeginning(10);
System.out.println("Circular Linked List after insertions:");
list.printList();
}
}
Output:
Circular Linked List after insertions: 10 -> 20 -> 30 -> (back to head)
Space Complexity: O(1)
Method 3: Data Swap Technique
Algorithm for Insertion at the beginning:
- Create a new node newNode.
- If the list is empty:
newNode.next = newNode
head = newNode
- Otherwise:
Insert newNode after head.
Swap head.data and newNode.data.
Java Code:
public class CircularListInsertionDataSwap {
static class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
Node head = null;
public void insertAtBeginning(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
head.next = head;
return;
}
newNode.next = head.next;
head.next = newNode;
// Swap data between head and new node
int temp = head.data;
head.data = newNode.data;
newNode.data = temp;
}
public void printList() {
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("(back to head)");
}
public static void main(String[] args) {
CircularListInsertionDataSwap list = new CircularListInsertionDataSwap();
list.insertAtBeginning(30);
list.insertAtBeginning(20);
list.insertAtBeginning(10);
System.out.println("Circular Linked List after insertions:");
list.printList();
}
}
Output:
Circular Linked List after insertions: 10 -> 20 -> 30 -> (back to head)
Space Complexity: O(1)
Note: Avoid this if node data is large or non-swappable.
Comparison between Methods for Insertion at the Beginning in Circular Linked List
| Method | Uses Tail? | Time Complexity | Space Complexity | Notes |
|---|---|---|---|---|
| Head Only (Traverse) | No | O(n) | O(1) | Simple but slower |
| Tail Pointer | Yes | O(1) | O(1) | Best for efficiency |
| Data Swap Trick | No | O(1) | O(1) | Fast but swaps data |
Insertion at the beginning of a circular linked list in Java can be implemented in multiple ways depending on what references you maintain (head, tail) and whether you can modify node data.
- Use a tail pointer for clean O(1) operations.
- use the data swap trick if you can’t maintain tail and swapping data is acceptable.
- otherwise fall back to a traversal based correct O(n) insertion.
The included Java code demonstrates all methods and is ready to run and test.
FAQ's Related to Insertion at the beginning in circular linked list
Answer:
It means adding a new node before the current head so that it becomes the new first node while maintaining the circular connection.
Answer:
By maintaining a tail pointer simply link the new node between tail and tail.next.
Answer:
Yes, but it requires O(n) time (traversing to the last node) or using the data swap trick.
Answer:
To form a continuous loop, ensuring traversal from any node eventually brings you back to the starting node.
Answer:
Maintain both head and tail. It simplifies operations like insertion and deletion while keeping O(1) performance.
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