Similarly in doubly linked lists too, when either of the remove methods are used, it'll be the same as above right ? because even though finding the successor and predecessor will be O(1), to iterate to the desired element it may take O(n) . Is this right ?
Don't try to reduce complexity to fit in such corner cases. Even in the case of extreme values, the complexity remains O(n), even though n = 1. That does not reduce to constant time.
Lilou Laure wrote:. . . when we refer to the first or last elements, for which it'll be O(1).
Yes; the time taken on average to remove something from a linked list remains linear time; there is no such thing as O(n ÷ 2) complexity.
Similarly in doubly linked lists too, when either of the remove methods are used, it'll be the same as above right . . . to iterate to the desired element it may take O(n) . Is this right?
Lilou Laure wrote:so the time complexity will be O(n) except when we refer to the first or last elements, for which it'll be O(1).
Complexity classes are not concerned with specific cases, they're only used to indicate how fast a function grows.
You can say "Getting an element at a fixed index in a linked list of size n performs in O(1)", or you can say "Getting an element at a given index om a linked list of size n performs in O(n)", but these are different operations. It doesn't matter what the exact value of n is. Here's an example of an O(1) operation:
Even though this method gets an element that's possibly in the middle of a linked list (if the list has close to a 100 elements), it still operates in O(1), because the amount of time it takes does not depend on the size of the list. It will take equally long for a list of a thousand elements.
Note that it's important to specify what n stands for. In your first method, n was taken to be the shortest distance between the index and the start or end of the list. In your second method, n was taken to be the size of the list. If instead, for the method remove(int index), d stands for the shortest distance between the start and end of the list, and n stands for the size of the list, then the operation performs in O(d), not O(n).
The first stage of removal runs in constant time because it is possible to find each element from its index with the underlying array; moving the remaining elements in the array to occupy that space however takes a time dependent on the size of the List.
All of the other operations run in linear time (roughly speaking).