linked list closed

Question

Let P be a single linked list.Let Q be a pointer to an intermediate node 'X' in the list.What is the worst case time complexity of best known algorithm to delete the node 'X ' from the list

Comments

is ans O(n) ?

---

O(1) as it's given that it's an intermediate node.

---

@Manu Thakur Suppose you are given a pointer Q which points to the current node (the one that is to be deleted which is intermediate). Now if we want to delete it then the next address of the previous node must point to the next of the present node. Since it is a singly linked list hence we do not have a pointer to the previous node, in order to obtain that pointer we need to traverse the list. This will take o(n).

And intermediate means it can be last but one node also.

Correct me if I am wrong

---

i think pointer is pointing to the element which we have to delete so it will take O(1)

---

@ashwin

Suppose we have a linked list as follows

A->B->C->D->E and pointer q is given to the node B as B is to be deleted.

q.data = q.next.data;

q.next = q.next.next;

now our modified linked list is

A->C->D->E

B is removed successfully in O(1) we can do such removal in O(1) except last node deletion.

---

Ohh I got my mistake. Thankyou so much @Manu Thakur

---

@ Manu Thakur

but by your operation previous node of Q how get connected to Q->next only Q pointer will be point toQ->next

---

@abhishek node is deleted we can set q to null. because job has been done and we don't require it anymore. And B is already connected to A, we don't need to worry about it. we copied data from Node C and connected it to D.

---

@abhishek Here content of node to which Q is pointing already changed. Hence to need to again point prev of Q to next of Q.

---

we need another pointer who will point to previous node of Q

P->next=Q; then again A will point to C

A->C->D...

but for this question we do not have to do  @ Manu Thakur sir ??

---

@abhishek why do you need a pointer the the previous node of the node pointedby q? it is written in the question node to be deleted is an intermediate node.

if question is to delete the last node then we need a pointer which will point to the second last node. hence to delete last TC is O(n) and other than last node each node can be deleted in O(1)