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


    temp=temp->next;     //temp will point to the node left to 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 | 165 views
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

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


Now delete C as below


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

Time complexity O(1).

Hope this helps
yeah it helps. thank u


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

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
52,315 questions
60,433 answers
95,257 users