ArrayList

1 The story

The waiting list that wouldn't fit

Kabir's train-booking practice project keeps the waiting list in String[] waitlist = new String[10]. On a festival weekend the 11th passenger crashes the app with ArrayIndexOutOfBoundsException, and cancelling passenger 3 leaves a hole that every loop must skip.

Riya

Sir, can't Kabir just make the array bigger? Say 1000?

Arjun Sir

And waste memory on quiet days, and still crash on the busiest one. Use an ArrayList. It holds an array inside too, but when that array fills up it quietly makes a bigger one and copies everything across.

Riya

What about the gap when someone cancels?

Arjun Sir

remove shifts everyone after them one place left, so positions stay continuous. That shifting has a cost, though, and it's one of several things worth knowing about what happens inside. Let's open it up.

2 Definition

What is an ArrayList?

Formal definition (write this in exams)

java.util.ArrayList<E> is a resizable-array implementation of the List interface. It maintains insertion order, allows duplicates and null, and provides constant-time random access by index. Internally it stores elements in an Object[] called elementData and tracks the number of elements in size; when the array is full, it allocates a larger array (about 1.5 times the old capacity) and copies the elements. ArrayList is not synchronised, and its iterators are fail-fast.

In simple words

A list backed by an array that grows when needed. Reading position 5 is instant; inserting or deleting in the middle means shifting the elements after it.

Words you'll meet in this lesson

SizeHow many elements the list holds: size().

CapacityHow many slots the internal array has. Always ≥ size.

IndexPosition, starting at 0. Valid indexes: 0 to size − 1.

Amortised O(1)Usually instant; occasionally slow (when growing), but cheap on average.

ShiftMoving elements one place to make room or close a gap: O(n).

Fail-fastIterators throw ConcurrentModificationException if the list changes under them.

Cost of each operation

Operation	Cost	Why
`get(i)`, `set(i, x)`	O(1)	Direct array access
`add(x)` at the end	O(1) amortised	Usually a free slot; sometimes grow and copy
`add(i, x)`, `remove(i)`	O(n)	Elements after `i` shift
`contains(x)`, `indexOf(x)`, `remove(x)`	O(n)	Linear search with `equals`
`size()`, `isEmpty()`	O(1)	Reads the counter

Exam tip: new ArrayList<>() starts with an empty array; the default capacity of 10 is allocated on the first add. When full, the new capacity is old + old/2 (10 → 15 → 22 → 33 …). Capacity is not size: size() counts elements, not slots.

3 Types and ways to use it

Everyday ArrayList operations

Add

add(x) at the end, add(i, x) at a position, addAll(other).

grow

Read and search

get(i), indexOf(x), contains(x), size().

read

Change

set(i, x) replaces; sort, Collections.reverse.

update

Remove

remove(i) by index, remove(obj) by value, removeIf, clear.

shrink

The full tour

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

public class Main {
    public static void main(String[] args) {
        List<String> menu = new ArrayList<>();
        menu.add("dosa");
        menu.add("chai");
        menu.add("idli");
        menu.add(1, "vada");                     // insert at index 1: the rest shift right
        System.out.println(menu + " size " + menu.size());

        System.out.println(menu.get(0) + ", " + menu.indexOf("idli") + ", " + menu.contains("poha"));
        menu.set(2, "masala chai");              // replace index 2
        menu.remove("dosa");                     // by value: the rest shift left
        Collections.sort(menu);
        System.out.println(menu);

        for (int i = 0; i < menu.size(); i++) {
            System.out.println(i + ": " + menu.get(i));
        }
    }
}

[dosa, vada, chai, idli] size 4 dosa, 3, false [idli, masala chai, vada] 0: idli 1: masala chai 2: vada

remove(int) or remove(Object)?

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

public class Main {
    public static void main(String[] args) {
        List<Integer> seats = new ArrayList<>(List.of(12, 3, 7));
        seats.remove(1);                          // index 1 → removes 3
        System.out.println(seats);
        seats.remove(Integer.valueOf(12));        // value 12
        System.out.println(seats);
    }
}

[12, 7] [7]

Removing while looping

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

public class Main {
    public static void main(String[] args) {
        List<String> cart = new ArrayList<>(List.of("tea", "coffee", "juice", "tea"));
        try {
            for (String item : cart) {
                if (item.equals("coffee")) cart.remove(item);   // changes the list mid-loop
            }
        } catch (java.util.ConcurrentModificationException e) {
            System.out.println("ConcurrentModificationException");
        }

        cart.removeIf(item -> item.equals("tea"));             // the safe way (a lambda, Lesson 14.1)
        System.out.println(cart);
    }
}

ConcurrentModificationException [juice]

Never call list.remove(…) inside a for-each loop over the same list. The hidden iterator notices the change (modCount) and throws ConcurrentModificationException. Use removeIf, an explicit Iterator with it.remove() (Lesson 11.7), or loop backwards by index.

Rule of thumb: ArrayList is the right default list. If you know roughly how many elements are coming, pass the capacity: new ArrayList<>(5000) avoids repeated growing. If you add and remove mostly at the front, use ArrayDeque instead.

4 Step by step

Inside `add` when the array is full

An empty list has an empty array
```
List<String> w = new ArrayList<>();   // elementData = {} , size = 0
```
Since Java 8 no array of 10 is created up front; many lists stay empty forever, so this saves memory.
First add: capacity 10
add sees there's no room, allocates Object[10], stores the reference in slot 0, and sets size = 1.
Adds 2 to 10: just fill slots
Each add writes into elementData[size] and increments size. O(1), no copying.
The 11th add: grow
size == elementData.length, so grow computes 10 + (10 >> 1) = 15, allocates Object[15], copies the 10 references with Arrays.copyOf, then stores the new element. The old array becomes garbage.
Why it's still fast on average
Growing costs O(n), but it happens rarely and the capacity grows by 50% each time, so the total copying for n adds stays proportional to n: amortised O(1) per add.

5 See it happen

Grow and shift: both views

Left: the list as your code sees it. Right: the internal elementData array, its capacity, and the copying and shifting it does.

Inside an ArrayList 6 steps

What you see

Behind the screen

6 Real-world use

ArrayList in real systems

Whenever code builds a sequence and reads it back in order or by position, an ArrayList is usually underneath.

Watch it with an example: a music app's playlist

A playlist is an ArrayList of songs. Watch jumping to a song (instant), adding at the end (cheap) and inserting at the top (every song moves).

Playlist operations and their cost 4 steps

Animated example

1. Query results

Code that loads rows from a database, or items from a JSON response, collects them into a List (almost always an ArrayList) to display, sort or page through.

SELECT … rows→list.add(row)→shown as a table

2. Carts, playlists and feeds

Items in a cart, songs in a playlist, posts in a feed: ordered, repeatable, and read by position as the screen scrolls.

scroll to row 40→feed.get(40)→instant

3. Batch processing with known sizes

Import jobs that know they'll read 50,000 records create the list with that capacity, avoiding a dozen grow-and-copy steps.

file with 50k lines→new ArrayList<>(50_000)→no resizing

4. A common performance bug

Checking list.contains(id) inside a loop over another big list is O(n × m). Production fixes usually convert the lookup list to a HashSet first.

100k × contains on 100k→HashSet instead→seconds → milliseconds

Examples are simplified. Framework and driver code may use other List types internally.

7 Run the code

A train waiting list

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

public class Main {
    static List<String> waitlist = new ArrayList<>();

    static void join(String name) {
        waitlist.add(name);
        System.out.println(name + " is WL" + waitlist.size());
    }

    static void cancel(String name) {
        int pos = waitlist.indexOf(name);
        if (pos == -1) {
            System.out.println(name + " is not on the list");
            return;
        }
        waitlist.remove(pos);                       // everyone after moves up
        System.out.println(name + " cancelled; list now " + waitlist);
    }

    static void confirmFirst() {
        if (!waitlist.isEmpty()) {
            System.out.println("Seat confirmed for " + waitlist.remove(0));
        }
    }

    public static void main(String[] args) {
        join("Riya");
        join("Kabir");
        join("Om");
        cancel("Kabir");
        confirmFirst();
        System.out.println("Remaining: " + waitlist);
    }
}

Riya is WL1 Kabir is WL2 Om is WL3 Kabir cancelled; list now [Riya, Om] Seat confirmed for Riya Remaining: [Om]

waitlist.add(name)Appends at the end: O(1) amortised. The position is size().
indexOf(name)Linear search with equals; −1 if absent.
remove(pos)Removes by index; later passengers shift up one place.
remove(0)Returns the removed element. On a long list this shifts everything: consider ArrayDeque for queues.

8 Line by line

Watch the capacity jump from 10 to 15

This trace is recorded from the real JVM. Each heap line shows the list's size and the length of its internal array, the capacity. Watch the 11th add.

Worked examples: real problems, solved and traced in memory

Three ArrayList tasks from real apps. Watch size and capacity on the heap, and the frames of the helper methods.

Example 1Education · list maths

Class average and toppers

Problem statement

Marks are collected into an ArrayList<Integer>. Compute the average and list the positions (1-based) of students who scored the highest mark.

Input

[78, 91, 64, 91]

Expected output

Average 81.0, top 91 by [2, 4]

Approach

A helper average(List<Integer> m) loops by index with get(i).
Collections.max gives the top mark.
Loop again and collect positions with that mark into a new list.

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

Example 2Retail · cleanup

Remove expired items safely

Problem statement

A grocery list stores days-to-expiry for each item. Remove every item with 0 days left, without a ConcurrentModificationException.

Input

[3, 0, 5, 0, 1]

Expected output

[3, 5, 1]

Approach

Loop backwards by index, so removing an element doesn't skip the next one.
Use remove(int), passing the index.
Print the list that's left.

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

Example 3Travel · insert in order

Keep stops sorted by time

Problem statement

A bus route keeps stop times (minutes after start) sorted. Insert a new stop at 25 minutes into [10, 20, 40] at the right position.

Input

stops [10, 20, 40], new stop 25

Expected output

[10, 20, 25, 40]

Approach

A helper insertSorted(list, t) finds the first index whose time is greater than t.
add(index, t) inserts there; later stops shift right.
Print the route.

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

9 Quiz and revision

Check yourself

Quick revision

Lesson 11.3 in one screen

ArrayList = resizable array implementing List: ordered, duplicates and null allowed.
Inside: Object[] elementData + int size. Empty at first; capacity 10 on first add; grows to old × 1.5.
get/set O(1); add at end O(1) amortised; insert/remove in middle O(n); contains/indexOf O(n).
remove(int) by index vs remove(Object) by value: watch out with Integer lists.
Don't remove inside for-each: ConcurrentModificationException. Use removeIf or Iterator.remove.
Pre-size with new ArrayList<>(n); not thread-safe; use ArrayDeque for queue-like work at the front.

Interview and viva questions

How does ArrayList grow internally?

When size equals the array length, grow() computes a new capacity of about 1.5 × the old one (old + (old >> 1)), allocates a new array, copies the references with Arrays.copyOf, and replaces elementData. The default empty list allocates 10 slots on its first add.

ArrayList vs array?

An array has a fixed length, can hold primitives, and has no methods beyond length. An ArrayList grows automatically, holds only objects (primitives are boxed), and offers add/remove/search/sort methods. Arrays are slightly faster and smaller for fixed-size primitive data.

ArrayList vs Vector?

Both are resizable arrays. Vector (legacy, Java 1.0) synchronises every method and doubles its capacity; ArrayList isn't synchronised and grows by 1.5×. For thread-safe lists today use CopyOnWriteArrayList or external synchronisation.

How do you remove elements while iterating?

Use list.removeIf(condition), or an explicit Iterator and its remove() method, or loop backwards by index. Calling list.remove inside a for-each changes modCount and the iterator throws ConcurrentModificationException.

What does trimToSize() do?

It shrinks the internal array to exactly size, releasing unused slots. Useful for a large list that's finished growing and will be kept in memory for a long time.

Practice problems

Everyday ArrayList work: add, read, search, remove safely and reason about cost. The last three are business tasks.

P1Easy

Build and print a list

Add five city names to an ArrayList, print the list, its size, and the third city.

Input

Mumbai, Pune, Nashik, Thane, Panvel

Expected output

[Mumbai, Pune, Nashik, Thane, Panvel] 5 Nashik

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        List<String> cities = new ArrayList<>();
        cities.add("Mumbai");
        cities.add("Pune");
        cities.add("Nashik");
        cities.add("Thane");
        cities.add("Panvel");
        System.out.println(cities + " " + cities.size() + " " + cities.get(2));
    }
}

[Mumbai, Pune, Nashik, Thane, Panvel] 5 Nashik

How it works: indexes start at 0, so the third city is get(2).

P2Easy

Sum with for-each

Sum the prices [120, 45, 60] stored in an ArrayList<Integer>.

Input

[120, 45, 60]

Expected output

Total ₹225

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        List<Integer> prices = new ArrayList<>(List.of(120, 45, 60));
        int total = 0;
        for (int p : prices) total += p;
        System.out.println("Total ₹" + total);
    }
}

Total ₹225

How it works: the for-each loop reads each Integer and unboxes it into p.

P3Easy

Replace with set

In ["chai", "coffee", "lassi"], replace "coffee" with "filter coffee" using indexOf and set.

Input

["chai", "coffee", "lassi"]

Expected output

[chai, filter coffee, lassi]

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        List<String> drinks = new ArrayList<>(List.of("chai", "coffee", "lassi"));
        int i = drinks.indexOf("coffee");
        if (i != -1) drinks.set(i, "filter coffee");
        System.out.println(drinks);
    }
}

[chai, filter coffee, lassi]

How it works: set replaces in place, O(1), without shifting anything.

P4Medium

Remove duplicates, keep order

From [3, 1, 3, 2, 1] build a new list with each value once, in first-seen order, using only ArrayList methods.

Input

[3, 1, 3, 2, 1]

Expected output

[3, 1, 2]

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        List<Integer> in = List.of(3, 1, 3, 2, 1);
        List<Integer> out = new ArrayList<>();
        for (Integer x : in) {
            if (!out.contains(x)) out.add(x);
        }
        System.out.println(out);
    }
}

[3, 1, 2]

How it works: contains is O(n), so this is O(n²): fine for small lists. For large ones, a LinkedHashSet does it in O(n).

P5Medium

Reverse in place

Reverse [1, 2, 3, 4, 5] in place by swapping from both ends with get/set.

Input

[1, 2, 3, 4, 5]

Expected output

[5, 4, 3, 2, 1]

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(List.of(1, 2, 3, 4, 5));
        for (int i = 0, j = a.size() - 1; i < j; i++, j--) {
            Integer t = a.get(i);
            a.set(i, a.get(j));
            a.set(j, t);
        }
        System.out.println(a);
    }
}

[5, 4, 3, 2, 1]

How it works: random access makes each swap O(1), so the whole reversal is O(n). Collections.reverse does the same.

P6Business problem

Top 3 sellers

Daily sales per product are in a list. Sort a copy in descending order and print the top 3 values.

Input

[340, 120, 990, 560, 75]

Expected output

Top 3: [990, 560, 340]

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        List<Integer> sales = List.of(340, 120, 990, 560, 75);
        List<Integer> sorted = new ArrayList<>(sales);
        sorted.sort(Collections.reverseOrder());
        System.out.println("Top 3: " + sorted.subList(0, 3));
    }
}

Top 3: [990, 560, 340]

How it works: we sort a copy (the original is immutable) in reverse order, then take a view of the first three with subList.

P7Business problem

Split orders into batches

A courier sends orders in batches of 3. Split [O1 … O7] into batches and print each.

Input

O1..O7, batch size 3

Expected output

Batch: [O1, O2, O3]
Batch: [O4, O5, O6]
Batch: [O7]

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        List<String> orders = new ArrayList<>();
        for (int i = 1; i <= 7; i++) orders.add("O" + i);
        for (int start = 0; start < orders.size(); start += 3) {
            int end = Math.min(start + 3, orders.size());
            System.out.println("Batch: " + orders.subList(start, end));
        }
    }
}

Batch: [O1, O2, O3] Batch: [O4, O5, O6] Batch: [O7]

How it works: subList(from, to) gives a window of the list; Math.min handles the shorter last batch.

P8Business problem

Pre-sized list for a big import

An import job knows it will load 100,000 rows. Create the list with that capacity, add the rows, and print the size.

Input

100,000 rows

Expected output

Loaded 100000 rows, last id 99999

Show solution and explanation

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

public class Main {
    public static void main(String[] args) {
        int rows = 100_000;
        List<Integer> ids = new ArrayList<>(rows);   // no resizing needed
        for (int i = 0; i < rows; i++) ids.add(i);
        System.out.println("Loaded " + ids.size() + " rows, last id " + ids.get(ids.size() - 1));
    }
}

Loaded 100000 rows, last id 99999

How it works: with the right initial capacity, the list never has to grow and copy. Without it, there would be about 23 grow-and-copy rounds.

Real-world scenario questions (asked in company interviews)

ArrayList questions in interviews test whether you know what happens inside, and when that matters.

E-commerce · bugFresher

Removing out-of-stock items crashes

A nightly job loops over the product list with for-each and removes items whose stock is 0. It throws ConcurrentModificationException. Explain and fix.

The interviewer is checking: fail-fast iterators.

Show a strong answer

For-each uses an iterator. list.remove changes the list's modCount; the iterator's next next() sees the mismatch and throws.
Fix: products.removeIf(p -> p.getStock() == 0); or Iterator<Product> it = …; if (…) it.remove();.
Better still, filter in the database query so out-of-stock items never load.

Avoid: catching and ignoring the exception. Some items will silently stay in the list.

Analytics · performanceJunior

A report that takes 20 minutes

A report checks, for each of 200,000 orders, whether blockedCustomers.contains(order.getCustomerId()), where blockedCustomers is an ArrayList of 50,000 IDs. It's painfully slow. Why, and what's the fix?

The interviewer is checking: O(n) contains and choosing a HashSet.

Show a strong answer

ArrayList.contains is a linear scan: up to 50,000 equals calls per order, about 10 billion in total.
Build Set<Long> blocked = new HashSet<>(blockedCustomers) once; each lookup becomes O(1) on average.
Measure before and after; mention memory cost of the set.

Avoid: sorting and binary searching unless the data is already sorted; the HashSet is simpler.

Logistics · designJunior

A queue built on remove(0)

A dispatch service keeps pending deliveries in an ArrayList, adds at the end and takes the next with remove(0). With 100,000 pending items it slows down badly. Why?

The interviewer is checking: cost of removing at the front.

Show a strong answer

remove(0) shifts all remaining elements left: O(n) per removal.
Use ArrayDeque (offer/poll, both O(1)) or a BlockingQueue if producers and consumers are separate threads.
Keep the variable typed as Queue so the intent is obvious.

Avoid: switching to LinkedList by default; ArrayDeque is usually faster and lighter (Lesson 11.4).

Batch jobs · memoryMid

Spiky memory while loading a big file

A job reads 2 million records into an ArrayList. Profiling shows memory spikes and many large garbage arrays during loading. How do you smooth it out?

The interviewer is checking: growth copies and pre-sizing.

Show a strong answer

Each grow allocates a 1.5× bigger array and copies; during the copy both arrays exist, and the old one becomes garbage.
If the count is known (file header, COUNT(*)), create new ArrayList<>(count) or call ensureCapacity.
Better, process records in a stream or in batches instead of holding all 2 million at once.

Avoid: simply raising the heap size. It hides the pattern instead of fixing it.

The waiting list that wouldn't fit

What is an ArrayList?

Words you'll meet in this lesson

Cost of each operation

Everyday ArrayList operations

Add

Read and search

Change

Remove

The full tour

remove(int) or remove(Object)?

Removing while looping

Inside add when the array is full

An empty list has an empty array

First add: capacity 10

Adds 2 to 10: just fill slots

The 11th add: grow

Why it's still fast on average

Grow and shift: both views

ArrayList in real systems

Watch it with an example: a music app's playlist

1. Query results

2. Carts, playlists and feeds

3. Batch processing with known sizes

4. A common performance bug

A train waiting list

Watch the capacity jump from 10 to 15

Worked examples: real problems, solved and traced in memory

Class average and toppers

Remove expired items safely

Keep stops sorted by time

Check yourself

Quick revision

Lesson 11.3 in one screen

Interview and viva questions

Practice problems

Build and print a list

Sum with for-each

Replace with set

Remove duplicates, keep order

Reverse in place

Top 3 sellers

Split orders into batches

Pre-sized list for a big import

Real-world scenario questions (asked in company interviews)

Removing out-of-stock items crashes

A report that takes 20 minutes

A queue built on remove(0)

Spiky memory while loading a big file

Inside `add` when the array is full