Interviewers do not ask collections only to check whether you remember class names. They want to see whether you can translate a requirement, such as fast lookup, stable insertion order or sorted keys, into the right data structure and explain its cost.
The useful answer starts with contracts. Choose the interface behaviour first, then the implementation that delivers it.
The collection hierarchy that matters
Collection and Map are separate top-level branches. A Collection stores individual elements. A Map stores key-value associations and does not extend Collection.
For most fresher interviews, prune the framework to six implementations:
Listpreserves positional order and permits duplicates. Its common implementations areArrayListandLinkedList.Setstores unique elements.HashSetgives hash-based membership, whileLinkedHashSetalso preserves insertion order.Mapassociates unique keys with values.HashMapis hash-based, whileTreeMapmaintains keys in sorted order.
That tree is enough to answer the first question: do you need positions, uniqueness or key-value lookup? Ordering and performance then decide the concrete class.
ArrayList versus LinkedList
ArrayList stores references in a resizable array. Index access is O(1) because the position can be computed directly. Appending is amortized O(1): most appends fill the next slot, while an occasional resize allocates a larger internal array and copies references.
Insertion or deletion in the middle is O(n) because later references must shift. Searching by value is also O(n) unless you maintain a separate index.
LinkedList stores nodes connected in both directions. Adding or removing at an end is O(1), and removing a node is O(1) once you already have an iterator positioned at it. Reaching index i is O(n), however, because the list must traverse nodes. Saying “linked-list insertion is always O(1)” is incomplete when finding the position takes O(n).
In typical application code, ArrayList is the better default. Its internal array of references has better locality than scattered linked nodes, and it uses less per-element structural memory. The element objects themselves still sit wherever the heap put them; what is compact and cache-friendly is the reference array the list walks.
Choose LinkedList only when its deque operations or iterator-based insertion pattern genuinely fits. For a queue, also consider purpose-built deque implementations rather than assuming a linked list is fastest.
How HashMap works in interviews
HashMap uses a key's hashCode() to choose a bucket, then uses equals() to distinguish keys within that bucket. A collision means different keys reach the same bucket; it does not mean one value automatically overwrites another.
The key contract is precise:
If two objects are equal according to
equals(), they must produce the same hash code.Unequal objects may share a hash code, so collisions must be handled.
Fields used by
equals()andhashCode()should not change while the object is serving as a map key.
That last rule is why immutable types make the safest keys. A String cannot change after construction, so it can never drift away from the bucket its entry was filed under. Java string handling works through the string pool and immutability behind that guarantee.
Average lookup and update are O(1) with a well-distributed hash function. A hash that concentrates keys into a few buckets drags those operations back towards O(n). Since Java 8, a sufficiently crowded bin may be restructured as a balanced tree once internal thresholds are met, improving operations inside that bin to logarithmic behaviour. Bucket layout, resizing and treeification are implementation details that differ between versions, not part of the Map interface contract. HashMap internal working takes those layers one at a time.
HashMap does not promise iteration order. If code depends on insertion order, use LinkedHashMap, which layers insertion-order iteration on top of the same hashing. If it depends on sorted keys, use TreeMap.
TreeMap and ordering
TreeMap maintains keys in sorted order using a balanced search tree. get, put and remove are O(log n), trading some raw lookup speed for ordered traversal and range operations such as keys below a boundary.
Natural ordering comes from Comparable, whose compareTo method belongs to the class being compared. External or alternate ordering comes from a Comparator supplied to the map. For example, a Student class might have a natural order by roll number but a report may use a comparator by name.
The comparison must be consistent enough for map semantics. If comparison returns zero for two keys, TreeMap treats them as the same key position even if a separate equals() check would say otherwise. That is a common interview follow-up.
Complexity contracts at a glance
These are the standard expected costs for ordinary use, with n elements:
Implementation | Access or lookup | Add or update | Remove | Ordering contract |
|---|---|---|---|---|
| index O(1), contains O(n) | end amortized O(1), middle O(n) | middle O(n) | positional |
| index or contains O(n) | ends O(1), found position O(1) | ends or known node O(1) | positional |
| average contains O(1) | average O(1) | average O(1) | none |
| average contains O(1) | average O(1) | average O(1) | insertion order |
| average key lookup O(1) | average O(1) | average O(1) | none |
| O(log n) | O(log n) | O(log n) | sorted keys |
These are asymptotic costs, not measured timings. Hash quality, resizing, allocation and access patterns decide what a given workload actually takes on real hardware.
Eight Java collections interview questions
1. Why is Map not a subtype of Collection?
A collection models individual elements, while a map models key-value entries with unique keys. Their core operations and invariants differ.
2. When would you choose ArrayList over LinkedList?
Choose it for frequent indexed reads, iteration and append-heavy workloads. It is also the usual default because its reference storage is compact and locality is favourable.
3. Can HashSet contain duplicates?
No. Internally it uses hashing and equality to reject an element equal to one already present.
4. What happens when two HashMap keys collide?
They share a bucket structure. The map then uses equality checks to locate the correct key rather than treating the hashes as unique identities.
5. Why must equal objects have equal hash codes?
Otherwise a hash-based collection may search a different bucket and fail to find an object that equality says is present.
6. Does HashMap preserve insertion order?
No. Use LinkedHashMap when insertion-order iteration is a requirement.
7. Comparable or Comparator?
Use Comparable for a class's natural order and Comparator for external, multiple or context-specific orders.
8. Why can a mutable key become unreachable?
Changing a field used in its hash code can make lookup search a different bucket from the one where the entry was stored. The entry still exists, but lookup by the mutated key may fail.
The short version
Start with the requirement. Use a list for positions and duplicates, a set for uniqueness, and a map for key-value lookup. Then decide whether you need insertion order, sorted order or the average constant-time behaviour of hashing.
For wider practice on choosing a structure by its cost, work through Data Structures MCQs.
Build the language foundation with the Complete Java course, and use the Coding & DSA courses to connect these contracts to interview problems. In every answer, name the contract, the expected cost and the trade-off.
