ArrayList is a resizable array and is the right default ~99% of the time; LinkedList is a doubly-linked list that only wins when you add/remove at an iterator's position.

How `ArrayList` grows

Backed by an Object[] elementData; size counts the slots actually used.
new ArrayList<>() starts with an empty shared array; the first add allocates capacity 10.
When full, it grows to old + old/2 (1.5×) and copies with Arrays.copyOf — O(n) once, so add is amortised O(1).
Pre-size with new ArrayList<>(expected) or ensureCapacity(n) to avoid repeated copying; trimToSize() releases the slack.

capacity: 10 → 15 → 22 → 33 → 49 → 73 → …

Complexity

Operation	`ArrayList`	`LinkedList`
`get(i)` / `set(i, x)`	O(1)	O(n) — walks from the nearer end
`add(x)` at the end	O(1) amortised	O(1)
`add(0, x)` / `remove(0)`	O(n) — shifts elements	O(1)
Insert/remove in the middle	O(n) shift	O(n) to find + O(1) to link
`contains` / `indexOf`	O(n)	O(n)
Memory per element	one reference (4–8 bytes)	node object: item + prev + next + header (~24–40 bytes)
CPU cache	Contiguous — very fast to scan	Pointer chasing — slow

Everyday operations

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(List.of("b", "c"));
        list.add(0, "a");               // insert at index
        list.add("d");
        list.set(3, "D");               // replace
        System.out.println(list + " get(1)=" + list.get(1));
        System.out.println(list.indexOf("c") + " " + list.contains("z"));
        list.remove("a");               // by value
        System.out.println(list);

        LinkedList<Integer> linked = new LinkedList<>(List.of(2, 3));
        linked.addFirst(1);
        linked.addLast(4);
        System.out.println(linked + " first=" + linked.getFirst() + " last=" + linked.peekLast());
    }
}

Output

[a, b, c, D] get(1)=b
2 false
[b, c, D]
[1, 2, 3, 4] first=1 last=4

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

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(10, 20, 30, 1));
        nums.remove(1);                     // remove(int index) — removes 20!
        System.out.println(nums);
        nums.remove(Integer.valueOf(1));    // remove(Object) — removes the value 1
        System.out.println(nums);
    }
}

Output

[10, 30, 1]
[10, 30]

`subList` is a view

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5));
        List<Integer> mid = list.subList(1, 4);   // [1, 4) — a live window
        mid.set(0, 99);
        System.out.println(list);
        list.subList(0, 2).clear();               // idiom: delete a range
        System.out.println(list);
        try {
            System.out.println(mid);              // parent was structurally modified
        } catch (ConcurrentModificationException e) {
            System.out.println("stale subList -> ConcurrentModificationException");
        }
    }
}

Output

[0, 99, 2, 3, 4, 5]
[2, 3, 4, 5]
stale subList -> ConcurrentModificationException

ArrayList vs LinkedList — when would you pick LinkedList?

What is the default capacity of ArrayList and how does it grow?

ArrayList vs Vector?

How ArrayList grows

Complexity

Everyday operations

Trap: remove(int) vs remove(Object)

subList is a view

How `ArrayList` grows

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

`subList` is a view