Collections Framework

Iterable<T>                    iterator(), for-each
 └── Collection<E>               size(), add(), remove(), contains()
      ├── List<E>                 ordered, duplicates OK, index access
      │    ├── ArrayList
      │    ├── LinkedList (also Deque)
      │    └── CopyOnWriteArrayList (concurrent)
      ├── Set<E>                  no duplicate equals() elements
      │    ├── HashSet / LinkedHashSet
      │    ├── TreeSet (NavigableSet)
      │    └── EnumSet
      └── Queue<E> / Deque<E>      FIFO, LIFO, offer/poll
           ├── ArrayDeque
           ├── PriorityQueue
           └── BlockingQueue* (java.util.concurrent)

Map<K,V>  (NOT a Collection)      key → value, unique keys
 ├── HashMap / LinkedHashMap
 ├── TreeMap (NavigableMap)
 ├── ConcurrentHashMap
 ├── WeakHashMap, IdentityHashMap, EnumMap

* BlockingDeque, DelayQueue, etc. extend concurrent package

List<String> names = new ArrayList<>();
Set<UUID> seen = new HashSet<>();
Map<String, Integer> counts = new HashMap<>();
Deque<Task> work = new ArrayDeque<>();

// Accept widest type in APIs
void process(Collection<? extends Order> batch) { ... }

Real-world analogy: A List is a numbered deli line; a Set is a guest list (one entry per person); a Map is a phone book keyed by name.

ArrayList — dynamic array

Backed by a growable Object[] (or typed array for some factories). Logical size size may be less than elementData.length (capacity).

• Append at end — amortized O(1): write at size, increment; occasionally resize
• get(i) / set(i) — O(1) index arithmetic + array access
• add/remove at middle — O(n) — System.arraycopy shifts elements
• Resize — new array ~1.5× capacity (JDK growth policy), copy all references

List<String> list = new ArrayList<>(10_000);  // presize — one resize avoided
list.add("a");           // amortized O(1) at end
list.get(0);             // O(1)
list.add(0, "front");    // O(n) — shift right

LinkedList — doubly linked nodes

Each element is a Node with prev, next, item. Implements List and Deque.

• Add/remove at ends — O(1) with pointer updates
• get(i) — O(n) — walk from nearer end
• Cache locality — nodes scattered on heap; each hop misses CPU cache lines
• Memory — extra overhead per element (two pointers + node object)

When to use which — benchmark reality

Micro-benchmarks (JMH) on modern JVMs: ArrayList wins for typical CRUD, bulk load, and iteration. LinkedList only competes when you already hold a ListIterator at a position and do many inserts there—or you need Deque and mistakenly pick LinkedList (prefer ArrayDeque).

CopyOnWriteArrayList — concurrent reads

Thread-safe: every mutating operation (add, set, remove) copies the entire backing array. Iterators snapshot the array at creation time—no CME, weakly consistent with concurrent writes.

• Good: listener lists, read-mostly config, event subscribers
• Bad: frequent writes, large lists (copy cost O(n) per write)

List<Runnable> listeners = new CopyOnWriteArrayList<>();
listeners.add(this::onChange);  // copies array — OK if rare

for (Runnable r : listeners) {
    r.run();  // safe even if another thread adds during loop
}

HashSet

Backed by a HashMap—each element is a key mapped to a constant PRESENT sentinel object. Average O(1) add, contains, remove with good hash distribution.

No iteration order guarantee—order changes when capacity resizes.

LinkedHashSet

Hash table + doubly linked list through entries → insertion-order iteration (or access-order if constructed from access-order LinkedHashMap pattern). Slightly more memory, still O(1) average ops.

TreeSet — NavigableSet

Red-black tree (balanced BST) backing TreeMap. O(log n) add/contains/remove. Iteration in sorted order—natural ordering (Comparable) or Comparator.

Extra API: ceiling, floor, subSet, headSet, tailSet—useful for range queries on ordered keys.

EnumSet — bit vector

Keys are enum constants from one enum type. Internal representation is a bit vector (or long[]) over ordinals—O(1) add/contains/remove, extremely compact and fast. Iteration order matches enum declaration order.

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("java");  // false — duplicate ignored

Set<DayOfWeek> weekend = EnumSet.range(DayOfWeek.SATURDAY, DayOfWeek.SUNDAY);

NavigableSet<Integer> scores = new TreeSet<>();
scores.add(90);
scores.floor(85);  // null — none ≤ 85

Interview focus: HashMap internals, resize/load factor, treeification, and ConcurrentHashMap vs synchronized wrappers. Production focus: key equality, ordering, and eviction (LRU).

Put flow (simplified)

1. Compute hash = key.hashCode() ^ (hash >>> 16) — spreads high bits into index
2. Bucket index: (n - 1) & hash where n is table length (power of 2)
3. If bucket empty → new node; else walk chain comparing hash and equals
4. If key found → replace value; else append node
5. If size > capacity * loadFactor (default 0.75) → resize (double n, rehash all entries)

table[]  (length n = power of 2)
  [0] → Node(k1,v1) → Node(k2,v2)     chain length 2
  [1] null
  [2] → TreeNode (red-black)          treeified: chain was ≥ 8
  [3] → Node(k3,v3)
  ...
threshold = (int)(n * loadFactor)   // resize when size > threshold

Linked list → tree Java 8+

When a bucket chain length reaches 8 (and table length ≥ 64), chain converts to TreeNode (red-black tree) — worst-case per bucket becomes O(log n) instead of O(n) under hash collisions (e.g. malicious or poor keys).

When tree size drops to 6, untreeify back to linked list.

Load factor & resize

Map<String, User> byEmail = new HashMap<>(16_384);  // ~12k entries @ 0.75
byEmail.put("[email protected]", user);
User u = byEmail.get("[email protected]");

byEmail.putIfAbsent("[email protected]", new User());
byEmail.computeIfPresent("[email protected]", (k, v) -> v.withLastLogin(Instant.now()));
byEmail.merge("[email protected]", 1, Integer::sum);  // if values are counts

LinkedHashMap — LRU cache pattern

Maintains doubly linked list through entries. Constructor flag accessOrder = true moves entry to tail on get—foundation for LRU caches.

Map<String, byte[]> cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, byte[]> eldest) {
        return size() > 10_000;
    }
};

Production caches prefer Caffeine/Guava with TTL, weight, and stats—but the pattern is the same: bounded map + eviction hook.

TreeMap — NavigableMap

Sorted by key (Comparable or Comparator). O(log n) operations. NavigableMap: lowerKey, floorEntry, subMap, descendingMap.

ConcurrentHashMap

Reads generally lock-free. Aggregate size is approximate under contention. No null keys or values.

ConcurrentMap<String, Long> counters = new ConcurrentHashMap<>();
counters.merge("requests", 1L, Long::sum);

// Atomic replace if present
counters.compute("key", (k, v) -> v == null ? 1L : v + 1);

Niche maps

Map<DayOfWeek, Integer> traffic = new EnumMap<>(DayOfWeek.class);
traffic.put(DayOfWeek.MONDAY, 1200);

Map<Object, String> metadata = new WeakHashMap<>();

ArrayDeque vs LinkedList as Queue

Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.pop();

Queue<String> fifo = new ArrayDeque<>();
fifo.offer("first");
fifo.poll();

PriorityQueue — binary heap

Min-heap by default (Comparator natural order). offer / poll are O(log n); peek is O(1). Not thread-safe. Iterator does not return sorted order—only poll drains in priority order.

// Max-heap by reversing comparison
Queue<Task> urgent = new PriorityQueue<>(
    Comparator.comparing(Task::deadline).reversed());

Task next = urgent.poll();

BlockingQueue — thread pools

BlockingQueue<Runnable> work = new LinkedBlockingQueue<>(1000);
ExecutorService pool = new ThreadPoolExecutor(
    4, 8, 60, TimeUnit.SECONDS,
    work,
    new ThreadPoolExecutor.CallerRunsPolicy());

Collections static methods

Arrays utility

Arrays.sort, binarySearch, copyOf, fill, equals, compare (Java 9+), stream, parallelPrefix—primitives and objects (objects require Comparable or Comparator for sort).

Immutable factories Java 9+

List<String> colors = List.of("red", "green", "blue");
Set<Integer> ids = Set.of(1, 2, 3);
Map<String, Integer> map = Map.of("x", 1, "y", 2);
Map<String, Integer> big = Map.ofEntries(
    Map.entry("a", 1),
    Map.entry("b", 2));

// Null elements forbidden — NPE
// List.of(1, 2, 1);  // OK for List (duplicates allowed)
// Set.of(1, 1);      // IllegalArgumentException duplicate

List<String> mutable = new ArrayList<>(List.of("a"));
Collections.sort(mutable);
List<String> frozen = Collections.unmodifiableList(mutable);

Design decision

public record Employee(String name, int salary, LocalDate hired)
    implements Comparable<Employee> {
    @Override
    public int compareTo(Employee o) {
        return Integer.compare(this.salary, o.salary);
    }
}

Comparator<Employee> byTenure = Comparator
    .comparing(Employee::hired)
    .thenComparing(Employee::name);

Comparator<Employee> bySalaryDesc = Comparator
    .comparingInt(Employee::salary)
    .reversed()
    .thenComparing(Employee::name, Comparator.nullsLast(String::compareTo));

employees.sort(bySalaryDesc);
Collections.sort(legacyList, byTenure);

List.sort uses TimSort — O(n log n) worst case, stable (preserves equal elements’ order). Stability matters when sorting by one key then another with thenComparing.

// Safe removal during iteration
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    String s = it.next();
    if (s.isBlank()) it.remove();
}

// ListIterator — edit while scanning
ListIterator<String> li = list.listIterator();
while (li.hasNext()) {
    if (li.next().equals("obsolete")) {
        li.set("replacement");
    }
}

// Idiomatic Java 8+
list.removeIf(String::isBlank);

// UNSAFE — fail-fast CME
for (String s : list) {
    if (s.isBlank()) list.remove(s);
}

ConcurrentModificationException — why & how to avoid

Most non-concurrent collections track modCount (structural change counter). Iterator remembers expected modCount at creation; mismatch → fail-fast CME (best-effort, not guaranteed in all threads).

• Avoid: mutate collection directly during enhanced-for; use iterator remove, removeIf, or copy-then-replace
• Concurrent collections: weakly consistent iterators—no CME, may or may not see concurrent adds
• Streams: not fail-fast on all sources; still avoid concurrent modification of backing collection during pipeline unless concurrent collection

// ConcurrentHashMap — Iterator on entrySet is weakly consistent
ConcurrentHashMap<String, Long> map = new ConcurrentHashMap<>();
map.put("a", 1L);
for (var entry : map.entrySet()) {
    map.merge("b", 1L, Long::sum);  // no CME
}