Is adding an element to an ArrayList always O(1) in complexity?

Not always.

In most cases, adding an element to the end of an ArrayList indeed has a complexity of O(1). This is because ArrayList is based on an array, and when there is free space, the element is simply written into the next available slot.

// Example of adding to the end
List<String> list = new ArrayList<>();
list.add("element1"); // O(1) in a typical case

However, when the internal array is full, ArrayList must increase its capacity. This involves creating a new, larger array, copying all existing elements from the old array to the new one, and then adding the new element. This array copying operation has a complexity of O(n), where n is the current size of the ArrayList.

// Example of adding that triggers capacity increase
List<Integer> list = new ArrayList<>(5); // Initial capacity
for (int i = 0; i < 5; i++) {
    list.add(i); // O(1)
}
list.add(5); // Here, capacity increase may occur, causing O(n)

Additionally, adding an element not at the end of an ArrayList always has a complexity of O(n). This is because all elements after the insertion point need to be shifted right to make space for the new element.

// Example of adding not at the end
List<String> list = new ArrayList<>(List.of("a", "c"));
list.add(1, "b"); // O(n), as element "c" needs to be shifted

To summarize:

Operation	Complexity	Note
At the end (space available)	O(1)	Most common scenario
At the end (no space)	O(n)	During capacity increase
Not at the end (any position)	O(n)	Elements need to be shifted