Unit 13: Collections Framework

Opening Hook — Flipkart Big Billion Day: How Collections Power India's Biggest Sale

Learning Outcomes — Bloom's Taxonomy Mapped (12 Outcomes)

Concept Explanation — Java Collections Framework from Scratch

1. The Collection Hierarchy

Think of Java Collections Framework like a well-organised Indian railway system. Just as railways have different types of trains (Express, Local, Rajdhani) for different needs, Collections has different interfaces and classes for different data storage needs.

Hierarchy
// Collection Hierarchy (Iterable → Collection → List/Set/Queue)

Iterable (root interface)
  └── Collection
        ├── List (ordered, allows duplicates)
        │     ├── ArrayList    — dynamic array, O(1) random access
        │     ├── LinkedList   — doubly-linked list, O(1) insert/delete
        │     └── Vector       — synchronized (legacy, use ArrayList)
        │           └── Stack   — LIFO (legacy, use ArrayDeque)
        │
        ├── Set (no duplicates)
        │     ├── HashSet      — unordered, O(1) ops, uses HashMap
        │     ├── LinkedHashSet— insertion-ordered, O(1) ops
        │     └── TreeSet      — sorted, O(log n) ops, uses TreeMap
        │
        └── Queue (FIFO processing)
              ├── PriorityQueue— min-heap, O(log n) insert/remove
              └── Deque (double-ended queue)
                    └── ArrayDeque — resizable array, faster than Stack/LinkedList

// Map Hierarchy (separate from Collection)
Map (key-value pairs)
  ├── HashMap        — unordered, O(1) ops, allows null key
  ├── LinkedHashMap  — insertion/access ordered, O(1) ops
  ├── TreeMap        — sorted by key, O(log n) ops
  └── Hashtable      — synchronized (legacy, use ConcurrentHashMap)

2. ArrayList vs LinkedList — The 10-Parameter Showdown

Analogy: ArrayList is like a movie theatre — seats are numbered (indexed), you can jump to seat 42 instantly, but inserting a new seat in the middle means shifting everyone. LinkedList is like a train — each coach is linked to the next, adding/removing a coach in the middle is easy, but finding coach #42 means walking from the engine.

Java
// ArrayList — Flipkart Cart Example
import java.util.ArrayList;

public class FlipkartCart {
    public static void main(String[] args) {
        ArrayList<String> cart = new ArrayList<>();
        
        // Adding items to cart — O(1) amortized
        cart.add("iPhone 16 Pro");        // index 0
        cart.add("Samsung Galaxy S24");    // index 1
        cart.add("OnePlus Nord 4");       // index 2
        cart.add("Boat Airdopes 441");    // index 3
        
        // Random access — O(1)
        System.out.println("Item 2: " + cart.get(1)); // Samsung Galaxy S24
        
        // Remove item — O(n) shifts remaining
        cart.remove("Samsung Galaxy S24");
        
        // Iterate cart
        System.out.println("=== Your Flipkart Cart ===");
        for (int i = 0; i < cart.size(); i++) {
            System.out.println((i+1) + ". " + cart.get(i));
        }
        System.out.println("Total items: " + cart.size());
    }
}

3. HashSet, TreeSet, LinkedHashSet — No Duplicates Allowed

Analogy: Think of Set like Aadhaar numbers — every Indian gets exactly ONE unique number. You can't have two people with the same Aadhaar. That's what Set does — guarantees uniqueness.

Java
// HashSet — Unique voter IDs at a booth
import java.util.*;

public class VoterBooth {
    public static void main(String[] args) {
        Set<String> voters = new HashSet<>();
        
        voters.add("VOTER001");
        voters.add("VOTER002");
        voters.add("VOTER003");
        voters.add("VOTER001");  // ❌ Duplicate — silently ignored!
        
        System.out.println("Total unique voters: " + voters.size()); // 3
        System.out.println("VOTER001 voted? " + voters.contains("VOTER001")); // true
        
        // TreeSet — sorted leaderboard
        TreeSet<Integer> scores = new TreeSet<>();
        scores.add(85); scores.add(92); scores.add(78); scores.add(95);
        System.out.println("Sorted scores: " + scores);    // [78, 85, 92, 95]
        System.out.println("Topper: " + scores.last());     // 95
        System.out.println("Lowest: " + scores.first());    // 78
    }
}

4. PriorityQueue & ArrayDeque

Analogy: PriorityQueue is like an emergency room (ER) at AIIMS Delhi — patients aren't treated first-come-first-served. The most critical patient (highest priority) is treated first, regardless of arrival time. ArrayDeque is like a Mumbai local train door — people can enter and exit from both ends.

Java
// PriorityQueue — IRCTC Flash Deal Countdown
import java.util.*;

public class FlashDealCountdown {
    public static void main(String[] args) {
        // Min-heap: deal expiring soonest comes first
        PriorityQueue<String> dealQueue = new PriorityQueue<>(
            (a, b) -> {
                int minA = Integer.parseInt(a.split(":")[0]);
                int minB = Integer.parseInt(b.split(":")[0]);
                return minA - minB;
            }
        );
        
        dealQueue.add("5:iPhone 16 - ₹59,999");
        dealQueue.add("2:Boat Earbuds - ₹499");
        dealQueue.add("10:Samsung TV - ₹29,999");
        dealQueue.add("1:Mi Band - ₹999");
        
        System.out.println("=== Flash Deals (Expiring Soonest First) ===");
        while (!dealQueue.isEmpty()) {
            String deal = dealQueue.poll(); // removes and returns head
            System.out.println("⏰ Expiring in " + deal.split(":")[0] 
                + " min → " + deal.split(":")[1]);
        }
    }
}

Java
// ArrayDeque — Faster than Stack and LinkedList
import java.util.*;

public class BrowserHistory {
    public static void main(String[] args) {
        // Use ArrayDeque as Stack (LIFO)
        Deque<String> history = new ArrayDeque<>();
        
        history.push("flipkart.com");
        history.push("flipkart.com/mobiles");
        history.push("flipkart.com/iphone-16");
        
        System.out.println("Current page: " + history.peek());  // iphone-16
        history.pop();  // Go back
        System.out.println("After back: " + history.peek());   // /mobiles
    }
}

5. HashMap — Internal Working (Interview Favourite)

Plain English: Imagine a library with 16 shelves (buckets). When you bring a new book, the librarian runs the book title through a formula (hash function) that produces a shelf number. The book goes on that shelf. When you ask for it later, same formula → same shelf → instant retrieval.

Internals
// HashMap Internal Structure (Java 8+)

Bucket Array (Node<K,V>[])
┌───────────────────────────────────────────────┐
│ [0] → null                                    │
│ [1] → Node("Milk",40) → null                 │
│ [2] → null                                    │
│ [3] → Node("Rice",60) → Node("Dal",80) → null│  ← collision chain
│ [4] → null                                    │
│ ...                                           │
│ [7] → 🌳 Red-Black Tree (if > 8 nodes)       │  ← treeified bucket
│ ...                                           │
│[15] → Node("Bread",35) → null                │
└───────────────────────────────────────────────┘

Default capacity: 16 buckets
Load factor: 0.75 (resize when 75% full)
TREEIFY_THRESHOLD: 8 (linked list → tree)

Java
// Full Code: FlipkartCatalog using HashMap
import java.util.*;

public class FlipkartCatalog {
    static HashMap<String, Double> catalog = new HashMap<>();
    static Scanner sc = new Scanner(System.in);
    
    public static void main(String[] args) {
        // Pre-load catalog
        catalog.put("PROD001", 59999.0);  // iPhone 16
        catalog.put("PROD002", 24999.0);  // Samsung Galaxy M34
        catalog.put("PROD003", 1499.0);   // Boat Rockerz 450
        catalog.put("PROD004", 34999.0);  // HP Laptop 15s
        catalog.put("PROD005", 999.0);    // Mi Band 8
        
        int choice;
        do {
            System.out.println("\n=== Flipkart Product Catalog ===");
            System.out.println("1. Add Product");
            System.out.println("2. Search Product by ID");
            System.out.println("3. Update Price");
            System.out.println("4. Remove Product");
            System.out.println("5. Display All Products");
            System.out.println("6. Exit");
            System.out.print("Choice: ");
            choice = sc.nextInt();
            sc.nextLine();
            
            switch (choice) {
                case 1: addProduct(); break;
                case 2: searchProduct(); break;
                case 3: updatePrice(); break;
                case 4: removeProduct(); break;
                case 5: displayAll(); break;
            }
        } while (choice != 6);
    }
    
    static void addProduct() {
        System.out.print("Product ID: ");
        String id = sc.nextLine();
        System.out.print("Price (₹): ");
        double price = sc.nextDouble();
        catalog.put(id, price); // O(1)
        System.out.println("✅ Product added!");
    }
    
    static void searchProduct() {
        System.out.print("Enter Product ID: ");
        String id = sc.nextLine();
        if (catalog.containsKey(id)) {  // O(1)
            System.out.println("✅ Found! Price: ₹" + catalog.get(id));
        } else {
            System.out.println("❌ Product not found.");
        }
    }
    
    static void updatePrice() {
        System.out.print("Product ID: ");
        String id = sc.nextLine();
        if (catalog.containsKey(id)) {
            System.out.print("New price (₹): ");
            catalog.put(id, sc.nextDouble()); // O(1) — replaces old value
            System.out.println("✅ Price updated!");
        } else {
            System.out.println("❌ Product not found.");
        }
    }
    
    static void removeProduct() {
        System.out.print("Product ID: ");
        String id = sc.nextLine();
        if (catalog.remove(id) != null) { // O(1)
            System.out.println("✅ Product removed.");
        } else {
            System.out.println("❌ Product not found.");
        }
    }
    
    static void displayAll() {
        System.out.println("\n--- All Products ---");
        for (Map.Entry<String, Double> entry : catalog.entrySet()) {
            System.out.printf("%-10s → ₹%,.0f%n", entry.getKey(), entry.getValue());
        }
        System.out.println("Total products: " + catalog.size());
    }
}

6. TreeMap & LinkedHashMap

Java
// TreeMap — Student marks sorted by name
import java.util.*;

public class SortedStudentMarks {
    public static void main(String[] args) {
        TreeMap<String, Integer> marks = new TreeMap<>();
        marks.put("Aarav", 92);
        marks.put("Zara", 88);
        marks.put("Kishore", 95);
        marks.put("Diya", 91);
        marks.put("Meena", 87);
        
        System.out.println("Alphabetical order: " + marks);
        System.out.println("First (A): " + marks.firstKey());    // Aarav
        System.out.println("Last (Z): " + marks.lastKey());     // Zara
        System.out.println("D-M range: " + marks.subMap("D", "N")); // Diya, Kishore, Meena
    }
}

7. Collections Utility Class

The Collections class (note the 's' — it's different from Collection interface) provides static utility methods for operating on collections:

Java
import java.util.*;

public class CollectionsDemo {
    public static void main(String[] args) {
        List<Integer> marks = new ArrayList<>(Arrays.asList(78, 92, 45, 88, 65));
        
        Collections.sort(marks);           // [45, 65, 78, 88, 92]
        Collections.reverse(marks);        // [92, 88, 78, 65, 45]
        Collections.shuffle(marks);        // random order
        
        System.out.println("Max: " + Collections.max(marks));  // 92
        System.out.println("Min: " + Collections.min(marks));  // 45
        System.out.println("Freq of 78: " + Collections.frequency(marks, 78));
        
        // Unmodifiable collection — immutable wrapper
        List<String> states = Collections.unmodifiableList(
            Arrays.asList("Maharashtra", "Karnataka", "Tamil Nadu")
        );
        // states.add("Kerala"); ← throws UnsupportedOperationException!
    }
}

8. Iterator & ListIterator

Java
// Safe removal during iteration — Iterator
import java.util.*;

public class SafeRemoval {
    public static void main(String[] args) {
        List<Integer> marks = new ArrayList<>(Arrays.asList(85, 32, 91, 28, 76, 44));
        
        // ❌ WRONG: ConcurrentModificationException
        // for (int m : marks) { if (m < 40) marks.remove(Integer.valueOf(m)); }
        
        // ✅ CORRECT: Use Iterator
        Iterator<Integer> it = marks.iterator();
        while (it.hasNext()) {
            if (it.next() < 40) {
                it.remove();  // Safe removal!
            }
        }
        System.out.println("Passing marks: " + marks); // [85, 91, 76, 44]
    }
}

9. Comparable vs Comparator

Java
// Full Code: StudentResultSystem — Comparable + Comparator
import java.util.*;

class Student implements Comparable<Student> {
    String name;
    int rollNo;
    double percentage;
    
    Student(String name, int rollNo, double percentage) {
        this.name = name;
        this.rollNo = rollNo;
        this.percentage = percentage;
    }
    
    // Natural ordering: by roll number
    public int compareTo(Student other) {
        return this.rollNo - other.rollNo;
    }
    
    public String toString() {
        return String.format("Roll#%d %-12s %.1f%%", rollNo, name, percentage);
    }
}

public class StudentResultSystem {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student("Aarav Patel", 103, 87.5));
        students.add(new Student("Sneha Iyer", 101, 92.3));
        students.add(new Student("Rohit Kumar", 105, 78.9));
        students.add(new Student("Diya Sharma", 102, 95.1));
        students.add(new Student("Kishore Nair", 104, 88.7));
        
        // Sort by roll number (Comparable — natural order)
        Collections.sort(students);
        System.out.println("=== Sorted by Roll Number (Comparable) ===");
        students.forEach(System.out::println);
        
        // Sort by percentage descending (Comparator — custom order)
        students.sort((s1, s2) -> Double.compare(s2.percentage, s1.percentage));
        System.out.println("\n=== Sorted by Percentage Descending (Comparator) ===");
        students.forEach(System.out::println);
        
        // Sort by name alphabetically (Comparator)
        students.sort(Comparator.comparing(s -> s.name));
        System.out.println("\n=== Sorted by Name (Comparator) ===");
        students.forEach(System.out::println);
        
        // Store in HashMap for O(1) lookup by roll number
        HashMap<Integer, Student> studentMap = new HashMap<>();
        for (Student s : students) {
            studentMap.put(s.rollNo, s);
        }
        
        // Instant lookup
        System.out.println("\n🔍 Lookup Roll#103: " + studentMap.get(103));
    }
}

10. Full Code: IRCTC Waitlist System

Java
// IRCTC Waitlist System using LinkedList as Queue
import java.util.*;

class Passenger {
    String pnr, name;
    int age;
    String status; // CONFIRMED, WAITLIST, RAC
    
    Passenger(String pnr, String name, int age) {
        this.pnr = pnr;
        this.name = name;
        this.age = age;
        this.status = "WAITLIST";
    }
    
    public String toString() {
        return String.format("PNR: %s | %-15s | Age: %d | Status: %s", 
            pnr, name, age, status);
    }
}

public class IRCTCWaitlist {
    static final int MAX_CONFIRMED = 5;
    static List<Passenger> confirmed = new ArrayList<>();
    static Queue<Passenger> waitlist = new LinkedList<>();
    static Map<String, Passenger> pnrMap = new HashMap<>();
    static int pnrCounter = 1000;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int choice;
        
        do {
            System.out.println("\n🚂 === IRCTC Booking System ===");
            System.out.println("1. Book Ticket");
            System.out.println("2. Cancel Ticket (by PNR)");
            System.out.println("3. Check PNR Status");
            System.out.println("4. View All Passengers");
            System.out.println("5. Exit");
            System.out.print("Choice: ");
            choice = sc.nextInt(); sc.nextLine();
            
            switch (choice) {
                case 1:
                    System.out.print("Name: ");
                    String name = sc.nextLine();
                    System.out.print("Age: ");
                    int age = sc.nextInt();
                    bookTicket(name, age);
                    break;
                case 2:
                    System.out.print("Enter PNR: ");
                    cancelTicket(sc.nextLine());
                    break;
                case 3:
                    System.out.print("Enter PNR: ");
                    checkPNR(sc.nextLine());
                    break;
                case 4:
                    viewAll();
                    break;
            }
        } while (choice != 5);
        System.out.println("🙏 Thank you for using IRCTC!");
    }
    
    static void bookTicket(String name, int age) {
        String pnr = "PNR" + (++pnrCounter);
        Passenger p = new Passenger(pnr, name, age);
        
        if (confirmed.size() < MAX_CONFIRMED) {
            p.status = "CONFIRMED";
            confirmed.add(p);
            System.out.println("✅ CONFIRMED! PNR: " + pnr);
        } else {
            p.status = "WL/" + (waitlist.size() + 1);
            waitlist.add(p);  // enqueue at end
            System.out.println("⏳ WAITLISTED (" + p.status + ") PNR: " + pnr);
        }
        pnrMap.put(pnr, p); // O(1) lookup later
    }
    
    static void cancelTicket(String pnr) {
        Passenger p = pnrMap.get(pnr);
        if (p == null) { System.out.println("❌ PNR not found."); return; }
        
        if (p.status.equals("CONFIRMED")) {
            confirmed.remove(p);
            // Promote first waitlisted passenger
            if (!waitlist.isEmpty()) {
                Passenger promoted = waitlist.poll(); // dequeue from front
                promoted.status = "CONFIRMED";
                confirmed.add(promoted);
                System.out.println("🎉 " + promoted.name + " promoted to CONFIRMED!");
            }
        } else {
            waitlist.remove(p);
        }
        pnrMap.remove(pnr);
        System.out.println("✅ Ticket " + pnr + " cancelled.");
    }
    
    static void checkPNR(String pnr) {
        Passenger p = pnrMap.get(pnr); // O(1)
        System.out.println(p != null ? p : "❌ PNR not found.");
    }
    
    static void viewAll() {
        System.out.println("\n--- Confirmed (" + confirmed.size() + "/" + MAX_CONFIRMED + ") ---");
        confirmed.forEach(System.out::println);
        System.out.println("--- Waitlist (" + waitlist.size() + ") ---");
        waitlist.forEach(System.out::println);
    }
}

Learn by Doing — 3-Tier Lab: Student Result Management System

Problem Set

Syntax-Level Questions (5)

1. Write the syntax to create an ArrayList of Strings, add 3 elements, and print the element at index 1.
2. Write code to create a HashMap<String, Integer>, insert 3 key-value pairs, and retrieve a value by key.
3. Write the syntax to iterate over a HashSet<String> using an Iterator and print each element.
4. Write code to sort an ArrayList<Integer> in descending order using Collections.sort() with a Comparator.
5. Write the syntax to create a PriorityQueue<Integer> (max-heap) and add 5 elements.

Programming Questions (8)

1. Write a program that takes 10 names as input, stores them in an ArrayList, and displays them sorted alphabetically using Collections.sort().
2. Write a program that counts the frequency of each word in a paragraph using HashMap<String, Integer>.
3. Write a program to remove all duplicate elements from an ArrayList using a HashSet.
4. Implement a phone book using TreeMap<String, String> (name → phone number) that displays contacts in alphabetical order with search functionality.
5. Write a program to find the first non-repeating character in a string using LinkedHashMap.
6. Implement a todo list using LinkedList with operations: addTask, removeTask, markComplete, displayPending.
7. Write a program that merges two sorted ArrayLists into a single sorted ArrayList without using Collections.sort().
8. Create a program that reads student names and marks from input, stores them in a HashMap, and prints students who scored above average.

Industry-Level Problems (3) — IRCTC Waitlist Theme

Interview-Level Problems (3) — LRU Cache Theme

Java
import java.util.*;

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true!
        this.capacity = capacity;
    }
    
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // evict when over capacity
    }
    
    public static void main(String[] args) {
        LRUCache<String, String> cache = new LRUCache<>(3);
        
        cache.put("user1", "Aarav");
        cache.put("user2", "Sneha");
        cache.put("user3", "Kishore");
        System.out.println(cache); // {user1=Aarav, user2=Sneha, user3=Kishore}
        
        cache.get("user1");  // Access user1 — moves to end
        cache.put("user4", "Diya");  // Capacity exceeded — user2 evicted (LRU)
        
        System.out.println(cache); // {user3=Kishore, user1=Aarav, user4=Diya}
        // user2 was evicted because it was least recently used!
    }
}

MCQ Assessment Bank — 30 Questions (Bloom's Mapped)

Remember / Identify (Q1–Q5)

Understand / Explain (Q6–Q10)

Apply (Q11–Q15)

Analyze (Q16–Q20)

Evaluate (Q21–Q25)

Create (Q26–Q30)

Short Answer Questions (8)

Q1. What is the difference between Collection and Collections in Java?

Answer: Collection (singular) is a root interface in java.util that represents a group of objects (extended by List, Set, Queue). Collections (plural) is a utility class in java.util that provides static helper methods like sort(), reverse(), shuffle(), max(), min(), unmodifiableList(). Analogy: Collection is the blueprint of a library; Collections is the librarian who organises books.

Q2. Why doesn't Map extend the Collection interface?

Answer: Collection stores single elements (Collection<E>), while Map stores key-value pairs (Map<K,V>). Their fundamental contracts are different — Collection has add(E), Map has put(K,V). Forcing Map to extend Collection would require awkward compromises. However, Map provides keySet(), values(), and entrySet() to expose its contents as Collections.

Q3. What is the load factor in HashMap and why is the default 0.75?

Answer: Load factor = (number of entries / number of buckets). It determines when to resize. Default 0.75 means HashMap resizes when 75% full. This is a balanced trade-off: too low (0.5) = more memory, fewer collisions, faster; too high (1.0) = less memory, more collisions, slower. 0.75 is empirically optimal for most use cases, as recommended by Java documentation.

Q4. Explain fail-fast vs fail-safe iterators with examples.

Answer: Fail-fast iterators (ArrayList, HashMap, HashSet) throw ConcurrentModificationException if the collection is structurally modified during iteration. They use an internal modCount field. Fail-safe iterators (ConcurrentHashMap, CopyOnWriteArrayList) work on a copy/snapshot, so modifications don't affect iteration. Example: new ArrayList<>().iterator() is fail-fast; new ConcurrentHashMap<>().keySet().iterator() is fail-safe.

Q5. How does TreeSet maintain sorted order?

Answer: TreeSet uses a Red-Black Tree (a self-balancing binary search tree) internally. Every insertion triggers tree rebalancing to maintain the BST property (left < parent < right). Elements must implement Comparable or a Comparator must be provided. All operations (add, remove, contains) are O(log n) due to tree height being O(log n).

Q6. What happens internally when you call hashMap.put(key, value)?

Answer: Step 1: Compute hash = key.hashCode(), then spread it: hash ^ (hash >>> 16). Step 2: Find bucket index: index = hash & (capacity - 1). Step 3: If bucket is empty, create a new Node and place it there. Step 4: If bucket is occupied, traverse the linked list/tree using equals(). If matching key found, replace value. If not found, append new Node. Step 5: If list length exceeds 8, treeify. Step 6: If size exceeds threshold (capacity × loadFactor), resize to 2× capacity.

Q7. Why should you override both hashCode() and equals() for HashMap keys?

Answer: HashMap uses hashCode() to find the bucket and equals() to find the exact key within the bucket. If only equals() is overridden, two equal objects may have different hashCodes (from Object.hashCode()), landing in different buckets — so get() won't find the key. Contract: if a.equals(b) is true, then a.hashCode() == b.hashCode() must also be true.

Q8. Compare ArrayDeque with Stack and LinkedList for stack operations.

Answer: ArrayDeque is the recommended replacement for both. vs Stack: Stack extends Vector (synchronized, slow). ArrayDeque has no synchronization overhead and is 3–4× faster. vs LinkedList: LinkedList allocates a new node object per element (GC pressure, cache misses). ArrayDeque uses a resizable array (contiguous memory, cache-friendly). Java docs explicitly state: "This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue."

Long Answer Questions (3)

Q1. Explain the internal working of HashMap in Java with a diagram. Cover: hashing, bucket array, collision handling (chaining), treeification, and resizing. [10 marks]

Answer:

(a) Hashing: When put(K, V) is called, HashMap computes the hash of the key: int hash = key.hashCode(); hash = hash ^ (hash >>> 16);. The XOR with the upper 16 bits reduces collision probability by spreading the hash bits.

(b) Bucket Index: The bucket index is calculated as index = hash & (n-1) where n = array length (always a power of 2). This is equivalent to hash % n but faster (bitwise AND).

(c) Storage: The bucket array Node<K,V>[] table starts with 16 slots. Each slot (bucket) is initially null. When an entry is added, a Node object (containing hash, key, value, next pointer) is placed at the computed index.

(d) Collision Handling (Chaining): When two keys hash to the same index, a collision occurs. The new Node is appended to the linked list in that bucket. On get(K), the chain is traversed using equals() to find the matching key.

(e) Treeification (Java 8+): When a bucket's linked list exceeds TREEIFY_THRESHOLD (8 nodes), it's converted to a Red-Black Tree for O(log n) lookup instead of O(n). This prevents worst-case performance when many keys hash to the same bucket.

(f) Resizing: When total entries exceed capacity × loadFactor (default: 16 × 0.75 = 12), HashMap doubles the array to 32 and rehashes all entries. This is called rehashing. The new index for each entry may change since hash & (newN-1) uses an additional bit.

Time Complexity: O(1) average for put/get/remove. O(log n) worst case per bucket (treeified). O(n) worst case overall only if resize is triggered.

Q2. Compare List, Set, and Map interfaces in Java with at least 8 differences. Provide real-world examples for each. [10 marks]

Answer:

Real-world examples: List = Flipkart shopping cart (ordered items, duplicates allowed — buy 2 of same). Set = Aadhaar database (each citizen has one unique ID). Map = PhonePe contact-to-UPI mapping (name → UPI ID, instant lookup).

Q3. Discuss Comparable vs Comparator with complete code examples. When would you use one over the other? [10 marks]

Answer:

Comparable (java.lang.Comparable<T>): Defines the natural ordering of a class by implementing compareTo(T other) inside the class itself. Only ONE ordering per class. Used when the class has an obvious default sort order (e.g., String: alphabetical, Integer: ascending).

Comparator (java.util.Comparator<T>): Defines external, custom orderings without modifying the original class. Implements compare(T o1, T o2). Supports MULTIPLE orderings (sort by name, by age, by salary). Can be passed to Collections.sort(), TreeSet, TreeMap, PriorityQueue.

When to use Comparable: (1) You own the class and want a default order. (2) There's one obvious natural order. (3) Example: Student sorted by rollNo by default.

When to use Comparator: (1) You don't own the class (third-party). (2) Multiple sort orders needed. (3) Lambda expressions make it concise in Java 8+. Example: Sort employees by salary, then by name, then by department — three different Comparators.

Java 8 shortcuts: Comparator.comparing(Student::getName), Comparator.comparing(Student::getPercentage).reversed(), Comparator.comparing(Student::getName).thenComparing(Student::getAge).

Lab Program 4 — Managing Multiple Items with ArrayList

Java
/*
 * Lab 4: Managing Multiple Items with ArrayList
 * Course: Programming in Java — Unit 13
 * Demonstrates: ArrayList operations — add, remove, update, iterate
 */
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

public class Lab4_ArrayListManager {
    static ArrayList<String> items = new ArrayList<>();
    static Scanner sc = new Scanner(System.in);
    
    public static void main(String[] args) {
        // Pre-load some items
        items.add("Rice (5kg)");
        items.add("Toor Dal (1kg)");
        items.add("Sugar (2kg)");
        items.add("Milk (1L)");
        items.add("Bread (1 pack)");
        
        int choice;
        do {
            System.out.println("\n╔══════════════════════════════════╗");
            System.out.println("║   🛒 GROCERY LIST MANAGER        ║");
            System.out.println("╠══════════════════════════════════╣");
            System.out.println("║ 1. Add Item                      ║");
            System.out.println("║ 2. Remove Item by Name           ║");
            System.out.println("║ 3. Update Item by Position       ║");
            System.out.println("║ 4. Display All (for loop)        ║");
            System.out.println("║ 5. Display All (for-each loop)   ║");
            System.out.println("║ 6. Display All (Iterator)        ║");
            System.out.println("║ 7. Check if item exists          ║");
            System.out.println("║ 8. Exit                          ║");
            System.out.println("╚══════════════════════════════════╝");
            System.out.print("Enter choice: ");
            choice = sc.nextInt();
            sc.nextLine(); // consume newline
            
            switch (choice) {
                case 1: addItem(); break;
                case 2: removeItem(); break;
                case 3: updateItem(); break;
                case 4: displayWithForLoop(); break;
                case 5: displayWithForEach(); break;
                case 6: displayWithIterator(); break;
                case 7: checkItem(); break;
                case 8: System.out.println("👋 Goodbye!"); break;
                default: System.out.println("❌ Invalid choice!");
            }
        } while (choice != 8);
    }
    
    // ADD — O(1) amortized
    static void addItem() {
        System.out.print("Enter item name: ");
        String item = sc.nextLine();
        items.add(item);
        System.out.println("✅ '" + item + "' added! Total items: " + items.size());
    }
    
    // REMOVE by name — O(n)
    static void removeItem() {
        System.out.print("Enter item name to remove: ");
        String item = sc.nextLine();
        if (items.remove(item)) {
            System.out.println("✅ '" + item + "' removed!");
        } else {
            System.out.println("❌ Item not found!");
        }
    }
    
    // UPDATE by index — O(1)
    static void updateItem() {
        displayWithForLoop();
        System.out.print("Enter position to update (1-" + items.size() + "): ");
        int pos = sc.nextInt();
        sc.nextLine();
        if (pos >= 1 && pos <= items.size()) {
            System.out.print("Enter new item name: ");
            String newItem = sc.nextLine();
            String old = items.set(pos - 1, newItem); // set() returns old value
            System.out.println("✅ '" + old + "' updated to '" + newItem + "'");
        } else {
            System.out.println("❌ Invalid position!");
        }
    }
    
    // ITERATION METHOD 1: Traditional for loop
    static void displayWithForLoop() {
        System.out.println("\n--- Grocery List (for loop) ---");
        for (int i = 0; i < items.size(); i++) {
            System.out.println((i + 1) + ". " + items.get(i));
        }
        System.out.println("Total: " + items.size() + " items");
    }
    
    // ITERATION METHOD 2: Enhanced for-each loop
    static void displayWithForEach() {
        System.out.println("\n--- Grocery List (for-each) ---");
        int count = 1;
        for (String item : items) {
            System.out.println(count++ + ". " + item);
        }
    }
    
    // ITERATION METHOD 3: Iterator (safe for removal during iteration)
    static void displayWithIterator() {
        System.out.println("\n--- Grocery List (Iterator) ---");
        Iterator<String> it = items.iterator();
        int count = 1;
        while (it.hasNext()) {
            System.out.println(count++ + ". " + it.next());
        }
    }
    
    // CHECK existence — O(n)
    static void checkItem() {
        System.out.print("Enter item to search: ");
        String item = sc.nextLine();
        if (items.contains(item)) {
            System.out.println("✅ Found at position: " + (items.indexOf(item) + 1));
        } else {
            System.out.println("❌ Item not in list.");
        }
    }
}

Industry Spotlight — A Day in the Life

Earn With It — Freelance & Income Roadmap

Chapter Summary

Checkpoint — Self-Assessment

✅ Unit 13 complete. MCQs: 30. Lab 4 covered. Ready for Unit 14!

[QR: Link to EduArtha video tutorial — Java Collections Framework]