Collections Framework Basics — Interview Questions

How to use this lesson

Interviewers use collections questions to find out whether you pick data structures deliberately. Whenever you name a collection, say why: ordering, duplicates, and the Big-O of the operation that matters.

Q1. What is the Java Collections Framework?

Short answer: A unified set of interfaces (Collection, List, Set, Queue, Deque, Map), implementations (ArrayList, HashSet, HashMap, ArrayDeque, …) and algorithms (sorting, searching and shuffling in Collections and Arrays) for storing and processing groups of objects.

Key points to cover:

• Programming to the interfaces (List<Order> orders = new ArrayList<>()) lets you swap implementations without changing the calling code.
• It replaced the pre-Java 2 classes (Vector, Hashtable, Enumeration), which still exist but are considered legacy.

Learn it in depth → Collections Framework Recap

Q2. What are the main interfaces of the Collections Framework?

Short answer:

• Collection (the root for groups of elements), with its sub-interfaces:
  • List: ordered, allows duplicates, index-based.
  • Set: no duplicates.
  • Queue/Deque: processing order. FIFO queues, priority queues, and double-ended stacks and queues.
• Map: key → value pairs with unique keys. It's part of the framework but doesn't extend Collection.

Iterable
 └── Collection
      ├── List   → ArrayList, LinkedList
      ├── Set    → HashSet, LinkedHashSet, TreeSet (SortedSet/NavigableSet)
      └── Queue  → PriorityQueue, ArrayDeque (Deque), LinkedList
Map → HashMap, LinkedHashMap, TreeMap (SortedMap/NavigableMap), ConcurrentHashMap

Key points to cover:

• Java 21 added SequencedCollection and SequencedMap, which give a uniform getFirst(), getLast() and reversed() to ordered collections.

Learn it in depth → List, Set, and Map

Q3. How does an Iterator work?

Short answer: An Iterator walks through a collection one element at a time with hasNext() and next(). It can also safely remove the current element with iterator.remove(). Every Collection provides one through iterator(), and the enhanced for loop uses it behind the scenes.

Iterator<Order> it = orders.iterator();
while (it.hasNext()) {
    if (it.next().isCancelled()) it.remove();       // safe removal while iterating
}
orders.removeIf(Order::isCancelled);                // the Java 8 one-liner

Common trap: calling list.remove(x) inside a for-each loop. The standard collections' iterators are fail-fast, and throw a ConcurrentModificationException when the collection is structurally modified other than through the iterator itself.

Learn it in depth → Iterators & Modification Semantics

Q4. What methods do all Collection types share?

Short answer:

• add, addAll, remove, removeAll, retainAll, clear.
• size, isEmpty, contains, containsAll.
• iterator, toArray.
• Since Java 8: stream(), removeIf() and forEach().

Key points to cover:

• Immutable collections (List.of, Set.of, Collections.unmodifiableList) throw UnsupportedOperationException from the mutating methods. These methods are "optional operations" in the interface contract.

Q5. How does the Collections Framework handle concurrency?

Short answer: The ordinary collections (ArrayList, HashMap) are not thread-safe. For concurrent use there are three options:

• Synchronized wrappers: Collections.synchronizedList(...). Every method takes a single lock. Simple, but slow under contention, and you must lock manually while iterating.
• Concurrent collections in java.util.concurrent:
  • ConcurrentHashMap: fine-grained locking and CAS.
  • CopyOnWriteArrayList: for read-mostly lists.
  • ConcurrentLinkedQueue.
  • BlockingQueue implementations, for producer-consumer designs.
• Immutable collections, which are safe to share freely.

Key points to cover:

• Iterators over concurrent collections are weakly consistent (fail-safe). They don't throw a ConcurrentModificationException, but they may or may not reflect concurrent changes.

Learn it in depth → Concurrent Collections

Q6. How do you choose the right collection for a problem?

Short answer: Ask four questions: do I need key-value lookup? Uniqueness? Ordering (insertion or sorted)? Which operation dominates (random access, insert or remove, contains)?

Learn it in depth → List, Set, and Map

Q7. What did Java 8 add to the Collections Framework?

Short answer: Streams (collection.stream()), and lambda-friendly default methods: forEach, removeIf, replaceAll, sort on List, and the new Map methods (getOrDefault, putIfAbsent, computeIfAbsent, merge). Internally, HashMap gained tree bins for buckets with many collisions.

Map<String, Integer> counts = new HashMap<>();
for (String w : words) counts.merge(w, 1, Integer::sum);         // word count in one line
Map<String, List<Order>> byCustomer = new HashMap<>();
byCustomer.computeIfAbsent(o.customerId(), k -> new ArrayList<>()).add(o);

Key points to cover:

• Later additions: immutable factories (List.of, Set.of, Map.of) in Java 9, List.copyOf in Java 10, Stream.toList() in Java 16, and sequenced collections in Java 21.

Q8. What's the difference between Iterator and ListIterator?

Short answer: Iterator works on any Collection, moves forward only, and can remove. ListIterator works only on lists, moves in both directions (hasPrevious()/previous()), knows the current index (nextIndex()), and can also set (replace) and add elements during iteration.

Q9. Which algorithms do Arrays.sort() and Collections.sort() use?

Short answer:

• Arrays.sort() on primitive arrays uses Dual-Pivot Quicksort. It's fast, but not stable (stability doesn't matter for primitives).
• On object arrays, Arrays.sort() uses TimSort, a stable hybrid of merge sort and insertion sort that exploits runs already in order.
• Collections.sort() and List.sort() also use TimSort.

Key points to cover:

• Stability matters when you sort by several keys in sequence: equal elements keep their earlier relative order.
• Complexity is O(n log n). TimSort is O(n) on data that's already sorted.
• Arrays.parallelSort() splits large arrays across the ForkJoin pool.

Q10. How do you store elements in a set while preserving insertion order?

Short answer: Use a LinkedHashSet. It's a HashSet whose entries are also linked together in a doubly linked list, so iteration follows insertion order, with O(1) operations like HashSet.

Q11. How do you store elements so they stay sorted?

Short answer: Use a TreeSet (unique elements) or a TreeMap (keys). They keep elements in natural order (Comparable), or in the order of a Comparator you supply, with O(log n) operations and navigation methods such as first(), ceiling() and headSet().

TreeSet<Integer> slots = new TreeSet<>(List.of(9, 11, 14, 16));
slots.ceiling(12);     // 14: the next available slot at or after 12

Learn it in depth → TreeMap & LinkedHashMap

Q12. When would you use ArrayList, LinkedList and HashSet?

Short answer:

• ArrayList: the default list. O(1) index access, and amortised O(1) appends. It's cache-friendly, because the elements sit in one contiguous array.
• LinkedList: O(1) inserts and removals at the ends, or at a position you already hold an iterator to. In practice, ArrayDeque is usually better for queues and stacks.
• HashSet: unique elements with O(1) average add, remove and contains. Use it for membership checks and deduplication.

Common trap: claiming that LinkedList is faster for "inserting in the middle". Finding the middle takes O(n), and linked nodes are scattered in memory, so ArrayList usually wins, even for middle inserts, at typical sizes.

Learn it in depth → List, Set, and Map

Q13. What is the internal implementation of ArrayList and LinkedList?

Short answer:

• ArrayList is backed by an Object[] array.
  • When the array is full, it grows by about 50% (a new array plus a copy), so appends cost amortised O(1).
  • get(i) is O(1). Inserting or removing in the middle shifts the elements that follow: O(n).
• LinkedList is a doubly linked list of nodes (item, prev, next), with references to the head and tail.
  • Adding or removing at either end is O(1).
  • get(i) walks the list from the nearer end: O(n).
  • Each node costs extra memory.

Follow-up questions this topic invites — and their answers

Q: What is the default capacity of an ArrayList? A: new ArrayList<>() starts with an empty array, and allocates capacity 10 on the first add. After that, it grows by about 1.5× each time. If you know the size in advance, pass it (new ArrayList<>(n)) to avoid repeated copying.

Q: What's the difference between Collection and Collections? A: Collection is the root interface. Collections is a utility class of static methods: sort, unmodifiableList, synchronizedMap, emptyList, frequency.

Q: Why doesn't Map extend Collection? A: A map holds key-value pairs, not single elements, so methods such as add(E) don't fit. You get collection views instead: keySet(), values() and entrySet().

Q: Vector vs ArrayList? A: Vector is a legacy, fully synchronised list that doubles in size when it grows. ArrayList is unsynchronised, and grows by 1.5×. Use ArrayList, plus concurrent alternatives when you need thread safety.