java - Why start an ArrayList with an initial capacity?

Question

The usual constructor of ArrayList is:

ArrayList<?> list = new ArrayList<>();

But there is also an overloaded constructor with a parameter for its initial capacity:

ArrayList<?> list = new ArrayList<>(20);

Why is it useful to create an ArrayList with an initial capacity when we can append to it as we please?

Answer 1

If you know in advance what the size of the ArrayList is going to be, it is more efficient to specify the initial capacity. If you don't do this, the internal array will have to be repeatedly reallocated as the list grows.

The larger the final list, the more time you save by avoiding the reallocations.

That said, even without pre-allocation, inserting n elements at the back of an ArrayList is guaranteed to take total O(n) time. In other words, appending an element is an amortized constant-time operation. This is achieved by having each reallocation increase the size of the array exponentially, typically by a factor of 1.5. With this approach, the total number of operations can be shown to be O(n).