ArrayList is a resizable array or dynamic array implementation in java. ArrayList grows dynamically and ensures that there is always a space to add elements. The backing data structure of ArrayList is an array of Object class. ArrayList class in Java has 3 constructors. It has its own version of readObject and writeObject methods. Object Array in ArrayList is transient . It implements RandomAccess, Cloneable, java.io.Serializable.

Internally an ArrayList uses an Object[] Array which is an array of objects. All operation like deleting, adding and updating the elements happens in this Object[] array.  

ArrayList is one of the most used data structure in Java today.

ArrayList<String> fruits = new ArrayList<>(2);
fruits.add("apple");
fruits.add("banana");

// by adding this, the internal array is doubled it's size
fruits.add("cantalope");

System.out.println(fruits.toString());

Array is a fixed size data structure while ArrayList is not. Even if we specify some initial capacity, we can add more elements.

If we try to add an element using the add() method in the array list, Internally it checks for the capacity to store the new element, If the internal array is full then a new capacity(more than old capacity by 50% at least) is calculated and a new array is created and copied over the old array to it.

Performance of ArrayList       

The time complexity of the common operations in ArrayList java.

• add(): For adding a single element O(1) . Adding n element in array list takes O(n).
• add(index, element): adding element in particular index in average runs in O(n) time
• get(): is always a constant time O(1) operation
• remove(): runs in linear O(n) time. We have to iterate the entire array to find the element fit for removal
• indexOf():  It runs over the whole array iterate through each and every element worst case will be the size of the array n .so, it requires O(n) time
• contains(): implementation is based on indexOf(). So it will also run in O(n) time
• The size, isEmpty, set, iterator, and listIterator operations run in constant time O(1)

Time Complexity

• add() – takes O(1) time. However, worst-case scenario, when a new array has to be created and all the elements copied to it, is O(n).
• add(index, element) – in average runs in O(n) time
• get() – is always a constant time O(1) operation
• remove() – runs in linear O(n) time. We have to iterate the entire array to find the element qualifying for removal
• indexOf() – also runs in linear time. It iterates through the internal array and checking each element one by one. So the time complexity for this operation always requires O(n) time
• contains() – implementation is based on indexOf(). So it will also run in O(n) time