The Gateway to Computer Science Excellence
+1 vote
97 views

Image may contain: text

in Algorithms by Boss (48.8k points) | 97 views
0
b ?
0
Yes its should be O(1)
0
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.
0
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

O(n).

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;

by Junior (751 points)
edited by
+1
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.
0
Agree!.
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,430 answers
195,211 comments
99,927 users