Internal Working of ArrayList in Java

Introduction

An ArrayList in Java is a part of the java.util package and is used to store dynamic arrays. Unlike arrays, ArrayList can grow dynamically when elements are added, making it more flexible.

---

1. Data Structure Used

ArrayList is implemented using an array internally. The key feature of ArrayList is its ability to resize dynamically when elements are added or removed.

Implementation in Java:

public class ArrayList<E> extends AbstractList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elementData;
    private int size;
}

• The elementData array holds the actual elements.
• The size variable tracks the number of elements currently in the list.
• The default initial capacity is 10.

---

2. How Elements are Stored and Accessed

Adding an Element

When add() is called:

1. If there is space, the element is added at elementData[size], and size is incremented.
2. If there is no space, the array is resized (doubled in capacity), and all existing elements are copied into the new array.

Example:

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
System.out.println(list); // Output: [Apple, Banana, Cherry]

Retrieving an Element

Elements are accessed using the get() method, which uses direct indexing (O(1) time complexity):

System.out.println(list.get(1)); // Output: Banana

Removing an Element

When remove(index) is called:

1. The element at the given index is removed.
2. All subsequent elements are shifted left by one position.
3. size is decremented.

Example:

list.remove(1); // Removes "Banana"
System.out.println(list); // Output: [Apple, Cherry]

---

3. Resizing Mechanism

How ArrayList Expands

• When an ArrayList exceeds its capacity, it creates a new array of 1.5 times the old size (since Java 1.8).
• All elements from the old array are copied into the new array.
• This resizing mechanism ensures efficient memory allocation.

Example:

ArrayList<Integer> numbers = new ArrayList<>(2);
numbers.add(1);
numbers.add(2);
numbers.add(3); // Triggers resizing
System.out.println(numbers); // Output: [1, 2, 3]

Initial Capacity Optimization

If you know the expected size, you can optimize memory usage:

ArrayList<Integer> list = new ArrayList<>(100); // Avoids multiple resizings

---

4. Performance Analysis

Operation	Time Complexity
Add at End	O(1) (Amortized)
Add at Index	O(n) (Shifting required)
Get Element	O(1) (Direct Access)
Remove Element	O(n) (Shifting required)

Comparison with LinkedList

Feature	ArrayList (O(1) Access)	LinkedList (O(n) Access)
Access by Index	✅ Fast (O(1))	❌ Slow (O(n))
Insert at End	✅ Fast (O(1))	✅ Fast (O(1))
Insert at Beginning	❌ Slow (O(n))	✅ Fast (O(1))
Memory Overhead	✅ Low	❌ High (due to node pointers)

---

5. Key Takeaways

✔ ArrayList is based on an array, offering fast random access.

✔ Expands dynamically when full, with a resizing factor of 1.5x.

✔ Adding/removing at the end is fast (O(1)), but inserting/removing in the middle requires shifting (O(n)).

✔ For frequent insertions/deletions, use LinkedList; for fast random access, use ArrayList.

Understanding the internal working of ArrayList helps optimize Java applications and choose the right data structure for performance-sensitive tasks.