The Gateway to Computer Science Excellence
0 votes
118 views
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?
in DS by Active (5.1k points) | 118 views
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.
0
in that case space complexity won't be O(1) as a separate list will be required
+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
0
yeah it helps. thank u
+1

@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).

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

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

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,429 answers
195,208 comments
99,921 users