ArrayList Implementation in Java

ArrayList is a class of Java Collection framework. It uses a dynamic array for storing the objects. It is much similar to Array, but there is no size limit in it. We can add or remove the elements whenever we want. We can store the duplicate element using the ArrayList; It manages the order of insertion internally.

The ArrayList class is much more flexible than the traditional Array. It implements the List interface to use all the methods of List Interface. It takes place in java.util package. Understanding its implementation is fundamental for any Java developer striving for proficiency and elegance in their code. In this section, we will discuss the ArrayList implementation in Java, along with its features, advantages, and best practices.

The ArrayList class inherits the AbstractList class and implements the List Interface. The elements of it can be randomly accessed. It cannot be used for primitive types such as int, char, etc.; for these data types, we need a wrapper class.

The difference between Array and ArrayList is that Arraylist provides a dynamic array that can be expanded when needed. In Array, we have to specify the size of the Array during initialization, but it is not necessary for ArrayList. By default, it takes its size to 10.

ArrayList class can be declared as follows:

ArrayList can be defined as follows:

Consider the following example:

File Name: ArrayListLExample.java

Output:

 List objects are: [Sam, Sandy, Joe, Arya, Nik] After Removing Nik, List Objects are: [Sam, Sandy, Joe, Arya] 

From the above example, we can see how we can add or remove the List's objects.

Let's understand how it works internally:

How ArrayList Works Internally?

When we initialize an ArrayList using the below syntax:

It creates an Array with the default capacity, which is 10. It invokes the default constructor of the ArrayList class. It uses an empty array instance to create the new object, and the following code is executed by the Java compiler:

in Java 7 or previous version:

in Java 8 or later version:

In the above code snipet, we can see an empty ArrayList is internally created with the default capacity, which is 10. When we add the first element in it, it will be expanded to DEFAULT_CAPACITY.

ArrayList uses an Object [] Array to add, remove, and traverse the element.

For the prior versions of Java than Java 8, it specifies the objects as follows:

In the above code snippet, we can see the array size will be equal to the specified Array.

We can also define the List with the specific capacity. When we provide an initial capacity, the ArrayList constructor is invoked internally to specify the Array internally. For example, if we define an array list with the capacity of 20, we have to define the ArrayList as follows:

Then the following code will be executed by the Java compiler:

In Java 7 or previous versions:

From the above code, we can see the array size will be equal to the specified Array.

In Java 8 or later versions:

From the above code, we can see the array size will be equal to the specified Array.

We can also create an object of ArrayList for a specific collection by executing the below line of code:

The above code will create a non-empty list having the objects of LinkedList.

Key Features of ArrayList

• Dynamic Resizing: Unlike traditional arrays in Java with fixed sizes, ArrayLists dynamically resize themselves, allowing flexibility in storing elements without worrying about the size constraints.
• Random Access: ArrayList provides constant-time positional access for retrieving or setting elements, making it efficient for random access operations.
• Support for Generics: ArrayLists support generics, enabling type-safe collections and ensuring compile-time type checking, thereby enhancing code reliability.
• Iterable Interface: ArrayList implements the Iterable interface, facilitating easy traversal through elements using enhanced for loops or iterators.

How the ArrayList Grows Dynamically?

When we add a new object to the ArrayList, it will check for the initial size of the ArrayList whether it has space or not. If there is enough space for the new object, it will add simply using the add() method. If there is not enough space to add a new object, it will dynamically increase the size of the Array by that much capacity.

Consider the following implementation of the add() method (In Java 7 or later):

In the above code the above code,

• The ensureCapacityInternal() is used to determine the current size of occupied objects and maximum size of Array.
• The grow method is used to expand the new size of Array.
• The minCapacity determines the current size of the objects; it includes the new specified elements.
• copyOf used to copy the specified Array.
• max is used to return the maximum or largest value from the passed arguments.

ArrayList Implementation Details

ArrayList in Java is internally backed by an array of objects (Object[]) to store elements. Let's explore some crucial implementation details:

Capacity and Size: ArrayList maintains two main parameters: capacity and size. Capacity represents the current size of the internal array, while size denotes the number of elements present in the ArrayList.

Resizing Strategy: When elements are added beyond the current capacity, ArrayList automatically increases its capacity to accommodate new elements. It typically doubles the size of the internal array to maintain amortized constant-time complexity for append operations.

Performance Considerations: While ArrayList provides efficient random access and insertion/removal at the end of the list, inserting or removing elements from the middle incurs higher computational overhead due to array copying.

Iterating through ArrayList: ArrayList offers various ways to iterate through its elements, including traditional for loops, enhanced for loops, and iterators obtained via the iterator() method.

Performance of ArrayList

In the ArrayList, the add operation requires o(n) time; other operations are run in linear time.

The size, isEmpty, get, set, iterator, and listIterator tasks run in a constant time of O(1).

Summary

• ArrayList is a customizable array implementation; we can dynamically add objects in the List.
• ArrayList uses an Object class array to store the objects.
• By default, ArrayList creates an array of size 10.
• While initializing the Array, we can specify the size of Array.
• When adding or removing elements, the space in the Array will automatically be adjusted.

Its dynamic resizing, efficient random access, and support for generics make it a versatile choice for managing collections of elements. By understanding its internals, leveraging best practices, and being cognizant of performance considerations, developers can harness the full potential of ArrayLists to write efficient and robust Java code.