*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

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 remainsLilou Laure wrote:. . . when we refer to the first or last elements, for which it'll be O(1).

*(*

**O***n*), even though

*n*= 1. That does not reduce to constant time.

Yes; the time taken on average to remove something from a linked list remains linear time; there is no such thing asSimilarly 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?

*(*

**O***n ÷ 2*) complexity.

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 r

`emove(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 mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

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).