WikiGalaxy
Deletion in Circular Linked List
Introduction:
A Circular Linked List is a linked list where the last node points back to the first node, forming a circle. Deletion in a circular linked list can be more complex compared to a singly linked list due to its circular nature. This operation involves removing a node from the list and updating pointers accordingly to maintain the circular structure.
Types of Deletion:
- Deleting the head node
- Deleting a node in the middle
- Deleting the last node
// Diagram for Deleting a Node in Circular Linked List
// Step 1: Identify the node to be deleted
// [Head] -> [Data | Next] -> [Data | Next] -> [Data | Next] -> [Head]
// Step 2: Adjust pointers to bypass the node
// [Head] -> [Data | Next] -> [Data | Next] -> [Head]
// Step 3: Remove the node and free memory
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
class CircularLinkedList {
Node head;
// Function to delete a node
void deleteNode(int key) {
if (head == null) return;
Node curr = head, prev = null;
// If head node is to be deleted
if (curr.data == key) {
while (curr.next != head) {
curr = curr.next;
}
curr.next = head.next;
head = head.next;
return;
}
// Search for the node to be deleted
do {
prev = curr;
curr = curr.next;
} while (curr != head && curr.data != key);
// If node is found
if (curr.data == key) {
prev.next = curr.next;
}
}
}
Explanation:
The deletion operation in a circular linked list requires careful handling of pointers to ensure the list remains circular. In the provided code, we check if the node to be deleted is the head. If so, we traverse to the last node, update its pointer to the new head, and adjust the head pointer. For other nodes, we traverse the list, find the node, and update the previous node's pointer to bypass the node to be deleted.
Console Output:
Node deleted successfully
Conclusion:
Deletion in a circular linked list requires maintaining the circular nature by updating pointers correctly. Whether deleting the head, a middle node, or the last node, the pointers must be adjusted to ensure the integrity of the list.
