The Gateway to Computer Science Excellence
+1 vote

Image may contain: text

in Algorithms by | 120 views
b ?
Yes its should be O(1)
it should be O(n).

In worst case pointer q points to last element of the list so we have to traverse the entire list.
my question is if head pointer is not given ,can we find worst case complaxity or can we delete the node.

1 Answer

+1 vote


If it is the Last node of the linked list it will take  O(n) time. Despite node pointer is given but we don't know the address of the previous node. From head, we need to traverse the linked list to get the add of the previous node.

If we have address of prevoius node then only we can store the address of the next node that has to be deleted.


Previous -> next = Current -> next;

edited by
If it is the 2nd last node, it can be deleted in O(1). This is how ->

1. copy data of last node, into 2nd last node

2. Now delete the last node (note we have pointer to previous of this node. i.e. we have pointer to 2nd last node)

However if the original node to be deleted is itself the last node, then even above method can't be appplied and in that case time complexity is O(n). Ans is O(n) bcoz of last node and not because of 2nd last node.

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,345 questions
60,517 answers
95,368 users