GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
496 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 (3.6k points) 3 17 39 | 496 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.5k points) 2 12 21
selected by


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
Top Users Oct 2017
  1. Arjun

    23462 Points

  2. Bikram

    17108 Points

  3. Habibkhan

    8560 Points

  4. srestha

    6314 Points

  5. Debashish Deka

    5458 Points

  6. jothee

    5038 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4416 Points

  9. sushmita

    3996 Points

  10. Rishi yadav

    3868 Points


Recent Badges

Notable Question Sanjay Sharma
Notable Question Warrior
Notable Question sid1221
Nice Answer 2018
Good Question Arjun
Nice Question mitalitak
Great Question Arjun
Popular Question Tesla!
Nice Question makhdoom ghaya
Popular Question Sankaranarayanan P.N
27,348 questions
35,204 answers
84,249 comments
33,328 users