Collections

ArrayList is backed by a resizable array, so random access by index is O(1), but inserting or removing in the middle shifts later elements and costs O(n). LinkedList is a doubly-linked list of nodes, so adding or removing at the ends is O(1), but reaching an index means walking the chain, giving O(n) access. Pick ArrayList for index-heavy reads, LinkedList for frequent end edits.

The Collections framework is a unified architecture for storing and manipulating groups of objects. It pairs core interfaces — Collection, List, Set, Map, Queue — with ready implementations like ArrayList and HashMap, plus reusable algorithms in the Collections utility class. This gives one consistent API, letting you swap implementations without rewriting calling code.

A List is an ordered, positional sequence: it keeps insertion order, lets you access elements by index, and permits duplicate values. A Set models a mathematical set: it rejects duplicate elements, so each value appears at most once, and it is typically unordered (HashSet) — though TreeSet keeps elements sorted and LinkedHashSet preserves insertion order. Choose a List for sequences, a Set for uniqueness.

Collection (singular) is the root interface of the hierarchy that List, Set, and Queue extend — it declares operations like add, remove, and size. Collections (plural) is a utility class holding only static helper methods such as sort, reverse, shuffle, synchronizedList, and unmodifiableList. So one is the interface you implement, the other is a toolbox you call.

Comparable defines a type's single natural ordering: the class implements compareTo(other) on itself, so Collections.sort knows the default order. Comparator is a separate object defining one of many external orderings via compare(a, b), letting you sort the same type by different keys without touching its source. Use Comparable for the one obvious order, Comparator for alternative or third-party orderings.

HashMap is unsynchronized, allows one null key and any number of null values, and is faster — the standard choice for single-threaded code. Hashtable is a legacy class whose methods are synchronized, so it locks the whole table per call, and it forbids null keys and values, throwing NullPointerException. For concurrent maps today, prefer ConcurrentHashMap, which locks finer-grained segments.

HashMap holds an array of buckets indexed by the key's hash. Colliding keys share a bucket as a linked list. capacity is the bucket-array size and loadFactor (default 0.75) is the fill threshold: when size > capacity * loadFactor the map doubles capacity and rehashes. Since Java 8, a bucket with more than 8 entries (in a large-enough table) converts its list into a red-black tree, cutting worst-case lookup from O(n) to O(log n).

HashSet stores elements via hashing, giving O(1) average add, remove, and contains, but no ordering — iteration order is unspecified. TreeSet is backed by a red-black tree that keeps elements sorted by their natural Comparable order or a supplied Comparator, costing O(log n) per operation but enabling range queries like first, ceiling, and headSet. Choose HashSet for raw speed, TreeSet when you need sorted order.

Both ArrayList and Vector are resizable arrays with the same O(1) indexed access, but Vector is a legacy class whose methods are synchronized, so every call locks even in single-threaded code, costing performance. ArrayList is unsynchronized and the default choice today. Vector also doubles capacity on growth, while ArrayList grows by about half. For thread-safety, prefer synchronizedList or CopyOnWriteArrayList.

ArrayList gives indexed get in O(1) and amortized O(1) append, but contains scans in O(n). LinkedList is O(1) only at the ends; indexed get and contains are O(n). HashMap and HashSet average O(1) for all three, degrading to O(log n) inside a treeified bucket and to O(n) with a degenerate hashCode. TreeMap and TreeSet are O(log n) for every operation, in exchange for sorted order.

A fail-fast iterator throws ConcurrentModificationException once it detects the collection was structurally modified mid-iteration — it tracks a modification counter and rechecks it each step. ArrayList and HashMap behave this way. A fail-safe iterator instead works over a copy or snapshot, so concurrent edits don't disrupt it and it never throws — CopyOnWriteArrayList and ConcurrentHashMap do this, at the cost of missing later changes.

A shallow copy duplicates the outer container but shares the same nested element references, so copy and original point at the same inner objects — mutating one's element mutates the other's. A deep copy recursively clones the whole object graph, giving the copy its own independent inner objects, so changes never leak across. clone and copy constructors are shallow by default; a deep copy needs explicit recursive duplication.

Keep two stacks. The main stack holds the values; a second max stack holds, at each level, the maximum of everything pushed so far. On push, also push max(value, maxStack.peek()) onto the max stack. On pop, pop both. getMax returns maxStack.peek(). Because the maximum is recomputed and stored per element, it stays correct after a pop, and all three operations are O(1).

Keep a TreeMap<value,count> plus a FIFO queue holding the window's values in insertion order. On add, if the window is full, poll the oldest from the queue and decrement (or remove) its count in the map; then increment the new value's count and enqueue it. getMin returns map.firstKey(). Each operation is O(log w); a monotonic deque gives amortized O(1).