ArrayList is one of the most commonly used data structures in Java, offering dynamic resizing capabilities that make it highly flexible for storing and manipulating lists of elements.
How Does ArrayList Work Internally in Java?
ArrayList in Java offers dynamic resizing capabilities, allowing it to adapt to changing requirements and efficiently store lists of elements. By understanding its internal implementation and dynamic resizing mechanism, you can leverage ArrayList effectively in your Java programs
In this blog post, we'll dive into the internals of ArrayList, exploring how it achieves dynamic resizing and providing detailed examples to illustrate its functionality.
What is ArrayList?
ArrayList is a part of the Java Collections Framework and implements the List interface. It provides a resizable array implementation of the List interface, allowing you to add, remove, and access elements with ease. Unlike arrays, ArrayList can dynamically resize itself to accommodate a varying number of elements.
Internal Implementation:
At its core, ArrayList uses an array to store elements internally. However, unlike traditional arrays, ArrayList manages this array dynamically, resizing it as needed to accommodate additional elements. Here's a breakdown of how ArrayList achieves dynamic resizing:
- Initial Capacity:
- When you create an ArrayList, it starts with an initial capacity, typically 10.
- This initial capacity represents the size of the internal array used to store elements.
- Adding Elements:
- When you add elements to the ArrayList using the add() method, it checks if there's enough space in the internal array to accommodate the new elements.
- If there is sufficient space, the elements are added to the end of the array.
- If there isn't enough space, ArrayList performs the following steps:
- Creates a new array with increased capacity, often double the current capacity.
- Copies all existing elements from the old array to the new array.
- Adds the new elements to the end of the new array.
- Updates the internal reference to point to the new array.
- Dynamic Resizing:
- ArrayList achieves dynamic resizing by dynamically creating larger arrays and copying elements from the old array to the new one when the current capacity is exceeded.
- By doubling the capacity each time, ArrayList ensures that adding elements remains efficient on average.
Example:
Let's illustrate the dynamic resizing behavior of ArrayList with a simple example:
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
// Add elements to the ArrayList
for (int i = 1; i <= 20; i++) {
list.add(i);
System.out.println("Size: " + list.size() + ", Capacity: " + getCapacity(list));
}
}
// Method to get the capacity of an ArrayList using reflection
private static int getCapacity(ArrayList<?> list) {
try {
java.lang.reflect.Field field = ArrayList.class.getDeclaredField("elementData");
field.setAccessible(true);
return ((Object[]) field.get(list)).length;
} catch (Exception e) {
e.printStackTrace();
return -1;
}
}
}In this example, we create an ArrayList and add elements to it. We also print the size and capacity of the ArrayList after each addition. Notice how the capacity increases dynamically as elements are added beyond the initial capacity.
In Java, the ArrayList class is an implementation of the List interface that uses a dynamic array to store elements. Here's a brief overview of how it works and is implemented internally:
Dynamic Array: ArrayList internally uses an array to store elements. Initially, this array is of a default size, often 10. When elements are added beyond the capacity of the array, a new, larger array is created, and the elements from the old array are copied into the new one. This allows ArrayList to dynamically grow and shrink as elements are added or removed.
Capacity Management: ArrayList maintains two variables to track its capacity and size. Capacity represents the total number of elements the internal array can hold without resizing, while size represents the number of elements currently stored in the list.
Adding Elements: When you add an element to an ArrayList, it checks if there's enough capacity in the internal array. If there is, the element is added at the end of the array. If not, a new array is created with increased capacity, and elements from the old array are copied into the new one, along with the new element.
Accessing Elements: Elements in an ArrayList can be accessed using their index. Since ArrayList uses an array internally, accessing an element by index is a constant-time operation, O(1).
Removing Elements: When you remove an element from an ArrayList, it shifts all subsequent elements to the left to fill the gap created by the removal. This operation can be time-consuming if the element being removed is near the beginning of the list, as it requires shifting many elements. On average, removal from an ArrayList is O(n), where 'n' is the number of elements in the list.
Iterating over Elements: ArrayList provides efficient iteration over its elements using enhanced for loops or iterators. It doesn't have to traverse any intermediate data structures since it stores elements in a contiguous array.
Null Elements: ArrayList allows null elements to be stored.
Overall, ArrayList provides dynamic resizing of the underlying array, efficient random access, and efficient iteration over elements, making it a versatile choice for storing and manipulating lists of elements in Java.
How does it implement?
Arrays in Java have a fixed size once they're created. However, ArrayList achieves dynamic resizing by internally managing an array and resizing it when necessary. Here's how it works:
Initial Capacity: When you create an ArrayList, it starts with an initial capacity, usually 10. This initial capacity is the size of the internal array.
Adding Elements: When you add elements to the ArrayList, it checks if there's enough space in the internal array to accommodate the new elements. If there is, it simply adds the elements to the end of the array. If there isn't enough space, it performs the following steps:
- It creates a new array with increased capacity, typically by doubling the current capacity.
- It copies all existing elements from the old array to the new array.
- It adds the new elements to the end of the new array.
- Finally, it updates the internal reference to point to the new array.
Dynamic Resizing: This process of creating a new array with increased capacity and copying elements is how ArrayList achieves dynamic resizing. By doubling the capacity each time, it ensures that adding elements remains efficient on average.
Capacity Management: ArrayList maintains two variables: elementData, which is the reference to the internal array, and size, which represents the number of elements currently stored in the ArrayList. As elements are added, the size increases, and when it reaches the capacity of the internal array, the array is resized as described above.
Performance: While dynamic resizing allows ArrayList to be flexible, it's important to note that resizing the internal array involves a performance cost, as it requires allocating memory and copying elements. However, ArrayList optimizes this process by doubling the capacity each time, which amortizes the cost over multiple additions..