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