When your question is answered use !solved to mark the question as resolved.
Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.
#Time complexity on Doubly linked list
remote fractalBOT
stable kernel
I would think it would be O(n) since in the worst case you're inserting in the middle, which would be n/2 things to iterate over
slender lynx
^, but if you don't care about where you insert or if you have a pointer to the element before/after where you want to insert, it's O(1)
sure, you can always insert at the beginning in O(1) by using the head pointer, but sometimes you care about the order of elements and don't want to do that
stable kernel
Well the worst case insert in a doubly linked list would be one where you want to insert in the middle and you only have the usual head and tail pointer for the double linked list, since that's the most objects you will have to iterate over
slender lynx
it's the best you can do if you get unlucky with the input.
let's say you wanted to find an element in a list.
No matter in which order you searched the list, you could always happen to look at the right element last, so it's O(n)
tame hare
O(n) to get to the element of interest, if you have a hold of that element it's O(1).
My application for example has direct addressing of list nodes so it's always O(1) to get to an element.
Yes.
remote fractalBOT