Collections

ArrayList

ArrayList is a class in java.util that implements the List interface using a resizable (dynamic) array internally.

In simple words:

ArrayList = An array that grows and shrinks automatically

Key Features

Feature	ArrayList
Internal structure	Dynamic array
Order	Insertion order maintained
Duplicates	Allowed
Null values	Allowed (multiple)
Index access	Yes, fast
Thread safe	No (not synchronized)
Default capacity	10 (allocated on the first `add()`)

Creating an ArrayList

import java.util.*;

// 1. Empty list
List<String> a = new ArrayList<>();

// 2. With initial capacity
List<String> b = new ArrayList<>(50);

// 3. From another collection
List<String> c = new ArrayList<>(List.of("A", "B", "C"));

new ArrayList<>(50) sets the capacity, not the size. The list still has 0 elements.

Common Methods

From `Collection` (shared with all collections)

add(), addAll(), remove(Object), removeAll(), retainAll(), removeIf(), contains(), containsAll(), size(), isEmpty(), clear(), iterator(), toArray(), stream()

Specific to `List` (index based)

Method	Purpose
`add(int index, E e)`	Inserts at a position (shifts others right)
`get(int index)`	Returns the element at the index
`set(int index, E e)`	Replaces the element, returns the old one
`remove(int index)`	Removes by index, returns the removed element
`indexOf(Object o)`	First index of the element, or -1
`lastIndexOf(Object o)`	Last index of the element, or -1
`subList(from, to)`	View of a range (`to` is exclusive)
`sort(Comparator c)`	Sorts the list
`replaceAll(UnaryOperator)`	Replaces every element using a function

Example

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> fruits = new ArrayList<>();

        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Mango");
        fruits.add(1, "Orange");          // insert at index 1

        System.out.println(fruits);       // [Apple, Orange, Banana, Mango]
        System.out.println(fruits.get(2)); // Banana

        fruits.set(0, "Grapes");          // replace
        System.out.println(fruits);       // [Grapes, Orange, Banana, Mango]

        fruits.remove("Banana");          // remove by object
        fruits.remove(0);                 // remove by index
        System.out.println(fruits);       // [Orange, Mango]

        System.out.println(fruits.indexOf("Mango"));   // 1
        System.out.println(fruits.contains("Apple"));  // false
        System.out.println(fruits.size());             // 2
    }
}

Common Trap: `remove(int)` vs `remove(Object)`

With List<Integer>, the two overloads cause confusion.

List<Integer> nums = new ArrayList<>(List.of(10, 20, 30));

nums.remove(1);                    // removes at INDEX 1 -> [10, 30]
nums.remove(Integer.valueOf(10));  // removes the VALUE 10 -> [30]

text

1remove(1)                    → treated as an index (int)
2remove(Integer.valueOf(1))   → treated as an object (value)

How ArrayList Works Internally

text

1Elements stored in:  Object[] elementData
2Fields:              size (number of elements), capacity (array length)

The array starts empty. On the first add(), it gets a capacity of 10.
When the array is full and a new element arrives, ArrayList creates a bigger array, copies the old elements, and discards the old array.
The new capacity is about 1.5 times the old one: newCapacity = oldCapacity + (oldCapacity >> 1).

text

1Capacity 10 (full)  →  add one more  →  new array of capacity 15  →  copy 10 elements  →  add new one

Method	Purpose
`ensureCapacity(n)`	Pre-allocates space to avoid repeated resizing
`trimToSize()`	Shrinks the array to the current size

If you know roughly how many elements are coming, pass the capacity in the constructor to avoid resizing.

Time Complexity

Operation	Complexity	Why
`get(i)` / `set(i, e)`	O(1)	Direct array index access
`add(e)` (at end)	O(1) amortized	Occasionally O(n) when resizing
`add(i, e)` (middle/start)	O(n)	Elements must shift right
`remove(i)` (middle/start)	O(n)	Elements must shift left
`remove(Object)`	O(n)	Search first, then shift
`contains(o)` / `indexOf(o)`	O(n)	Linear search

text

1Insert at index 1:   [A, B, C, D]  →  shift B, C, D right  →  [A, X, B, C, D]

Iterating an ArrayList

List<String> list = new ArrayList<>(List.of("A", "B", "C"));

// 1. Classic for loop (index based)
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// 2. For-each
for (String s : list) {
    System.out.println(s);
}

// 3. Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

// 4. ListIterator (forward and backward)
ListIterator<String> li = list.listIterator();
while (li.hasNext()) {
    System.out.println(li.next());
}

// 5. forEach + lambda
list.forEach(System.out::println);

Do not call list.remove() inside a for-each loop. It causes ConcurrentModificationException. Use Iterator.remove() or removeIf().

Sorting an ArrayList

List<Integer> nums = new ArrayList<>(List.of(30, 10, 20));

Collections.sort(nums);                          // [10, 20, 30]
nums.sort(Comparator.reverseOrder());            // [30, 20, 10]

List<String> names = new ArrayList<>(List.of("Ravi", "Anita", "Kiran"));
names.sort(null);                                // natural order: [Anita, Kiran, Ravi]
names.sort(Comparator.comparing(String::length)); // by length

Converting Between Array and ArrayList

// Array -> ArrayList
String[] arr = {"A", "B", "C"};
List<String> list = new ArrayList<>(Arrays.asList(arr));

// ArrayList -> Array
String[] back = list.toArray(new String[0]);

Arrays.asList(arr) alone returns a fixed-size list. add() or remove() on it throws UnsupportedOperationException. Wrap it in new ArrayList<>(...) to get a fully resizable list.

ArrayList with Custom Objects

class Student {
    int id;
    String name;

    Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return id + " - " + name;
    }
}

public class Main {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student(2, "Anita"));
        students.add(new Student(1, "Ravi"));

        students.sort(Comparator.comparingInt(s -> s.id));
        System.out.println(students);   // [1 - Ravi, 2 - Anita]
    }
}

contains(), indexOf(), and remove(Object) use equals(). For custom classes, override equals() (and hashCode()) or these methods will not find equal-looking objects.

Fail-Fast Behavior

ArrayList's iterator is fail-fast. If the list is structurally modified (add/remove) after the iterator is created, other than through the iterator itself, it throws ConcurrentModificationException. It tracks this with an internal counter called modCount.

Making ArrayList Thread Safe

Option	Example
Synchronized wrapper	`Collections.synchronizedList(new ArrayList<>())`
Concurrent alternative	`CopyOnWriteArrayList`

ArrayList vs Array

Feature	Array	ArrayList
Size	Fixed	Dynamic
Types stored	Primitives and objects	Objects only (wrappers)
Length	`arr.length`	`list.size()`
Methods	Few	Many
Generics	Not supported	Supported

When to Use ArrayList

text

1Mostly reading elements by index?              → ArrayList ✅
2Mostly adding at the end?                      → ArrayList ✅
3Frequent insert/delete in the middle or front? → LinkedList / ArrayDeque
4Need thread safety?                            → CopyOnWriteArrayList
5Need unique elements?                          → Set

Key Benefits

Benefit	Explanation
Dynamic size	Grows automatically
Fast access	O(1) by index
Easy to use	Rich set of methods
Cache friendly	Elements stored contiguously in memory

Limitations

Limitation	Reason
Slow insert/delete in the middle	Elements must be shifted
Not thread safe	No synchronization
Resizing cost	New array allocation and copying
Stores objects only	Primitives need wrapper classes (boxing)

Interview Definition

ArrayList is a resizable-array implementation of the List interface that maintains insertion order, allows duplicates and nulls, provides O(1) random access, and is not synchronized.

Remember

ArrayList = dynamic array. Fast reads by index, slow inserts and deletes in the middle, grows by about 1.5x when full.

Next TopicClass Relationships

ArrayList

Key Features

Creating an ArrayList

Common Methods

From Collection (shared with all collections)

Specific to List (index based)

Example

Common Trap: remove(int) vs remove(Object)

How ArrayList Works Internally

Time Complexity

Iterating an ArrayList

Sorting an ArrayList

Converting Between Array and ArrayList

ArrayList with Custom Objects

Fail-Fast Behavior

Making ArrayList Thread Safe

ArrayList vs Array

When to Use ArrayList

Key Benefits

Limitations

Interview Definition

Remember

From `Collection` (shared with all collections)

Specific to `List` (index based)

Common Trap: `remove(int)` vs `remove(Object)`