Lists, sets, maps, and picking the right one

List, Set, and Map are interfaces; the class you pick decides the performance and the ordering guarantees.

List: ArrayList against LinkedList

ArrayList is backed by a resizable array: get(i) is O(1), inserting or removing in the middle is O(n) because everything after it has to shift. LinkedList is a doubly linked list: get(i) is O(n) because it has to walk from an end, but adding or removing at a known position — particularly the front or back, which is what makes it a workable Deque — is O(1).

In practice, default to ArrayList. Sequential access and random reads dominate almost every real use, and ArrayList's array is far more cache-friendly than chasing pointers around a linked list — LinkedList loses the theoretical advantage in practice more often than people expect.

Map: three real choices

Map<String, Integer> a = new HashMap<>();        // no order guarantee
Map<String, Integer> b = new LinkedHashMap<>();  // insertion order
Map<String, Integer> c = new TreeMap<>();        // sorted by key

HashMap is the default: O(1) average get/put, and no ordering guarantee at all — the order it happens to iterate in can change as the map grows. LinkedHashMap costs a little more memory to keep a doubly linked list threading through the entries, in exchange for iterating in insertion order. TreeMap keeps keys sorted, at O(log n) per operation instead of O(1), because it is a red-black tree underneath.

Try it

computeIfAbsent and merge

Building up a Map<K, List<V>> or counting occurrences by hand means a get, a null check, and a put, every time:

Map<String, List<Integer>> byLetter = new HashMap<>();
List<Integer> list = byLetter.get(letter);
if (list == null) {
    list = new ArrayList<>();
    byLetter.put(letter, list);
}
list.add(value);

computeIfAbsent does all three in one call:

byLetter.computeIfAbsent(letter, k -> new ArrayList<>()).add(value);

For counting, merge is the equivalent one-liner:

Map<String, Integer> counts = new HashMap<>();
counts.merge(word, 1, Integer::sum);   // counts.getOrDefault(word, 0) + 1

Both exist because "read, check for absence, write" is common enough to deserve a name, and both are safe to reach for by default — merge in particular reads better than the getOrDefault plus put it replaces.

Common mistakes

• Calling add on a list from List.of(...) or Arrays.asList(...). List.of is unmodifiable, and is a fixed-size view of an array — works, and throw . Copy into when the list has to grow.

What interviewers ask

• When would you choose LinkedList over ArrayList? Rarely: only for heavy insertion and removal at the ends or through an iterator. For a queue or stack, ArrayDeque usually beats both.
• HashMap, LinkedHashMap or TreeMap? No order and O(1) average; insertion (or access) order for a little more memory; sorted keys at O(log n) per operation.
• How would you count word frequencies? One merge(word, 1, Integer::sum) per word, into a map type chosen for the order the result needs.