Java Collections Framework
The Collections Framework is Java's standard data-structure library — a unified set of interfaces (List, Set, Map, Queue), their ready-made implementations (ArrayList, HashMap, TreeSet, and others), and reusable algorithms in the Collections utility class. One consistent API lets you swap implementations without rewriting calling code — you declare a variable as List<T> while holding an ArrayList or a LinkedList underneath, so the choice becomes a performance decision rather than a syntax one.
A collections interview almost always tests your model of how these types work internally, not recall of class names — which operation costs O(1) and which costs O(n), where there is an array and where there are nodes and pointers, who is synchronized, who allows null. A candidate who justifies ArrayList with "O(1) index access but O(n) mid-list insert" immediately stands out from "well, it's a list". The full map is in the layers below.
Topic map
- The Collections Framework — the two roots
CollectionandMap, and the "interface — implementation — algorithm" split. - ArrayList vs LinkedList — a resizable array vs a doubly-linked list and their per-operation Big-O.
- ArrayList vs Vector — why
Vectorsynchronizes on every method and is therefore legacy. - Set vs List — uniqueness and ordering rules vs a positional sequence with duplicates.
- HashSet vs TreeSet — an O(1) hash table with no order vs an O(log n) red-black tree that stays sorted.
- HashMap vs Hashtable —
null, synchronization, and whyHashtableis legacy. - HashMap Internals — buckets,
loadFactor, resize, and a bucket turning into a tree at 8 entries. - Comparable vs Comparator — one natural order vs many external orderings.
- Collection vs Collections — the root interface vs the final utility class.
- Choosing a Data Structure — from a task's requirements to a concrete collection implementation.
Common traps
| Mistake | Consequence |
|---|---|
Assuming LinkedList.get(i) is O(1) | An indexed loop walks the chain every time — O(n²) instead of O(n) |
Reaching for Vector or Hashtable for thread-safety in new code | It locks the whole structure per call, and compound operations still are not atomic |
Storing a null key in a Hashtable | NullPointerException — unlike HashMap, which allows one null key |
Expecting get(index) on a Set | A Set has no positional access; a repeat add silently returns false |
Putting a type with no Comparable and no Comparator into TreeSet/TreeMap | ClassCastException at runtime on the first comparison |
Returning boolean from compareTo/compare | Wrong contract — it needs an int sign (negative, zero, positive) |
Treating Map as a subtype of Collection | It is a separate root of the hierarchy — a design confusion |
Mutating a collection during a for-each loop | ConcurrentModificationException from the fail-fast iterator |
Relying on a poor hashCode | Every key lands in one bucket — average O(1) degrades to O(n) |
Interview relevance
Collections come up on almost every Java interview, but the check is your model, not trivia — the asymptotics of operations, the internal layout, and the null/synchronization/ordering rules. A strong answer always ties the choice to the cost of the operations.
Typical checks:
- The Big-O of access, insert, and remove for
ArrayList,LinkedList,HashMap,TreeMap. HashMapinternals — buckets, collisions,loadFactor, resize, treeify since Java 8.- The
HashMap/HashtableandArrayList/Vectordifferences in synchronization andnull. ComparablevsComparatorand thecompareTocontract.- When to pick a
Set, aList, aMap, or a queue.
Common wrong answer: "LinkedList is faster than ArrayList because it never copies the array." That opens the discussion that random access on a LinkedList is O(n), that the array's cache locality usually wins, and that on real workloads ArrayList is more often the faster choice.