.png)
Deletion from a Circular Linked List
Problem Statement
Given a circular linked list, perform deletion of a node based on different conditions such as:
- Deleting the head node
- Deleting the last node
- Deleting a node with a given value
- Deleting a node at a given position
In a circular linked list, the last node points back to the head, so deletion requires careful pointer manipulation to maintain circularity.
Types of Deletion in Circular Linked List
- Deletion of Head Node
- Deletion of Last Node
General Edge Cases
- Empty list
- Single node list
- Node to be deleted not found
Approach 1: Deletion of Head Node
To delete the head node:
- Traverse the list to find the last node.
- Update the last node’s next to point to head->next.
- Move head to the next node.
If only one node exists, set head to NULL.
Algorithm
- If head == NULL, return.
- If head->next == head, set head = NULL.
- Traverse to the last node.
- Set last->next = head->next.
- Update head = head->next.
Time Complexity
- O(n)
Space Complexity
- O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
void printList(struct Node* head) {
if (head == NULL) return;
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(head)\n");
}
void deleteHead(struct Node** head) {
if (*head == NULL) return;
if ((*head)->next == *head) {
free(*head);
*head = NULL;
return;
}
struct Node* last = *head;
while (last->next != *head)
last = last->next;
struct Node* temp = *head;
last->next = (*head)->next;
*head = (*head)->next;
free(temp);
}
int main() {
// Creating circular list: 10->20->30->(back to 10)
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; second->data = 20; third->data = 30;
head->next = second; second->next = third; third->next = head;
printf("Before Deletion:\n");
printList(head);
deleteHead(&head);
printf("After Deleting Head:\n");
printList(head);
return 0;
}C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
struct Node {
int data;
Node* next;
};
// Print Circular Linked List
void printList(Node* head) {
if (head == NULL) return;
Node* temp = head;
do {
cout << temp->data << " -> ";
temp = temp->next;
} while (temp != head);
cout << "(head)" << endl;
}
// Delete Head Node
void deleteHead(Node*& head) {
if (head == NULL) return;
// Only one node
if (head->next == head) {
delete head;
head = NULL;
return;
}
Node* last = head;
// Find last node
while (last->next != head) {
last = last->next;
}
Node* temp = head;
last->next = head->next; // bypass head
head = head->next; // move head
delete temp;
}
int main() {
// Create nodes
Node* head = new Node{10, NULL};
Node* second = new Node{20, NULL};
Node* third = new Node{30, NULL};
// Link nodes circularly
head->next = second;
second->next = third;
third->next = head;
cout << "Before Deletion:\n";
printList(head);
deleteHead(head);
cout << "After Deleting Head:\n";
printList(head);
return 0;
}Java Implementation
static Node deleteHead(Node head) {
if (head == null)
return null;
if (head.next == head)
return null;
Node last = head;
while (last.next != head)
last = last.next;
last.next = head.next;
head = head.next;
return head;
}
Python Implementation
def delete_head(head):
if head is None:
return None
if head.next == head:
return None
last = head
while last.next != head:
last = last.next
last.next = head.next
head = head.next
return head
JavaScript Implementation
function deleteHead(head) {
if (head === null) return null;
if (head.next === head) return null;
let last = head;
while (last.next !== head) {
last = last.next;
}
last.next = head.next;
head = head.next;
return head;
}
Output-
Before Deletion:
10 -> 20 -> 30 -> (head)
After Deleting Last:
10 -> 20 -> (head)Approach 2: Deletion of Last Node
To delete the last node:
- Traverse the list until the node just before the last node.
- Update its next to point to the head.
Algorithm
- If head == NULL, return.
- If only one node exists, set head = NULL.
- Traverse until current->next->next == head.
- Set current->next = head.
Time Complexity
- O(n)
Space Complexity
- O(1)
C Implementation
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
void printList(struct Node* head) {
if (head == NULL) return;
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(head)\n");
}
void deleteLast(struct Node** head) {
if (*head == NULL) return;
if ((*head)->next == *head) {
free(*head);
*head = NULL;
return;
}
struct Node* current = *head;
while (current->next->next != *head)
current = current->next;
struct Node* temp = current->next;
current->next = *head;
free(temp);
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; second->data = 20; third->data = 30;
head->next = second; second->next = third; third->next = head;
printf("Before Deletion:\n");
printList(head);
deleteLast(&head);
printf("After Deleting Last:\n");
printList(head);
return 0;
}C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
struct Node {
int data;
Node* next;
};
void printList(Node* head) {
if (head == NULL) return;
Node* temp = head;
do {
cout << temp->data << " -> ";
temp = temp->next;
} while (temp != head);
cout << "(head)\n";
}
void deleteLast(Node*& head) {
if (head == NULL) return;
if (head->next == head) {
delete head;
head = NULL;
return;
}
Node* current = head;
while (current->next->next != head)
current = current->next;
Node* temp = current->next;
current->next = head;
delete temp;
}
int main() {
Node* head = new Node{10};
Node* second = new Node{20};
Node* third = new Node{30};
head->next = second;
second->next = third;
third->next = head;
cout << "Before Deletion:\n";
printList(head);
deleteLast(head);
cout << "After Deleting Last:\n";
printList(head);
return 0;
}Java Implementation
static Node deleteLast(Node head) {
if (head == null)
return null;
if (head.next == head)
return null;
Node current = head;
while (current.next.next != head)
current = current.next;
current.next = head;
return head;
}
Python Implementation
def delete_last(head):
if head is None:
return None
if head.next == head:
return None
current = head
while current.next.next != head:
current = current.next
current.next = head
return head
JavaScript Implementation
function deleteLast(head) {
if (head === null) return null;
if (head.next === head) return null;
let current = head;
while (current.next.next !== head) {
current = current.next;
}
current.next = head;
return head;
}
Output-
Before Deletion:
10 -> 20 -> 30 -> (head)
After Deleting Last:
10 -> 20 -> (head)Key Points to Remember
- Always maintain circularity after deletion
- Handle single-node list separately
- Traversal stopping condition is reaching the head again
Conclusion
Deletion in a circular linked list requires careful handling of pointers due to the absence of a NULL end. By correctly updating the head and last node references, all deletion operations can be performed efficiently in linear time and constant space.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
