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

The Gateway to Computer Science Excellence

0 votes

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?

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?

0

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

0

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?

+1

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.

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

+1

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

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

52,315 questions

60,433 answers

201,778 comments

95,257 users