GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
124 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 .?

 

asked in DS by Loyal (2.5k points)   | 124 views
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.

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

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

answered by Active (1.2k points)  
selected by


Top Users Jun 2017
  1. Bikram

    3912 Points

  2. Arnab Bhadra

    1526 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1501 Points

  5. Debashish Deka

    1480 Points

  6. junaid ahmad

    1432 Points

  7. pawan kumarln

    1286 Points

  8. Rupendra Choudhary

    1242 Points

  9. rahul sharma 5

    1240 Points

  10. Arjun

    1232 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. pawan kumarln

    418 Points

  2. akankshadewangan24

    334 Points

  3. Arjun

    272 Points

  4. Debashish Deka

    234 Points

  5. Abhisek Das

    230 Points


23,433 questions
30,149 answers
67,606 comments
28,486 users