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, no ordering at all — iterating it twice is not even guaranteed to produce the same order. 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.