About ArrayList class in Java
What’s ArrayList
The ArrayList class implements the List interface. ArrayList supports dynamic arrays that can grow as needed.
Standard Java arrays are of a fixed length. After arrays are created, they cannot grow or shrink, which means that you must know in advance how many elements an array will hold.
ArrayList are created with an initial size. When this size is exceeded the collection is automatically enlarged. When objects are removed, the array may be shrunk.
If we set the capacity of the ArrayList as a argument, the ArrayList is created with the capacity.
If the capacity is exceeded, this grow function is called. This method implements copying original array with new capacity.
Time Complexity
add(E e) function
The time complexity of the add(E e)
function is 0(1) basically. This is because, ArrayList has internally standard array. But if the capacity of ArrayList is exceeded, it takes 0(N) time in order to copy original array with new capacity.
add(int index, E element) function
In this function case, we have to shift the elements in order to insert the element into middle of the ArrayList. So it takes O(N) time.
remove(int index) function
This method takes O(N) time in order to shift elements as well as add(int index, E element)
.
E get(int index) function
This method takes O(1) time because we can access the element by index