Collections Framework

The Java Collections Framework provides a unified architecture for storing and manipulating groups of objects. Choosing the right data structure has a direct impact on time complexity and memory usage. Every Java developer must know the internal workings and trade-offs of the core implementations.

Key Points

• ArrayList: backed by an array, O(1) random access, O(n) insert/delete in middle, amortised O(1) add-to-end
• LinkedList: doubly-linked list, O(1) insert/delete at known position, O(n) random access — rarely outperforms ArrayList in practice due to cache misses
• HashSet / HashMap: backed by a hash table, O(1) average get/put/contains — degrades to O(n) on hash collisions
• LinkedHashSet / LinkedHashMap: maintain insertion order via a doubly-linked list — O(1) operations with ordering
• TreeSet / TreeMap: backed by a Red-Black Tree, O(log n) operations, elements kept sorted — implements SortedSet/SortedMap
• ArrayDeque: double-ended queue, O(1) push/pop/peek both ends — prefer over Stack and LinkedList as a queue
• PriorityQueue: min-heap, O(log n) add/poll, O(1) peek — does not guarantee ordering on iteration
• ConcurrentHashMap (Java 8+): lock-striping per bucket, thread-safe without locking entire map — use over Hashtable
• Fail-fast iterators throw ConcurrentModificationException if collection modified during iteration; fail-safe (CopyOnWriteArrayList, concurrent collections) iterate over a snapshot

Common Collections patterns: merge for frequency maps, TreeMap range queries, ArrayDeque dual role, CopyOnWriteArrayList

// HashMap — custom key requires equals + hashCode
Map<String, Integer> freq = new HashMap<>();
for (String word : words) {
    freq.merge(word, 1, Integer::sum);  // Java 8 merge
}

// TreeMap — sorted by key, get floor/ceiling/range
TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(1, "a"); tm.put(3, "c"); tm.put(5, "e");
tm.subMap(1, true, 4, false).forEach((k, v) -> ...); // keys 1..3

// ArrayDeque as stack and queue
Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);       // stack: addFirst
deque.offer(2);      // queue: addLast
deque.pop();         // stack: removeFirst
deque.poll();        // queue: removeFirst

// CopyOnWriteArrayList — safe iteration without locks
List<String> safe = new CopyOnWriteArrayList<>(list);
for (String s : safe) {   // iterates snapshot — no CME
    safe.add("new");       // writes create a new array copy
}

// Java 9+ immutable collections
List<Integer> immutable = List.of(1, 2, 3);   // UnsupportedOperationException on mutation
Map<String, Integer> map = Map.of("a", 1, "b", 2);