I have read that the time complexity of a searching for an element, which is located at end of the double ended singly linked list is o(N).
But since time complexity of searching for an element at front is o(1), I think the same should apply to end element. Any ideas? Thanks
The cost of searching for an element that is at the front of the linked list is indeed one, because you would be holding a pointer to that first element. Thus, it would be O(1) to find the first element.
In the case of a double ended singly linked list, assuming you mean you hold a pointer to both the first and last element of the singly linked list, you would indeed find that the time to locate the last element would be O(1), because you have a reference to exactly where it is.
However, consider the case of a double ended singly linked list where you want to find the (n-1)th element in that list. Suddenly, you find that you have to iterate over n-1 elements until you get to that element. Thus you would find that the worst case runtime for the double ended singly linked list would be O(n-1), which is really O(n).
Even in the case where you had a double ended doubly linked list, you would find that the worst case runtime would be O(n/2), (assuming you had a mechanism to tell if the element was in the first half of second half, which is unlikely). But O(n/2) is still really O(n).
Since we generally refer to the worst case when we talk about big-o time complexity, you can see that linked lists are invariably O(n).
Note: That's not to say that big-o is the only measure of time-complexity. Depending on your implementation, the amortized or probabilistic time-complexity could indeed be different from its worst case time complexity, and likely is.
