Deletion in Circular Linked List
Deleting an element from a circular linked list. We will be given a node and our task is to delete that node from the circular linked list.

Question

Deletion in Circular Linked List

Deleting an element from a circular linked list. We will be given a node and our task is to delete that node from the circular linked list.

Accepted Answer

To delete a node from a circular linked list, we need to find the previous node of the node to be deleted and update its next pointer.

Find the previous node of the node to be deleted
Update the next pointer of the previous node to skip the node to be deleted
Free the memory occupied by the node to be deleted

Accepted Answer

Here is complete algorithm:

- If the list is empty simply return.

- If the list is not empty then we define two pointers curr and prev and initialize the pointer curr with the head node.

- Traverse the circular linked list using curr to find the node to be deleted and before moving curr to next node, everytime set prev = curr so that previous will be on one node behind current.

-If the node is found, check if it is the only node in the circular linked list. If yes, do head = NULL and free(curr).

- If the circular linked list has more than one node, check if it is the first node of the list. To check this check( curr == head). If yes, then move prev until it reaches the last node. After prev reaches the last node, set head = head -> next and prev -> next = head. Delete curr.

- If curr is not first node, we check if it is the last node in the list. To check this is condition (curr -> next == head).

- If curr is the last node. Do prev -> next = head and delete the node curr by applying free(curr).

- If the node to be deleted is neither the first node nor the last node, then set prev -> next = temp -> next and delete curr node to free up space.

void deleteValue(Node *head, int key)

{

if (head == NULL)

return;

if(head->data==key && head->next==head)

{

free(head);

head=NULL;

return;

}

Node * temp=head,*d;

// If head is to be deleted

if(head->data==key) {

// Find the last node

while(temp->next!=head)

temp=temp->next;

temp->next=head->next;

free(head);

head=temp->next;

}

while(temp->next!= head && temp->next->data!=key) {

temp=temp->next;

}

if(temp->next->data==key) {

d=temp->next;

temp->next=d->next;

free(d);

}

else

cout<<"Not found the key";

}

Accepted Answer

Recursion

The idea is to use a recursive approach to find the given key and then remove that node. The recursive idea is very clear that we will traverse through the circular linked list, and we will check if the value of the node is equal to the given key.

We will define a function deleteNodeHelper(root, key, head) to remove the key in which the head is the starting node of the linked list, and we will send root as the next node of the head node.

Working of the Recursive function:

If the root is equal to head, then we have traversed the whole linked list and have not found the given key. So, we will return head. This will act as the base case of the recursive function.
We will check if the value of the node is equal to the key. We have found the node with the given key, and we have to remove this node. So, we will return the next node of the root.
Now, we have to make a recursive call to check all nodes of the remaining linked list. We will set the next node of the root as deleteNodehelper(next, key, head), where next is equal to the next node of root.
In the end, we will return the current node root.

Space Complexity: O(n)Explanation:

O(N), where N is the size of the circular linked list

In the worst case, we are making N recursive calls that take O(N) Space Complexity. Hence, the overall Space Complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the size of the circular linked list.

We are traversing through the linked list to check if the value of the node is equal to the given key that takes O(N) time. Hence, the overall Time Complexity is O(N).

Accepted Answer

Curr And Prev Approach

Here is complete algorithm:

If the list is empty simply return.
If the list is not empty, then we define two pointers curr and prev and initialize the pointer curr with the head node.
Traverse the circular linked list using curr to find the node to be deleted and before moving curr to the next node everytime, set prev = curr so that previous will be on one node behind current.
If the node is found, check if it is the only node in the circular linked list. If yes, do head = NULL.
If the circular linked list has more than one node, check if it is the first node of the list. To confirm this, check (curr == head). If yes, then move prev until it reaches the last node. After prev reaches the last node, then set head = head.next and prev.next = head.
If curr is not the first node, we check if it is the last node in the list. To check this is condition (curr.next == head).
If curr is the last node. Do prev.next = head and delete the node curr by applying free(curr).
If the node to be deleted is neither the first node nor the last node, then set prev.next = temp.next.

Space Complexity: O(1)Explanation:

O(1).

Constant extra space is being used. Hence, the overall Space Complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where N is the size of the circular linked list.

We have to traverse the list to find the node to be deleted that O(N) time. Hence, the overall Time Complexity is O(N).

Accepted Answer

Just used basic linked list deletion by taking care of each and every case.

Top Wolters Kluwer Software Developer interview questions & answers

Popular interview questions of Software Developer