Collections Framework

🎯 Learning Objectives

• Navigate the Java Collections Framework hierarchy
• Use List, Set, and Map interfaces and their implementations
• Choose the right collection for different scenarios
• Use Collections utility class methods
• Understand hash-based vs tree-based collections

1. Collection Hierarchy

pseudo
Iterable
  └── Collection
        ├── List (ordered, allows duplicates)
        │     ├── ArrayList (resizable array)
        │     └── LinkedList (doubly-linked list)
        ├── Set (no duplicates)
        │     ├── HashSet (hash table, no order)
        │     ├── LinkedHashSet (insertion order)
        │     └── TreeSet (sorted, navigable)
        ├── Queue (FIFO)
        │     ├── LinkedList (also a Queue)
        │     └── PriorityQueue (priority order)
        └── Deque (double-ended)
              └── ArrayDeque
Map (separate, not extending Collection)
  ├── HashMap (hash table, no order)
  ├── LinkedHashMap (insertion order)
  └── TreeMap (sorted by keys)

2. List — Ordered Collections

2.1 ArrayList

java
List<String> list = new ArrayList<>();  // Default capacity 10
list.add("Apple");
list.add("Banana");
list.add(1, "Orange");  // Insert at index 1
String fruit = list.get(0);  // "Apple"
list.set(1, "Grape");  // Replace at index 1
list.remove("Banana");
list.remove(0);
int size = list.size();

• Backed by a dynamic array
• Fast random access O(1)
• Slow insertion/deletion in middle O(n)
• Good for: read-heavy, index-based access

2.2 LinkedList

java
List<String> list = new LinkedList<>();
list.add("First");
list.add("Last");
list.add(1, "Middle");  // Insert at index 1
String first = list.get(0);

• Doubly-linked list structure
• Fast insertion/deletion at ends O(1)
• Slower random access O(n)
• Also implements Queue and Deque
• Good for: frequent insertions/deletions at ends

3. Set — No Duplicates

3.1 HashSet

java
Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple");  // Ignored — already present
System.out.println(set.size());  // 2 (no duplicates)

• Uses hashCode() and equals()
• No guaranteed order
• O(1) for add, remove, contains
• Objects must properly override hashCode() and equals()

3.2 TreeSet

java
Set<String> sortedSet = new TreeSet<>();
sortedSet.add("Banana");
sortedSet.add("Apple");
sortedSet.add("Orange");
System.out.println(sortedSet);  // [Apple, Banana, Orange] (sorted)

• Maintains sorted order (Comparable or Comparator)
• O(log n) operations
• Navigable features: first(), last(), headSet(), tailSet()

4. Map — Key-Value Pairs

4.1 HashMap

java
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 85);
map.put("Bob", 72);
map.put("Charlie", 90);
int score = map.get("Alice");    // 85 (or null if absent)
int score2 = map.getOrDefault("Dave", 0);  // 0 with default
boolean hasKey = map.containsKey("Bob");   // true
// Iteration
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

• Uses hash table: O(1) average
• No order guarantee
• Allows one null key, many null values
• loadFactor (default 0.75) controls when to resize

4.2 TreeMap

java
Map<String, Integer> sortedMap = new TreeMap<>();
sortedMap.put("Charlie", 90);
sortedMap.put("Alice", 85);
sortedMap.put("Bob", 72);
// Iterates in key order (alphabetical)

• Red-black tree: O(log n)
• Sorted by keys (Comparable or Comparator)
• Navigable methods

5. Collections Utility Class

java
List<Integer> numbers = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9));
Collections.sort(numbers);                    // [1, 1, 3, 4, 5, 9]
Collections.reverse(numbers);                 // [9, 5, 4, 3, 1, 1]
Collections.shuffle(numbers);                 // Random order
int max = Collections.max(numbers);           // 9
int min = Collections.min(numbers);           // 1
int freq = Collections.frequency(numbers, 1); // 2
Collections.fill(numbers, 0);                 // All zeros
Collections.copy(dest, src);                  // Copy list
List<Integer> unmodifiable = Collections.unmodifiableList(numbers);

6. Choosing the Right Collection

7. Java vs Python: Collections

8. Practice Questions

Q1: What is the output?

java
Set<String> set = new HashSet<>();
set.add("A"); set.add("B"); set.add("A"); set.add("C");
System.out.println(set.size());

Answer: 3 — "A" is added only once (no duplicates). Order is not guaranteed. Q2: How does HashMap handle collisions?

Answer: When two keys hash to the same bucket, Java 8+ uses a linked list initially, then converts to a balanced tree when the bucket exceeds TREEIFY_THRESHOLD (8 entries) for performance. Q3: What is the difference between ArrayList and LinkedList?

Answer: ArrayList: backed by array, O(1) get, O(n) insert/delete middle. LinkedList: doubly-linked list, O(n) get, O(1) insert/delete at ends. Use ArrayList for most cases unless you frequently insert/delete at the beginning. Q4: Why must you override both equals() and hashCode()?

Answer: The contract: if a.equals(b) is true, then a.hashCode() == b.hashCode() MUST be true. Hash-based collections (HashSet, HashMap) use hashCode to find the bucket, then equals to check equality. Breaking the contract causes incorrect behavior. Q5: What is the difference between HashMap and Hashtable?

Answer: HashMap: not synchronized (faster), allows one null key. Hashtable: synchronized (thread-safe, slower), doesn't allow null keys. HashMap is preferred in single-threaded code. For thread safety, use ConcurrentHashMap. Q6: How to make an unmodifiable collection?

java
List<String> modifiable = new ArrayList<>(Arrays.asList("A", "B", "C"));
List<String> immutable = Collections.unmodifiableList(modifiable);

Q7: What is the initial capacity and load factor of HashMap?

Answer: Default initial capacity is 16, default load factor is 0.75. When the number of entries exceeds capacity * loadFactor, the HashMap resizes (doubles its capacity and rehashes). Q8: Can you use custom objects as HashMap keys?

Answer: Yes, but you MUST properly override equals() and hashCode(). The class should also be immutable (like String, Integer) to prevent the hash code from changing while it's a key in the map. Q9: What does the diamond operator <> do?

Answer: The diamond (<>) allows type inference on the right side of a generic assignment:

java
List<String> list = new ArrayList<>();  // Compiler infers String
// Equivalent to: new ArrayList<String>()

Q10: What is the fail-fast behavior of iterators?

Answer: Collection iterators are fail-fast: if the collection is structurally modified (added/removed elements) after the iterator is created (except through the iterator's own remove method), the iterator throws ConcurrentModificationException.

📐 Key Concepts

🔗 Cross-References

• Next: Exception Handling
• Related: Generics Join Discord Previous6.1 GenericsNext7.1 Exception Handling