Karumanchi

Question

There is a singly linked list. We have a pointer to a particular node(it is not tail node). what is the time and space complexity required to delete this node?

my approach is... As there is no previous pointer so we traverse the list from the starting to just before the concerned node. then we adjust the pointers like this

let ptr be a pointer pointing to the node to be deleted

while(temp->next!=ptr)
{

    temp=temp->next;     //temp will point to the node left to ptr

}

temp->next=ptr->next;

free(ptr);

 

if the node to be deleted is the second last node then we have to traverse the list upto 3rd element from the last node. so I'm getting time complexity as O(n) and space complexity O(1).
but in the book the time complexity is mentioned O(1)
where am I going wrong?

Comments

When a pointer is pointing to a particular node we can delete it directly right why is the need for O(n) complexity ??

---

so how will you link the previous node(previous to the node to be deleted) to the next node(next to the node to be deleted) in the absence of any previous pointer?

---

i dont know if i am right. correct me if wrong

if pointed list (say x),copy the next list(say y) value into x and then delete y.

---

in that case space complexity won't be O(1) as a separate list will be required

---

No

A->B->C->D  and say the pointer is pointing to B then from B we can access C

just copy the address of C into temp variable and

Struct node *temp= B->next

Copy data and address part of C into B like

B-> data =B->next->data

B->next=B->next->next

Now delete C as below

free(temp);

So here we just using one extra node space complexity O(1)

Time complexity O(1).

Hope this helps

---

yeah it helps. thank u

---

@aditi19

O(n) will be when You have traversed the node which you want to delete. If the pointer is directly pointing that node then It will take o(1).

---

Is log^2 n and (logn)^2 are same?

---

(logn)^2 = logn * logn

log^2n at times means log(log(n))

Answer 1

space is (n) and time complexity is 0(n)

Answer 2

we can delete the element in O(1) time complexity by using the copying element method.

suppose, the elements in the linked list are 1->2->3->4. The node to be deleted is 3(denoted by X). let's take the temp pointer which points to the node just after the node is to be deleted(which means X points to node 3 and temp points to node 4). Now follow the below procedure:-

temp=X->next; (making temp to point node 4)

X->data=temp->data;

X->next=temp->next;

free(temp);

This procedure takes only O(1) time to delete any node except the last node.

finally, time complexity=O(1) and  space complexity=O(1)