ArrayList in Java

Introduction

Imagine you are hosting a dinner party. If you know exactly 4 people are coming, you can buy a table with exactly 4 chairs. This is like a standard Java Array: its size is fixed at creation. But what if people start bringing unexpected plus-ones? Your fixed-size table is now useless. You need a magical table that automatically extends itself whenever a new guest arrives.

In Java, that magical expanding table is the ArrayList.

ArrayList is part of the Java Collections Framework (implementing the List interface). It provides the speed and random access of a standard array but abstracts away the headache of managing the array's size. It is overwhelmingly the most commonly used data structure in enterprise Java applications due to its balance of simplicity and performance.

Core Concept: How ArrayList Works Under the Hood

The Illusion of Infinite Space

Despite its name, an ArrayList does not actually use any special hardware or OS magic to grow. Under the hood, an ArrayList is simply a wrapper around a standard, fixed-size Java array (e.g., Object[] elementData).

Here is exactly what happens when you use an ArrayList:

1. Initialization: When you create a new ArrayList via new ArrayList<>(), Java creates a tiny empty array. When you add the first element, it typically initializes an internal array of size 10 (the default capacity).
2. Adding Elements: As you add elements, Java simply places them in the internal array at the next available index and increments an internal size counter.
3. The Resize Trigger (Capacity Reached): What happens when you try to add the 11th element? The internal array is full.
4. The Array Copy Magic:
   • The JVM creates a brand new array that is 1.5 times the size of the old one (so, size 15).
   • It uses Arrays.copyOf() (which maps down to a blazing-fast native C++ function System.arraycopy) to copy all 10 old elements into the new array.
   • It throws away the old array (the Garbage Collector will clean it up later).
   • It adds your 11th element to the new array.

Time Complexity

Because of this internal architecture, ArrayList performance characteristics are highly predictable:

• Access by Index (get(i)): $O(1)$ constant time. Lightning fast.
• Add to End (add(e)): Amortized $O(1)$. It's $O(1)$ most of the time, but occasionally $O(N)$ when a resize is triggered.
• Insert/Delete in Middle (add(i, e) / remove(i)): $O(N)$ linear time. If you remove the 1st element from a 1000-element list, Java has to shift 999 elements one spot to the left to fill the gap.

Code Examples

1. Beginner Example: The Basics

Here is how you perform fundamental CRUD (Create, Read, Update, Delete) operations with an ArrayList.

import java.util.ArrayList;
import java.util.List;

public class ArrayListBasics {
    public static void main(String[] args) {
        // ALWAYS program to the interface (List), not the implementation (ArrayList)
        List<String> fruits = new ArrayList<>();
        
        // CREATE
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");
        
        // READ
        System.out.println("First fruit: " + fruits.get(0)); // Output: Apple
        System.out.println("List size: " + fruits.size()); // Output: 3
        
        // UPDATE
        fruits.set(1, "Blueberry"); // Replaces "Banana"
        
        // DELETE
        fruits.remove("Cherry"); // Removes by object value
        fruits.remove(0);        // Removes by index
        
        System.out.println(fruits); // Output: [Blueberry]
    }
}

2. Intermediate Example: Iteration and Primitives

Because Collections in Java can only hold Objects (not primitives like int or double), Java automatically "autoboxes" primitives into their wrapper classes (Integer, Double).

import java.util.ArrayList;
import java.util.List;

public class IterationExample {
    public static void main(String[] args) {
        // Note the use of Integer, not int
        List<Integer> scores = new ArrayList<>();
        scores.add(85);
        scores.add(92);
        scores.add(78);
        scores.add(99);
        
        // Approach 1: Enhanced For-Loop (Preferred for reading)
        int sum = 0;
        for (int score : scores) { // Auto-unboxing happens here
            sum += score;
        }
        System.out.println("Average: " + (sum / scores.size()));
        
        // Approach 2: ForEach with Lambdas (Java 8+)
        scores.forEach(score -> System.out.println("Score: " + score));
        
        // Approach 3: removeIf (Java 8+ safe deletion)
        // Removes all scores lower than 90
        scores.removeIf(score -> score < 90);
        System.out.println("High scores: " + scores); // [92, 99]
    }
}

3. Advanced Example: Capacity Optimization and Concurrency Issues

If you know you are going to add 1 million items to an ArrayList, relying on the default 1.5x resizing strategy will result in dozens of array copies and garbage generation. You can optimize this! Also, standard ArrayList is not thread-safe.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class AdvancedArrayList {
    public static void main(String[] args) {
        
        // 1. CAPACITY OPTIMIZATION
        // If we know we need exactly 1,000,000 items, we pre-allocate the capacity!
        // This prevents ALL resizing overhead.
        List<String> bigList = new ArrayList<>(1_000_000); 
        
        for (int i = 0; i < 1_000_000; i++) {
            bigList.add("Item " + i);
        }
        
        // 2. CONCURRENCY DANGER
        // Standard ArrayList will throw ConcurrentModificationException 
        // or corrupt data if multiple threads modify it simultaneously.
        
        // Solution A: Synchronized wrapper (Lock-based, can be slow)
        List<String> syncList = Collections.synchronizedList(new ArrayList<>());
        
        // Solution B: CopyOnWriteArrayList (Lock-free reading, expensive writes)
        // Great for read-heavy, write-rarely scenarios.
        List<String> threadSafeList = new CopyOnWriteArrayList<>();
        threadSafeList.add("Safe");
    }
}

Common Mistakes Beginners Make

1. Modifying a List while Iterating over it

The Mistake: Using a standard for-each loop to remove items based on a condition.

List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Charlie"));
// WRONG: Throws ConcurrentModificationException
for (String name : names) {
    if (name.equals("Bob")) {
        names.remove(name); 
    }
}

The Fix: Use the removeIf() method (Java 8+) or an explicit Iterator.

// CORRECT
names.removeIf(name -> name.equals("Bob"));

2. Confusing Capacity with Size

The Mistake: Trying to add at an arbitrary index based on the initial capacity.

// We set CAPACITY to 10. The SIZE is still 0!
List<String> list = new ArrayList<>(10); 
// WRONG: Throws IndexOutOfBoundsException
list.add(5, "Hello"); 

The Fix: You can only set or add up to the current size() of the list.

3. Removing by Primitive int Index vs Integer Object

The Mistake: Unintended method resolution when dealing with lists of Integers.

List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));
// Does this remove the integer '10' or the object at index 10?
numbers.remove(10); // ERROR: IndexOutOfBounds. It calls remove(int index).

The Fix: Explicitly cast to Object or Integer if you want to remove by value.

numbers.remove(Integer.valueOf(10)); // Safely removes the value 10

Interview Q&A

Q1: What is the difference between ArrayList and LinkedList? When would you use which? Answer: ArrayList is backed by an array. It provides $O(1)$ random access, but $O(N)$ insertion/deletion in the middle (because elements must shift). LinkedList is backed by a doubly-linked list. It provides $O(1)$ insertion/deletion at the ends, but $O(N)$ access because you must traverse nodes. In 99% of cases, use ArrayList. Modern CPUs are optimized for contiguous memory blocks (cache locality), making ArrayList significantly faster even for some shifting operations.

Q2: What is the default growth factor of an ArrayList? Answer: In modern Java versions, it grows by 50% (1.5x) of its current capacity when it runs out of space. (Specifically, the old capacity is bit-shifted: newCapacity = oldCapacity + (oldCapacity >> 1)).

Q3: Is ArrayList thread-safe? Answer: No. If multiple threads access an ArrayList concurrently, and at least one modifies it structurally, it must be synchronized externally. Otherwise, it will result in data corruption or a ConcurrentModificationException.

Q4: How does ArrayList prevent memory leaks when removing an element? Answer: When you call remove(), the elements are shifted to the left. The ArrayList implementation explicitly sets the last position of the internal array to null (elementData[--size] = null;). This removes the strong reference, allowing the Garbage Collector to reclaim the object.

Q5: Why does ArrayList implement the RandomAccess interface? Answer: RandomAccess is a marker interface (it has no methods). It simply flags to the JVM and collection utilities (like Collections.binarySearch) that this specific list supports fast, constant-time $O(1)$ access, allowing algorithms to optimize their behavior dynamically.

Practice Problems

1. The Merger:

   • Write a method public static List<Integer> mergeLists(List<Integer> a, List<Integer> b) that takes two ArrayLists of integers and returns a single new ArrayList containing all elements from both, alternating between them (e.g., A1, B1, A2, B2).

2. The Capacity Test:

   • Write a program that creates an ArrayList without an initial capacity, adds 1 million random strings, and times how long it takes.
   • Do it again, but this time initialize the ArrayList with new ArrayList<>(1_000_000). Compare the execution times.

3. Custom Filter:

   • Create an ArrayList of custom Employee objects (fields: name, salary).
   • Using only the removeIf method and a lambda expression, remove all employees who make less than $50,000.

Summary

• ArrayList is a dynamic, resizable array. It is the default, go-to data structure for ordered collections in Java.
• It offers $O(1)$ read access and amortized $O(1)$ appending.
• Under the hood, it uses a standard fixed array. When full, it creates a new array 1.5x the size and copies elements over.
• It is not thread-safe. Use CopyOnWriteArrayList or external synchronization for multithreaded environments.
• Always use the List interface type for the variable declaration to remain decoupled from the specific implementation.