ArrayList and LinkedList

Why this matters

• The textbook answer — "LinkedList for insertions, ArrayList for reads" — is misleading, and knowing why marks the difference between memorised and understood.
• ArrayList growth is the mechanism behind a surprising amount of garbage in list-heavy code, and one constructor argument removes it.
• These two are the most frequently compared classes in Java interviews.

How each one stores elements

Cost, honestly

How ArrayList grows

The internal array has a capacity that is usually larger than the size. When it fills, a new larger array is allocated and the contents copied.

List<Integer> numbers = new ArrayList<>();      // default capacity 10, allocated lazily
for (int i = 0; i < 1_000_000; i++) {
    numbers.add(i);                              // ~30 reallocations and copies along the way
}

// Pre-size it when the count is known or estimable
List<Integer> sized = new ArrayList<>(1_000_000);   // one allocation, no copying

Growth is roughly 1.5× the current capacity. That makes the amortised cost of add constant, because the occasional expensive copy is spread across many cheap appends. But each copy allocates a full array and leaves the old one for the garbage collector.

Removing while iterating

The enhanced for loop cannot remove safely. There are three correct approaches.

List<String> names = new ArrayList<>(List.of("ana", "bob", "carl", "dee"));

// Wrong: ConcurrentModificationException
// for (String name : names) {
//     if (name.startsWith("b")) names.remove(name);
// }

// 1. removeIf — clearest, and the right default
names.removeIf(name -> name.startsWith("b"));

// 2. An explicit iterator, when the condition needs more than a predicate
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
    if (iterator.next().length() > 3) {
        iterator.remove();           // the only safe removal during iteration
    }
}

// 3. A backwards index loop, when you need the index itself
for (int i = names.size() - 1; i >= 0; i--) {
    if (names.get(i).isEmpty()) names.remove(i);
}

remove has two overloads

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

numbers.remove(1);                      // remove(int index)    → removes 20
numbers.remove(Integer.valueOf(10));    // remove(Object value) → removes the value 10

Both compile. The first takes an index, the second a value, and for a List<Integer> the two are indistinguishable at a glance. Always write Integer.valueOf(...) or cast to Object when you mean the value.

CopyOnWriteArrayList

The thread-safe list, suited to a specific shape of workload.

List<Listener> listeners = new CopyOnWriteArrayList<>();

listeners.add(listener);         // copies the whole array — expensive

for (Listener listener : listeners) {
    listener.onEvent(event);      // iterates a snapshot; no lock, no CME
}

Every mutation copies the entire backing array. Reads and iteration are lock-free and never throw ConcurrentModificationException, because the iterator holds the snapshot it started with.

Other list operations worth knowing

List<String> names = new ArrayList<>(List.of("carl", "ana", "bob"));

Collections.sort(names);                        // natural order, in place
names.sort(Comparator.comparing(String::length));   // the modern equivalent
Collections.reverse(names);
Collections.shuffle(names);

List<String> middle = names.subList(1, 3);      // a VIEW, not a copy
int position = Collections.binarySearch(names, "bob");   // sorted list required

String[] array = names.toArray(new String[0]);  // the idiomatic conversion
List<String> fromArray = new ArrayList<>(Arrays.asList(array));

Common misreadings

• "LinkedList is faster for insertion." Only when you are already at the position. Index-based insertion pays O(n) to get there.
• "size() tells you how much memory the list uses." Capacity is usually larger and only grows.
• "remove shrinks the backing array." It does not. Use trimToSize() if that matters.
• "ArrayList is thread-safe if you only read." Safe only if no thread writes at all. Any concurrent write needs CopyOnWriteArrayList or external synchronisation.
• "subList returns a copy." It is a live view with a two-way relationship to the original.
• "toArray() with no argument gives a typed array." It returns Object[]. Pass new String[0] for a typed one.