Collections in Depth

HashMap is a hash table: O(1) average get/put and no ordering guarantee whatsoever. LinkedHashMap extends it with a doubly-linked list threaded through the entries, preserving insertion order — or access order, which turns it into an LRU cache via removeEldestEntry — still O(1), at a small memory cost. TreeMap is a red-black tree: keys sorted by Comparable/Comparator, O(log n) operations, and no null key.

ArrayDeque implements Deque over a resizable circular array, so additions and removals at both ends are amortized O(1) with contiguous, cache-friendly storage. LinkedList also implements Deque, but every element needs a separate node holding two links, which costs memory, locality and GC pressure. ArrayDeque is the recommended stack (over the legacy Stack) and queue; it just forbids null elements.

List.of() builds a genuinely immutable list: it copies the arguments into its own storage, rejects null elements, and hands out no reference to any backing collection, so nothing can ever change it. Collections.unmodifiableList(list) returns only a read-only view — its own mutators throw UnsupportedOperationException, but a write through the original list reference is still visible through that view.

Only the head is ordered. PriorityQueue is a binary heap, so peek/poll always return the least element by natural order or by the supplied Comparator, but iterator() and toString() walk the backing array in heap order, which is not sorted. offer/poll cost O(log n), peek is O(1), and elements of equal priority have no defined relative order — the queue is not stable, so it is not FIFO within a priority.

Iterator traverses any Collection forward only, with hasNext, next, and remove. ListIterator, obtainable only from a List, also moves backward via hasPrevious/previous, reports positions with nextIndex/previousIndex, replaces the last returned element with set, and inserts at the cursor with add. Both are fail-fast on structural change made outside the iterator.

The for-each loop runs on the list's own fail-fast Iterator. names.remove(name) bumps the list's modCount behind the iterator's back, so the next next() finds modCount != expectedModCount and throws ConcurrentModificationException — no second thread is involved. Fix it by mutating through the iterator (it.remove() after it.next()), or simply call names.removeIf(n -> n.length() == 3); iterating over a copy also works.

A plain Set promises only uniqueness — HashSet gives no order at all. SortedSet, implemented by TreeSet, keeps elements in Comparable/Comparator order and adds first, last and the range views headSet/tailSet/subSet. NavigableSet extends it with closest-match lookups — floor, ceiling, lower, higher — plus pollFirst/pollLast and descendingSet/descendingIterator, all O(log n).

Java 21 gives every collection with a defined encounter order a common supertype. SequencedCollection declares getFirst/getLast, addFirst/addLast, removeFirst/removeLast and reversed(); List, Deque and LinkedHashSet implement it, so list.getFirst() replaces list.get(0). SequencedSet narrows reversed() to a set, and SequencedMap adds firstEntry/lastEntry and putFirst/putLast. reversed() is a live view, not a copy.