self doubt

Question

Given a  pointer to a node to be deleted what is the time complexity to delete a node in the circular linked list :

i think answer is O(1).

Am i right?

Comments

If it is singly linked list, O(n) due to you have to update previous node, next pointer.... But you don't know the previous node

 

If it is doubly linked list, it will take O(1)

---

@shaik

Deletion with the single pointer in a linked list is possible by copying the next node into a current node and deleting the next node.

 

If given pointer is head pointer then only O(n) possible because of traversing list to access that element then delete.

---

Yes bro... It is possible in your way...

But you didn't code in this way... Why because, let a,b,c,d are in your linked list... You want to delete b, then you are actually deleting c, if somewhere You use c Previously... Then your code collapse..

Answer 1

If only a pointer to that node is given:

1. Single Circular Linked list: You have to traverse the whole list and come back to that node(so as to link previous and next node of the node to be deleted). So, in that case, O(n).

2. Doubly circular Linked list: Just link the next of previous node with the next node of the node to be deleted, and also link the previous node of the next node with node before the node to be deleted. This will take O(1).

P.S. The comments give the same answer too.

Comments

@mohitjar.....

you are talking about a general case, see question tell pointer is already pointing required node to be deleted then why will you traverse the list.

---

@raj , you need previous node for deletion, try to write a code , you will understand, you need to link the previous node with the next node of node to be deleted, i.e
prev_node->next = node_d -> next  // node_d is the node to be deleted
to get prev_node you need to traverse the list

---

@shubham

let pointer *ptr point the required node:

let *t = ptr->next;

ptr->data = t->data

ptr->next = ptr->data

free(t)

 

The above pseudocode for deletion node with a single pointer. But the above code fail at only one condition (deleting the last node). In that case, we need to traverse the entire linked list.I think I need to add that condition in my answer.

ok thanks!