Is checking the size of a list linear?

Question

I've seen many answers online saying that checking the size of a list is constant time, but I don't understand why.

My understanding was that a list isn't stored in contiguous memory chunks (like an array), meaning there is no way of getting the size of a list (last element index + 1), without first traversing through every element.

Thoughts?

Answer 1

I've seen many answers online saying that checking the size of a list is constant time.

This fallacy may originate in a fundamental flaw in the Python language: arrays are called lists in Python. As Python gains popularity, the word list has become ambiguous.

Computing the length of a linked list is an O(n) operation, unless the length has been stored separately and maintained properly.

Retrieving the size of an array is performed in constant time if the size is stored along with the array, as is the case in Python, so a=[1,2,3]; len(a) is indeed very fast.

Computing the length of an array may be an O(n) operation if the array must be scanned for a terminating value, such as a null pointer or a null byte. Thus strlen() in C, which computes the number of bytes in a C string (a null terminated array of char) operates in linear time.