WikiGalaxy
Insertion in Circular Linked List
Introduction:
A Circular Linked List is a variation of a linked list where the last node points to the first node, forming a circular chain. Insertion in this structure can occur at various positions including the beginning, end, or any given position.
Insertion at the Beginning:
To insert at the beginning of a circular linked list, you need to make the new node point to the current head and then update the last node to point to this new node.
Insertion at the End:
For inserting at the end, the new node should point to the head, and the previous last node should be updated to point to this new node.
Insertion at a Specific Position:
When inserting at a specific position, traverse the list to the desired position, adjust pointers to include the new node in the sequence, and ensure the circular nature is maintained.
// Diagram for Insertion at the Beginning
// Before: [Head] -> [Node1] -> ... -> [Last] -> [Head]
// After: [NewHead] -> [Head] -> [Node1] -> ... -> [Last] -> [NewHead]
// Diagram for Insertion at the End
// Before: [Head] -> [Node1] -> ... -> [Last] -> [Head]
// After: [Head] -> [Node1] -> ... -> [Last] -> [NewEnd] -> [Head]
// Diagram for Insertion at a Specific Position
// Before: [Head] -> [Node1] -> [Node2] -> [Node3] -> ... -> [Head]
// After: [Head] -> [Node1] -> [NewNode] -> [Node2] -> [Node3] -> ... -> [Head]
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
class CircularLinkedList {
Node head = null;
Node tail = null;
// Insert at the beginning
void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
newNode.next = head;
} else {
newNode.next = head;
head = newNode;
tail.next = head;
}
}
// Insert at the end
void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
newNode.next = head;
} else {
tail.next = newNode;
tail = newNode;
tail.next = head;
}
}
// Insert at a specific position
void insertAtPosition(int data, int position) {
Node newNode = new Node(data);
if (position == 0) {
insertAtBeginning(data);
return;
}
Node temp = head;
for (int i = 0; i < position - 1; i++) {
temp = temp.next;
if (temp == head) break;
}
newNode.next = temp.next;
temp.next = newNode;
if (temp == tail) {
tail = newNode;
}
}
}
Conclusion:
Insertion in a Circular Linked List requires careful pointer management to maintain the circular nature. Each insertion method—beginning, end, or specific position—has its own set of steps to ensure the list remains connected and circular.
