Internal Working of ArrayLists

 In Java, ArrayLists are a commonly used data structure that allows for dynamic resizing, much like dynamic arrays in other programming languages. ArrayLists use normal arrays internally to implement this dynamic resizing functionality. Specifically, if the internal array of an ArrayList becomes full, it creates a new array of double size and copies the elements from the previous array to this newly created array. Once the elements have been copied, the space allocated to the old array is then freed.

It is important to note that this is a general implementation of dynamic arrays, and the actual implementation of ArrayLists may vary from version to version. For example, in Java 1.8, it is claimed by some sources like StackOverflow and Wikipedia that Java pre-allocates space for 10 items and creates a new space of size 1.5 times instead of double when the old space becomes full.

One major advantage of ArrayLists is that they have all the advantages of normal arrays, since they use arrays internally. Two major advantages of arrays are their cache friendliness and the ability to access elements randomly.

The amortized time complexity of adding an element to the end of an ArrayList (dynamic array) is O(1), although the worst-case time complexity is still O(N). Therefore, it is more advisable to use normal arrays over ArrayLists if you know the number of elements you will be storing beforehand.

To better understand the internal implementation of ArrayLists and how the amortized time complexity of adding an element is O(1), let's consider an example. Suppose we create an empty ArrayList and then insert 100 items into it using a for loop.

In this example, let's assume that the ArrayList initially contains an array of size 10, and that a new array of double the size is created whenever the old array becomes full.

Since the initial array can hold 10 elements, we can easily insert the first 10 elements. For the 11th element, a new array of size 20 is created, and the last 10 elements from the previous array are copied to it before proceeding with the insertion. Similarly, for the 21st element, a new array of size 40 is created, and the last 20 elements are copied to it before proceeding. This process continues as necessary until the 100 elements have all been inserted.

The amortized time complexity is defined as the average time complexity for any operation. Let's assume that there are N items initially and that we double the size of the array every time it becomes full.

import java.util.*;

class Gfg{
    public static void main (String[] args) {
        
        // Create a ArrayList
        ArrayList<Integer> al = new ArrayList<Integer>();
    
        for(int i=1; i<=100; i++)
        {
            al.add(i);
        }
    
        // Print the ArrayList
        System.out.println(al);
    }
}

Therefore, the average time to insert (N + 1) items can be calculated as follows: { θ(1) + θ(1) + θ(1) +.......+ θ(1) + θ(N)} / (N + 1)

Since the array initially has a capacity of N, inserting the first N items will cost θ(1) time. However, for the last item (the (N + 1)th item), it will cost θ(N) as we have to copy the first N items to the newly created array of double size. Therefore, the average time can be calculated as {θ(N) + θ(N)}/(N + 1) = θ(1).

In summary, ArrayLists are a useful data structure in Java that allow for dynamic resizing through the use of normal arrays internally. While the worst-case time complexity for adding an element to an ArrayList is still O(N), the amortized time complexity is O(1), making ArrayLists a great option for situations where the number of elements to be stored is unknown or likely to change.