What are the costs of ArrayList, LinkedList, HashMap and TreeMap, and how do you choose?

From the Javadoc.

• ArrayList: get, set, size and iteration run in constant time; add runs in amortized constant time; other operations are roughly linear. The constant factor is low compared with LinkedList.
• LinkedList: a doubly linked list; operations that index into it traverse from the nearer end, so get(i) is linear. Insert and remove are constant time only once you have an iterator at the spot.
• HashMap: constant-time get and put assuming the hash function spreads keys well; iteration is proportional to capacity plus size; no ordering guarantee.
• TreeMap: a red-black tree with guaranteed log n containsKey, get, put and remove, keys sorted by natural order or a comparator, and range views such as subMap and headMap.

Choosing. Ask which contract you need: index access, insertion order, sorted order, uniqueness, or fast membership. A list you append to and read by index is an ArrayList. A queue or stack is an ArrayDeque, which beats LinkedList in practice. Fast lookup without order is a HashMap; insertion order adds LinkedHashMap; sorted keys or ranges need a TreeMap.

Why LinkedList rarely wins. Each node is a separate object with two pointers, so memory use is higher and traversal jumps around memory. Even the "insert in the middle" case needs a linear walk to reach the middle unless you already hold a ListIterator.

Alternate interview scenarios

"ArrayList or LinkedList for a list you mostly append to and then read by index?" ArrayList. Append is amortized constant and index reads are constant, while LinkedList makes every get(i) a walk. LinkedList only helps if you insert or remove at a position you already hold through an iterator, and even then the memory and cache cost often cancel the gain.

"Fail-fast versus fail-safe iterators, HashSet, and HashMap resizing." These come up together.

• Fail-fast: ArrayList, HashMap and the other classic collections throw ConcurrentModificationException if the collection is structurally modified during iteration, except through the iterator's own remove. The Javadoc says this is "on a best-effort basis" and should be used "only to detect bugs".
• "Fail-safe": not a Javadoc term. The concurrent collections use two different designs: CopyOnWriteArrayList iterates a snapshot, so it never sees later writes; ConcurrentHashMap iterators are weakly consistent, so they may or may not see concurrent changes. Neither throws.
• HashSet is "backed by a hash table (actually a HashMap instance)": each element is a key with a dummy value, so it has the same hashing, equals/hashCode contract and costs as HashMap.
• Capacity and resizing: HashMap starts with 16 buckets by default and rehashes to about twice the buckets when the entries exceed capacity times the load factor, 0.75 by default, which the Javadoc calls "a good tradeoff between time and space costs". If you know the size, presize it; in Java 19 and later HashMap.newHashMap(n) computes the capacity for n entries.

import java.util.*;
import java.util.concurrent.*;

public class FailFast {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(List.of("a", "b", "c"));
        try {
            for (String s : list) if (s.equals("a")) list.remove(s);   // structural change mid-iteration
        } catch (ConcurrentModificationException e) {
            System.out.println("ArrayList: " + e.getClass().getSimpleName());
        }
        list.removeIf(s -> s.equals("b"));                             // the safe way
        System.out.println("removeIf: " + list);

        List<String> cow = new CopyOnWriteArrayList<>(List.of("a", "b", "c"));
        for (String s : cow) if (s.equals("a")) cow.add("d");          // iterates a snapshot
        System.out.println("CopyOnWriteArrayList: " + cow);

        Map<String, Integer> chm = new ConcurrentHashMap<>(Map.of("a", 1, "b", 2));
        for (String k : chm.keySet()) chm.remove(k);                   // weakly consistent, no exception
        System.out.println("ConcurrentHashMap: " + chm);
    }
}

Verified with OpenJDK 21.0.13. It prints ArrayList: ConcurrentModificationException, removeIf: [c] (the earlier loop had already removed a), CopyOnWriteArrayList: [a, b, c, d] and ConcurrentHashMap: {}.