What is the complexity of adding an element to an…

The average case complexity of adding an element to an ArrayList is O(1).

This is achieved by using a dynamic array, and the addition occurs at the end of the list.

// Adding to the end of the list
List<String> list = new ArrayList<>();
list.add("element"); // O(1) on average

However, if the internal array of the ArrayList is full, a resize operation is required. This involves creating a new, larger array and copying all existing elements into it. The complexity of this operation is O(n), where n is the current size of the list.

// Example where resize might occur
List<Integer> numbers = new ArrayList<>(3); // Initial capacity 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Resize may occur here - O(n)

If an element is added not at the end of the list (using add(int index, E element)), but in the middle or at the beginning, all subsequent elements need to be shifted one position to the right. The complexity of this operation is O(n), where n is the number of elements to shift.

// Adding at the beginning of the list
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Adding at the beginning - O(n)

Thus, the complexity of adding an element to an ArrayList depends on the position of insertion and whether a resize is needed:

Operation	Average case	Worst case (during resize or non-end insertion)
`add(E element)` (at the end)	O(1)	O(n)
`add(int index, E element)`	O(n)	O(n)

What is the complexity of adding an element to an ArrayList?