What is the time complexity of the ArrayList.add method?

Question

The java documentation for class ArrayList<E> specifies that:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

How is this possible?

The method void add​(int index, E element) inserts the specified element at the specified position in this list, shifting all subsequent elements to the right. While it seems possible to achieve amortized constant time to insert n elements at the end of the ArrayList by reallocating the backing array using geometric growth, this would not allow for amortized constant time when inserting elements in the middle of the array.

Does the documentation only refer to the add(element E) method or is there a neat trick to achieve amortized constant time in all cases?

Answer 1

As explained in this answer, Oracle uses a confusing convention: when they mention the add method, they usually refer to the add(E element) method, whereas the void add​(int index, E element) is referred to as the insert method... The method name is indeed confusing, and so is the class name too.