ArrayList

#Introduction

If there is one Collection class you must master for Java interviews, it is ArrayList.

Interviewers don't just ask how to use ArrayList; they expect you to understand how it works internally, how it grows, why operations have different time complexities, and when it should or should not be used.

#What is ArrayList?

ArrayList is a resizable array implementation of the List interface.

Package:

java.util.ArrayList

Declaration:

public class ArrayList<E>
        extends AbstractList<E>
        implements List<E>,
                   RandomAccess,
                   Cloneable,
                   Serializable

#Characteristics of ArrayList

• Maintains insertion order
• Allows duplicate elements
• Allows multiple null values
• Index-based access
• Dynamically grows
• Not synchronized
• Not thread-safe

#Internal Structure

Many beginners think ArrayList is some magical data structure. It is not. Internally it is simply an array of objects.

Internally Java stores elements in:

transient Object[] elementData;

This single array is the heart of ArrayList.

#Creating an ArrayList

ArrayList<String> list = new ArrayList<>();

What actually happens? Java creates an empty ArrayList.

Default Constructor

Internally:

elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

Initially Size = 0 and Capacity = 0. The internal array is shared and empty.

What Happens on the First add()?

list.add("Java");

Now Java creates the first internal array. The default capacity becomes 10.

#Size vs Capacity

This is one of the favourite interview questions.

Size

The number of actual elements.

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);

Size = 2.

Capacity

The total number of elements that can be stored before resizing. Current capacity = 10.

Capacity Example

#Growth Algorithm

Interview favourite. Suppose the current capacity is 10 and we need one more element. Java creates a new capacity of 15.

newCapacity = oldCapacity + (oldCapacity >> 1)

Meaning: old + 50%.

Why Not Double the Size?

Imagine storing 10 million objects. Doubling on every resize would waste large amounts of memory. Using 1.5× growth balances:

• Memory usage
• Performance
• Fewer reallocations

#What Happens During Resize?

Suppose capacity = 10 and you insert the 11th element.

Resize Cost

This copy operation is expensive, because all elements are copied again. Complexity: O(n).

#Why is add() O(1)?

Interview favourite. Most insertions occur at the end:

list.add(100);

Java simply places the element in the next free slot → O(1). Only during resizing does it cost O(n). Therefore the average complexity is amortized O(1).

#Amortized Time Complexity

#ensureCapacity()

Sometimes we already know how many elements we need.

ArrayList<Employee> list = new ArrayList<>();
list.ensureCapacity(10000);

Benefits:

• Reduces resizing
• Improves performance
• Fewer array copies

Useful when loading large datasets from files or databases.

#trimToSize()

Suppose capacity = 1000 but size = 50. Extra memory is wasted. Use:

list.trimToSize();

Now capacity = 50. Memory optimized.

#Accessing Elements

list.get(5);

How? Arrays support direct indexing:

Address + (Index × Element Size)

Therefore O(1). Random access is extremely fast.

#Why Does ArrayList Implement RandomAccess?

Notice implements RandomAccess. RandomAccess is a marker interface — it contains no methods. It tells Java:

This collection supports fast random access.

Algorithms can optimize based on this information.

#Insertion

Adding at the end — list.add(100); → O(1).

Adding at the beginning — list.add(0, 100);

#Removal

Removing the last element — list.remove(list.size() - 1); → O(1).

Removing the first element — list.remove(0); — the remaining elements shift left.

#contains()

list.contains("Java");

Java searches sequentially: element 1 → element 2 → element 3 … Complexity: O(n).

#Iteration

for (String s : list)

Complexity O(n), but fast because memory is contiguous. This makes ArrayList more CPU cache-friendly than LinkedList.

#Null Values and Duplicates

ArrayList allows multiple null values:

list.add(null);
list.add(null);

Duplicates are allowed:

list.add("Java");
list.add("Java");

[Java, Java]

#Thread Safety

How to Make It Thread-Safe?

Option 1:

List<String> list = Collections.synchronizedList(new ArrayList<>());

Option 2: CopyOnWriteArrayList (covered later).

#ArrayList vs Array

#ArrayList vs LinkedList

*Amortized O(1)

#Internal Source Code (Simplified)

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

A resize happens only if required. Otherwise, the element is simply placed into the next free slot.

#Time Complexity