For a signly linked list where each node has a pointer to a data array as well as a next pointer, what would be the worst case time complexity to delete an intermediate node x?
"Worst case time complexity to delete an intermediate node x ?"
Does this means ANY intermediate node ?
if NO,
Then we have to search for that particular node x and then delete.
Searching in linked list takes O(n) time and deletion takes constant.
Total Time = O(n) + O(1) = O(n)
Edited Answer :
For a signly linked list where each node has a pointer to a data array as well as a next pointer, what would be the worst case time complexity to delete an intermediate node x (given a pointer to it)?
Let node x has to be deleted. Pointer is also given so O(1)for searching.
Now apply this algo :
x.data = x-->Next.data
t = x-->Next
x--->Next = x--->Next ---> Next
Free(t)