How does Java List size() work?

Question

Hi,

In java, there is a List interface and size() method to compute the size of the List. when i call List.size(), how does it count? is it counted linearly? or the count is determined and just the value is returned back when size()?

Answer 1

java.util.List is an interface, not a class. The implementation of the size() method may be different for different concrete implementations. A reasonable implementation for a size() method on a java.util.List implementation would be to initialize an instance member of type int to zero and increment/decrement it appropriately as items are added to/removed from the List. The size() method could simply return the aforementioned instance member. This is of course, simply an example. For complete detail, you could always look at the sources for the built-in List implementation. All the source code has been available for years.

Answer 2

Size is defined as the number of elements in the list. The implementation does not specify how the size() member function operates (iterate over members, return stored count, etc), as List is an interface and not an implementation.

In general, most concrete List implementations will store their current count locally, making size O(1) and not O(n)