List: ArrayList vs LinkedList

Ordered, indexed, duplicates allowed — and when each concrete class makes sense.

The List contract

A List<E> is an ordered sequence where elements are accessed by zero-based index. Duplicate elements are allowed. The core operations:

Method	Meaning
`add(e)`	Append at end
`add(i, e)`	Insert at index
`get(i)`	Element at index
`set(i, e)`	Replace at index
`remove(i)`	Remove by index
`remove(e)`	Remove first occurrence by value
`size()`	Number of elements
`contains(e)`	Linear search

List<String> fruits = new ArrayList<>(List.of("apple", "banana"));
fruits.add("cherry");          // [apple, banana, cherry]
fruits.add(1, "apricot");      // [apple, apricot, banana, cherry]
String s = fruits.get(2);      // "banana"
fruits.remove("apple");        // [apricot, banana, cherry]
System.out.println(fruits.size()); // 3

ArrayList backs elements in a resizable array. Random access (get(i)) is O(1). Insertion/deletion in the middle shifts elements — O(n).

LinkedList backs elements in a doubly linked node chain. Head/tail insertion/deletion is O(1). Random access traverses the chain — O(n).

In practice ArrayList is the right default for almost every list. Use LinkedList only when you are inserting/deleting heavily at both ends and rarely doing indexed access.

List.of(...) (Java 9+) creates an immutable list. No add, set, or remove — any mutation throws UnsupportedOperationException.

Insertion at index 1 shifts every later element one slot right, and removing apple shifts them all back left. That shifting is the O(n) an ArrayList pays for any change away from the end.