Part 2 — ArrayList Deep Dive¶

ArrayList is one of the most frequently discussed classes in Java interviews. Interviewers often start with basic questions and then progressively explore internal implementation details, performance, and edge cases.

1. What is ArrayList?¶

ArrayList is a resizable array implementation of the List interface.

Characteristics:

• Preserves insertion order.
• Allows duplicate elements.
• Allows multiple null values.
• Provides fast random access.
• Not thread-safe.

Example:

List<String> fruits = new ArrayList<>();

fruits.add("Apple");
fruits.add("Banana");
fruits.add("Apple");

System.out.println(fruits);
// [Apple, Banana, Apple]

2. Class Hierarchy¶

Object
   │
AbstractCollection
   │
AbstractList
   │
ArrayList

Interfaces:

Iterable
     │
Collection
     │
List
     │
ArrayList

3. Internal Data Structure¶

The most important interview fact:

ArrayList is backed by an array of object references.

Simplified version of the JDK implementation:

public class ArrayList<E> {

    transient Object[] elementData;

    private int size;
}

Where:

• elementData → internal array
• size → number of elements actually stored

Example:

Capacity = 10

Index

0   1   2   3   4   5   6   7   8   9

A   B   C   _   _   _   _   _   _   _

size = 3
capacity = 10

Interview point: size and capacity are different.

4. Size vs Capacity¶

Suppose:

ArrayList<Integer> list = new ArrayList<>(10);

Initially:

Capacity = 10

Size = 0

After:

list.add(10);
list.add(20);
list.add(30);

Capacity = 10

Size = 3

Interviewers commonly ask:

"How do you get the capacity?"

There is no public API to retrieve an ArrayList's capacity. You can only obtain its size(). Capacity is an implementation detail.

5. Default Capacity¶

This changed in Java 8.

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

Many candidates think it immediately allocates an array of size 10.

Not anymore.

Initially:

elementData = EMPTY_ELEMENTDATA

The internal array is shared and empty.

When the first element is added:

list.add("A");

Java allocates an array with a capacity of 10.

Why?

To avoid unnecessary memory allocation when many empty lists are created but never used.

6. Growth Algorithm¶

Suppose capacity is 10.

Add the 11th element.

A new array is created.

Java grows the capacity by approximately 1.5×.

Formula:

newCapacity = oldCapacity + (oldCapacity >> 1)

Since:

oldCapacity >> 1

means integer division by 2,

Example:

10

↓

15

↓

22

↓

33

↓

49

↓

73

This balances memory usage and the frequency of resizing.

7. What Happens During add()?¶

Case 1: Space available

[A B C _ _ _]

↓

Add D

↓

[A B C D _ _]

Time complexity:

O(1)

Case 2: Array full

Capacity = 3

[A B C]

Adding D:

1. Allocate a larger array.
2. Copy existing elements.
3. Add D.

Old

[A B C]

↓

New

[A B C D _ _]

Copying is O(n).

Why is add() considered O(1)?¶

Because most insertions do not trigger resizing.

Resizing occurs occasionally.

The average cost across many insertions is amortized O(1).

Interview example¶

Insert 1,000,000 elements.

Only a small number of insertions require copying; the rest are constant time. The total work grows linearly, giving an average constant cost per insertion.

8. Random Access¶

Suppose:

Index

0 1 2 3 4

A B C D E

Need:

list.get(3);

The JVM calculates:

address = base + index × referenceSize

No traversal is needed.

Time complexity:

O(1)

This is why ArrayList is preferred for frequent indexed access.

9. contains()¶

list.contains("C");

Internally:

Compare A

↓

Compare B

↓

Compare C

↓

Found

Java checks each element using equals().

Worst case:

O(n)

10. remove()¶

Suppose:

[A B C D E]

Remove:

list.remove(1);

Result:

[A C D E _]

Elements after the removed index must shift left.

Time complexity:

O(n)

Removing the last element does not require shifting, so it is effectively O(1).

11. Memory Layout¶

ArrayList stores references, not the objects themselves (for object types).

Example:

List<Employee> list = new ArrayList<>();

Memory layout:

ArrayList

elementData

↓

+------+------+------+
| ref1 | ref2 | ref3 |
+------+------+------+
    |      |      |
    v      v      v
 Employee Employee Employee

The objects reside elsewhere on the heap.

12. Fail-Fast Iterator and modCount¶

Each structural modification increments an internal counter called modCount.

Example:

List<Integer> list = new ArrayList<>();

list.add(10);
list.add(20);

Iterator<Integer> it = list.iterator();

list.add(30);

it.next(); // throws ConcurrentModificationException

Why?

The iterator stores the expected modification count when it is created.

expectedModCount = 2

After:

list.add(30);

modCount = 3

When next() executes:

expectedModCount != modCount

↓

ConcurrentModificationException

Important: This is called fail-fast behavior. It is a best-effort mechanism for detecting concurrent structural modification; it is not a synchronization mechanism or a thread-safety guarantee.

13. ArrayList vs Vector¶

Today, prefer:

• ArrayList for single-threaded use.
• CopyOnWriteArrayList or other concurrent collections when appropriate for multi-threaded use.

14. ArrayList vs LinkedList¶

Despite theoretical advantages of LinkedList, ArrayList often outperforms it in real applications because contiguous memory improves CPU cache utilization.

15. Production Use Cases¶

Use ArrayList when:

• Reading is much more frequent than writing.
• Random access is required.
• Data size is reasonably predictable.
• Order matters.
• Duplicates are allowed.

Examples:

• REST API responses.
• Product catalogs.
• Search results.
• Configuration lists.
• Report generation.

Avoid it when:

• There are frequent insertions/removals in the middle of very large lists.
• Many threads need to modify the list concurrently.

Common Interview Questions¶

Q1. Why is ArrayList faster than LinkedList for get(index)?¶

Because ArrayList uses an array and computes the element's location directly, whereas LinkedList must traverse nodes.

Q2. Why is add() amortized O(1) instead of O(1)?¶

Occasional resizing requires allocating a larger array and copying all elements, making some insertions O(n). Averaged over many insertions, the cost is constant.

Q3. Why does removing from the middle take O(n)?¶

All subsequent elements must be shifted one position to fill the gap.

Q4. What is modCount?¶

An internal counter that tracks structural modifications to detect concurrent modification during iteration.

Q5. Does ArrayList store objects?¶

For object types, it stores references to objects, not the objects themselves.

Q6. Is ArrayList synchronized?¶

No. It is not thread-safe. External synchronization or a concurrent collection is required for safe concurrent modification.

Complexity Summary¶

Key Takeaways¶

• ArrayList is backed by a dynamically resized array.
• It offers O(1) indexed access.
• Appending is amortized O(1) because resizing is infrequent.
• Insertions and removals in the middle are O(n) due to element shifting.
• modCount underpins fail-fast iterators.
• size and capacity are distinct concepts.
• In practice, ArrayList is usually the default List implementation unless a specific workload justifies another choice.

Next: Part 3 — LinkedList Deep Dive, where we'll examine node structure, head/tail pointers, traversal strategy, deque operations, memory overhead, and why LinkedList is often less efficient than many developers expect.