search
Log In
1 vote
964 views

The Answer given is A) 

I think the naswer should be B) as we have both the prev pointer and the next pointer available , it will take constant time to update the adjacent nodes pointers and delete the given node .?

in DS 964 views
0
In linked list finding element itself takes O(n) time and deletion takes O(1) time,so it is O(n).

suppose if elements stored in DLL are (head)12,5,8,6,9,4,13(tail).

to find an element '9' worst case we need to traverse entire list.
0

So does deletion include search time as well ? 

I thought that the position of the node is already known and we have to only perform deletion.

So if this question comes in exam what do we consider ?

http://stackoverflow.com/questions/1895769/time-complexity-of-node-deletion-in-singly-and-doubly-linked-lists

1

For deletion=search time+link modification

When deleted node address is given then in CDLL we can perform deletion in O(1) time.

In SLL eventhough deleted node address given it takes O(n) time.

In the given question address is not specified so TC=O(n) otherwise it is O(1) only in CDLL but not DLL.

IN DLL also reaching last node it takes O(n) time in CLL with help of prev pointer at first node we can reach last in O(1)

1 Answer

4 votes
 
Best answer

If the pointer to the node to be deleted is given then worst case time complexity would be O(1). But since it is not given, we would have only pointer to the head. So before deleting we would have to search by traversing the LL. In worst case it might take O(n) and deleting would take only O(1). 

Thus O(n).


selected by

Related questions

1 vote
1 answer
1
272 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 ... 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?
asked Nov 20, 2018 in DS aditi19 272 views
0 votes
1 answer
2
406 views
WHAT IS THE TIME COMPLEXITY TO ENQUEUE AN ELEMENT IF THE QUEUE IS IMPLEMENTED AS A CIRCULAR QUEUE AND WE HAVE GOT ONLY ONE POINTER TO FRONT ELEMENT??
asked Sep 20, 2018 in DS sushmita 406 views
0 votes
1 answer
3
1.3k views
With regard to linked list, which of the following statement is false ? (A) An algorithm to search for an element in a singly linked list requires 0(n) operations in the worst case. (B) An algorithm for deleting the first element in a singly linked list ... linked list requires 0(n) operations. (D) An algorithm for deleting the middle node of a circular linked list requires 0(n) operations.
asked Sep 17, 2017 in DS rishu_darkshadow 1.3k views
...