Internal working of ArrayList: Source Code, Examples, and Practical Insights

Introduction

In Java, collections are essential for handling dynamic data where the size of elements isn’t fixed at compile time. Arrays provide constant-time access, but they come with a limitation: fixed size. Once declared, the size of an array cannot be changed. That’s where ArrayList comes in — it combines the benefits of arrays (random access) with the flexibility of dynamic resizing.

ArrayList is one of the most widely used classes in the Java Collections Framework (JCF). It is part of the java.util package and is ideal for scenarios where frequent retrieval operations are more common than frequent insertions or deletions in the middle of the list.

ArrayList Hierarchy in Collections Framework

Here’s how ArrayList fits into the JCF hierarchy:


java.lang.Object
   ↳ java.util.AbstractCollection<E>
       ↳ java.util.AbstractList<E>
           ↳ java.util.ArrayList<E>

ArrayList implements List, RandomAccess, Cloneable, and Serializable.

Arrays vs ArrayList vs LinkedList

Feature	Array	ArrayList	LinkedList
Size	Fixed at creation	Dynamic (resizes automatically)	Dynamic
Access (get by index)	O(1)	O(1)	O(n)
Insertion/Deletion in middle	Expensive (shift elements)	Expensive (shift elements)	Efficient (just relink nodes)
Memory overhead	Low (direct elements)	Medium (backed by Object[])	High (extra node objects)
Use case analogy	A fixed-size tray with N compartments	A stretchable tray that expands when needed	A chain of linked boxes connected by pointers

Basic Usage of ArrayList

Initialization


import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        // Empty initialization
        ArrayList<String> list1 = new ArrayList<>();

        // With initial capacity
        ArrayList<Integer> list2 = new ArrayList<>(20);

        // From another collection
        List<String> list3 = new ArrayList<>(Arrays.asList("A", "B", "C"));
    }
}

Adding, Removing, Accessing Elements


ArrayList<String> fruits = new ArrayList<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Mango");

System.out.println(fruits.get(1)); // Banana

fruits.remove("Apple"); 
fruits.remove(0); // Removes Banana (by index)

fruits.set(0, "Grapes"); // Replace Mango with Grapes

Common Pitfalls


// Autoboxing overhead
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(10); // primitive int converted to Integer object

// Thread safety issue
ArrayList<Integer> unsafeList = new ArrayList<>();
Runnable task = () -> {
    for(int i=0; i<1000; i++) unsafeList.add(i);
};
new Thread(task).start();
new Thread(task).start();
// May cause ConcurrentModificationException

Internal Implementation of ArrayList

ArrayList Backing Structure

ArrayList is backed by an Object[] elementData array. Elements are stored sequentially in this array.


ArrayList
   └── elementData[]: [ A | B | C | null | null | ... ]

Resizing Process

Lazy initialization (pre-Java 8): elementData array was created only when the first element was added.
Java 8+: An empty array (EMPTY_ELEMENTDATA) is created immediately.
Growth logic: When array is full, capacity is increased by 50% (newCapacity = oldCapacity + oldCapacity/2).


Before resize (capacity=3):
[ A | B | C ]

After resize (capacity=4):
[ A | B | C | D ]

Memory Layout and Default Capacity

Default capacity is 10 when the first element is inserted (if not explicitly specified).

Important Source Code Walkthrough

Constructors


public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

Adding Elements


public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

Grow Method


private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5x growth
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

elementData Field


transient Object[] elementData; // non-private to simplify nested class access

Time and Space Complexities

Operation	Array	ArrayList	LinkedList
Access (get)	O(1)	O(1)	O(n)
Add at end	O(1) if space, else O(n)	Amortized O(1)	O(1)
Insert/Remove in middle	O(n)	O(n)	O(1) (with iterator)
Search	O(n)	O(n)	O(n)

Advanced Topics

Thread Safety

Problem: ArrayList is not thread-safe.
Solution 1: Use Collections.synchronizedList().
Solution 2: Use CopyOnWriteArrayList from java.util.concurrent.

Best Practices

Use Array when size is fixed and performance-critical.
Use ArrayList when frequent read operations and occasional resizing are expected.
Use LinkedList when frequent insertions/deletions in middle are required.

Interview Questions on ArrayList Internals

What is the default capacity of ArrayList?
→ 10
How does ArrayList grow internally?
→ Increases capacity by 50% (1.5x).
Is ArrayList thread-safe?
→ No, but you can use Collections.synchronizedList or CopyOnWriteArrayList.
Difference between Array and ArrayList?
→ Arrays are fixed-size, ArrayLists are dynamic with extra methods.
Why is ArrayList random access fast?
→ Because it is backed by a contiguous array, allowing O(1) index lookup.

Conclusion

ArrayList is a powerful and flexible data structure that balances the efficiency of arrays with the adaptability of dynamic collections. Understanding its internal working is crucial for writing performant Java applications and excelling in interviews. Use ArrayList wisely by analyzing time complexities, thread-safety requirements, and real-world use cases.

Search This Blog

DevForgeHub