i am little confused over the time complexity of single and doubly link list operation.for a single link list deletion takes o(n) time which is clear since first we have to search and for the worst case it is o(n) but i have read somewhere on the net that for doubly link list its o(1) why? for that too we have to traverse whole list…
thanks in advance.
reply soon
You haven’t read properly.
The cost of searching in both singly-linked list and doubly-linked list is O(n).
Before deletion you need to search the linked list, which is O(n). Once you have searched the node to be deleted, you can delete in O(1) for both singly-linked list and doubly-linked list. But there is an important point to be noted for singly-linked list : you need to track the previous node as well while searching for the node to be deleted. This is not required for doubly-linked list.
So the cost of deletion depends on whether you are including cost of searching or not.