Collections, Generics & Java’s Data Structures

TAKEAWAYS:

• Java’s Collections Framework provides ready-to-use data structures (List, Set, Map, Queue) that replace raw arrays with dynamic resizing and built-in methods.
• Generics (<E>, <K,V>) enforce type safety at compile-time, avoiding ClassCastException and enabling reusable code (e.g., ArrayList<String>).
• List (ordered, duplicates allowed) vs. Set (unique elements) vs. Map (key-value pairs) are chosen based on access patterns (index vs. hash vs. key).
• Hash-based collections (HashSet, HashMap) use hashCode() and equals() for O(1) operations, while tree-based (TreeSet, TreeMap) use O(log n) comparisons.
• Queue and PriorityQueue model FIFO/LIFO behavior (e.g., Daraz order processing, Pathao driver allocation).
• Iterators and Comparators customize sorting/searching (e.g., sorting eSewa transactions by date or amount).

Core Collections Interfaces and Implementations

Java’s Collections Framework is a unified architecture for storing and manipulating groups of objects. It includes interfaces (contracts) and implementations (concrete classes). Below is a classification:

classDiagram
    class Collection {
        <<interface>>
        +add(E e)
        +remove(Object o)
        +contains(Object o)
        +iterator()
    }
    class List {
        <<interface>>
        +get(int index)
        +add(int index, E e)
    }
    class Set {
        <<interface>>
        +add(E e) // returns false if duplicate
    }
    class Queue {
        <<interface>>
        +offer(E e)
        +poll()
        +peek()
    }
    class Map {
        <<interface>>
        +put(K key, V value)
        +get(Object key)
        +entrySet()
    }
    Collection <|-- List
    Collection <|-- Set
    Collection <|-- Queue
    Collection <|-- Map
    class ArrayList {
        +dynamic array
        +O(1) random access
        +O(n) insertion/deletion (middle)
    }
    class LinkedList {
        +doubly-linked list
        +O(1) insertion/deletion (head/tail)
        +O(n) random access
    }
    class HashSet {
        +backed by HashMap
        +O(1) add/contains (average)
    }
    class TreeSet {
        +backed by TreeMap
        +O(log n) operations
        +sorted order
    }
    class PriorityQueue {
        +heap-based
        +O(log n) insertion
        +O(1) peek/poll (min/max)
    }
    class HashMap {
        +key-value pairs
        +O(1) get/put (average)
    }
    List <|-- ArrayList
    List <|-- LinkedList
    Set <|-- HashSet
    Set <|-- TreeSet
    Queue <|-- PriorityQueue
    Map <|-- HashMap

1. List Interface: Ordered, Indexed Collections

Definition: A List is an ordered collection (sequence) that allows duplicate elements. Access is by index (0-based).

Key Implementations

Example: ArrayList vs. LinkedList

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListDemo {
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        List<String> linkedList = new LinkedList<>();

        // Adding elements
        arrayList.add("Kathmandu");
        arrayList.add("Pokhara");
        linkedList.add("Lalitpur");
        linkedList.add("Bhaktapur");

        // Insertion in middle (ArrayList is slower)
        arrayList.add(1, "Chitwan");  // Shifts elements
        linkedList.add(1, "Dharan");  // Faster for linked lists
    }
}

Visual: Insertion in ArrayList (Shifting Elements)

STEP 1: Initial ArrayList ["Kathmandu", "Pokhara"]
STEP 2: Insert "Chitwan" at index 1 → ["Kathmandu", "Chitwan", "Pokhara"]

Real-World Analogy:

• eSewa Transaction History: Stored as an ArrayList<Transaction> where each transaction is accessed by index (e.g., history.get(0) for the first payment).
• Pathao Driver Queue: A LinkedList<Driver> where drivers are added/removed from the front (FIFO) for ride allocation.

2. Set Interface: Unique Elements

Definition: A Set contains no duplicates and is unordered (unless using TreeSet). Useful for membership tests (contains()).

Key Implementations

Example: Removing Duplicates from a List

import java.util.*;

public class SetDemo {
    public static void main(String[] args) {
        List<String> names = Arrays.asList("Rohan", "Sita", "Rohan", "Hari");
        Set<String> uniqueNames = new HashSet<>(names); // Removes duplicates
        System.out.println(uniqueNames); // [Rohan, Sita, Hari] (order not guaranteed)
    }
}

Visual: HashSet Internals (Collision Handling)

Bucket 0: "Rohan" → "Sita" → null
Bucket 1: "Hari" → null

Real-World Analogy:

• Nepse Stock Symbols: Stored in a HashSet<String> to ensure no duplicate symbols (e.g., "NTC" appears only once).
• Khalti User IDs: A TreeSet<String> keeps IDs sorted for binary search-based validation.

3. Map Interface: Key-Value Pairs

Definition: A Map stores key-value pairs where each key is unique. Used for fast lookups by key.

Key Implementations

Example: Storing User Profiles

import java.util.*;

public class MapDemo {
    public static void main(String[] args) {
        Map<String, String> userProfiles = new HashMap<>();
        userProfiles.put("user1", "Rohan,25,Kathmandu");
        userProfiles.put("user2", "Sita,22,Pokhara");

        // Retrieve by key
        String profile = userProfiles.get("user1");
        System.out.println(profile); // "Rohan,25,Kathmandu"
    }
}

Visual: HashMap Collision Resolution (Chaining)

Key: "user1" → Value: "Rohan,25,Kathmandu" → null
Key: "user2" → Value: "Sita,22,Pokhara" → null

Real-World Analogy:

• eSewa User Database: A HashMap<String, User> where the key is the user’s phone number (e.g., "98XXXXXXXX") and the value is a User object.
• Daraz Product Catalog: A TreeMap<String, Product> where keys are product names (sorted alphabetically) for efficient search.

Generics: Type-Safe Collections

Definition: Generics allow classes/methods to operate on objects of various types while providing compile-time type safety. Without generics, you’d use Object and risk ClassCastException.

Why Use Generics?

• Type Safety: Compile-time checks (e.g., ArrayList<String> cannot hold integers).
• Code Reusability: Write once, use for any type (e.g., List<E>).
• Eliminates Casting: No need for (String) list.get(0).

Syntax

// Generic class
class Box<T> {
    private T content;
    public void set(T content) { this.content = content; }
    public T get() { return content; }
}

// Generic method
public <T> void printArray(T[] array) {
    for (T element : array) {
        System.out.println(element);
    }
}

Example: Generic Pair Class

public class Pair<K, V> {
    private K key;
    private V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() { return key; }
    public V getValue() { return value; }
}

Usage:

Pair<String, Integer> agePair = new Pair<>("Rohan", 25);
System.out.println(agePair.getKey());   // "Rohan"
System.out.println(agePair.getValue()); // 25

Visual: Generic Type Erasure

At runtime, all generic types are replaced with Object:
Pair<String, Integer> → Pair<Object, Object>

graph LR
    A["Pair<String, Integer>"] -->|"Compile-time"| B["Pair<Object, Object>"]
    B -->|"Runtime"| C["Actual Object storage"]

Real-World Analogy:

• Khalti Transaction Pairs: A Map<String, Transaction> where String is the transaction ID and Transaction is a generic class holding amount, date, etc.
• Pathao Ride Data: A List<Pair<Driver, Location>> to track driver locations dynamically.

Queue and PriorityQueue: Specialized Collections

1. Queue Interface (FIFO)

Definition: A Queue follows First-In-First-Out (FIFO). Used for task scheduling, buffering, etc.

Key Implementations

Example: Order Processing (Daraz)

import java.util.LinkedList;
import java.util.Queue;

public class OrderQueue {
    public static void main(String[] args) {
        Queue<String> orderQueue = new LinkedList<>();
        orderQueue.offer("Order123");  // Enqueue
        orderQueue.offer("Order456");

        String nextOrder = orderQueue.poll(); // Dequeue
        System.out.println("Processing: " + nextOrder); // "Order123"
    }
}

Visual: Queue Operations

STEP 1: Empty Queue []
STEP 2: After offer("Order123") → ["Order123"]
STEP 3: After offer("Order456") → ["Order123", "Order456"]
STEP 4: After poll() → ["Order456"]

2. PriorityQueue (Min-Heap)

Definition: A PriorityQueue orders elements based on a priority (natural ordering or custom Comparator). Used for scheduling (e.g., shortest job first).

Example: Pathao Driver Allocation

import java.util.PriorityQueue;

public class DriverPriorityQueue {
    public static void main(String[] args) {
        // Min-heap based on distance from pickup location
        PriorityQueue<Double> drivers = new PriorityQueue<>();
        drivers.offer(5.2);  // Distance in km
        drivers.offer(2.8);
        drivers.offer(7.1);

        double closestDriver = drivers.poll(); // 2.8
        System.out.println("Allocated driver at: " + closestDriver + " km");
    }
}

Visual: PriorityQueue (Min-Heap)

STEP 1: Insert 5.2 → [5.2]
STEP 2: Insert 2.8 → [2.8, 5.2]
STEP 3: Insert 7.1 → [2.8, 5.2, 7.1]
STEP 4: poll() → 2.8 (smallest)

graph TD
    A["Insert 5.2"] --> B["[5.2]"]
    B -->|"Insert 2.8"| C["[2.8, 5.2]"]
    C -->|"Insert 7.1"| D["[2.8, 5.2, 7.1]"]
    D -->|"poll()"| E["[5.2, 7.1]"]

Real-World Analogy:

• Pathao Ride Matching: Drivers are stored in a PriorityQueue based on proximity to the pickup location (shortest distance first).
• NTC Call Center: Calls are processed in a PriorityQueue where emergency calls have higher priority.

Iterators and Comparators

1. Iterator Interface

Definition: An Iterator provides a way to traverse collections while allowing modifications (e.g., remove()).

Example: Removing Even Numbers

import java.util.*;

public class IteratorDemo {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
        Iterator<Integer> iterator = numbers.iterator();

        while (iterator.hasNext()) {
            int num = iterator.next();
            if (num % 2 == 0) {
                iterator.remove(); // Safe removal
            }
        }
        System.out.println(numbers); // [1, 3, 5]
    }
}

Visual: Iterator Traversal

STEP 1: iterator.next() → 1 (odd, keep)
STEP 2: iterator.next() → 2 (even, remove)
STEP 3: iterator.next() → 3 (odd, keep)

2. Comparator Interface

Definition: A Comparator defines a custom ordering for objects. Used with sort(), TreeSet, and PriorityQueue.

Example: Sorting eSewa Transactions by Amount

import java.util.*;

class Transaction {
    String id;
    double amount;
    Transaction(String id, double amount) {
        this.id = id; this.amount = amount;
    }
}

public class ComparatorDemo {
    public static void main(String[] args) {
        List<Transaction> transactions = Arrays.asList(
            new Transaction("T1", 500),
            new Transaction("T2", 2000)
        );

        // Sort by amount (descending)
        transactions.sort((t1, t2) -> Double.compare(t2.amount, t1.amount));
        System.out.println(transactions); // [T2, T1]
    }
}

Visual: Custom Sorting with Comparator

Before: [T1(500), T2(2000)]
After:  [T2(2000), T1(500)]

Real-World Analogy:

• Nepse Stock Prices: A TreeSet<Stock> sorted by price (ascending/descending) for trend analysis.
• Khalti Transactions: A PriorityQueue<Transaction> where transactions are ordered by timestamp (newest first).

In the Real World

1. eSewa Bill Payments

   • Data Structure: HashMap<String, User> (key: phone number, value: User object).
   • Generics: List<PaymentTransaction<E>> where E is a generic enum (ELECTRICITY, WATER, etc.).
   • Why? Fast O(1) lookup for user details and type-safe transaction records.

2. Daraz Order Processing

   • Data Structure: PriorityQueue<Order> where orders are prioritized by:
     • Time placed (FIFO for same priority).
     • Order value (higher value first for premium users).
   • Algorithm: Custom Comparator<Order> compares orderTime and amount.
   • Why? Ensures high-value orders are processed quickly during sales.

3. Pathao Driver Allocation

   • Data Structure: HashMap<String, Driver> (key: driver ID, value: Driver object) + PriorityQueue<Driver> for ride matching.
   • Generics: List<Pair<Driver, Location>> to track driver locations dynamically.
   • Why? Efficient O(1) driver lookup and priority-based ride assignment.

4. Nepse Stock Market Data

   • Data Structure: TreeMap<String, Stock> (key: stock symbol, value: Stock object) for sorted listings.
   • Operations: stockMap.floorKey("NTC") to find the largest symbol ≤ "NTC".
   • Why? Enables range queries (e.g., "show all stocks between 'A' and 'D'").

5. Khalti Transaction History

   • Data Structure: ArrayList<Transaction> for chronological order + HashSet<String> to track unique transaction IDs.
   • Generics: Map<String, List<Transaction>> where key is user ID and value is their transaction list.
   • Why? Fast duplicate detection and user-specific history retrieval.

Exam Tip

Common Exam Patterns for Unit 9

1. Code Writing (30%)

   • Write a method to:
     • Remove duplicates from a List using HashSet.
     • Sort a List of custom objects using Comparator.
     • Implement a Queue for task scheduling.
   • Example Question:

     "Write a Java method reverseList(List<T> list) that reverses a list using an iterator."

2. Short Answer (20%)

   • Define:
     • List vs. Set vs. Map.
     • Generics and type erasure.
     • Time complexity of HashMap vs. TreeMap operations.
   • Example Question:

     "Why does HashSet not guarantee order while LinkedHashSet does?"

3. Problem Solving (30%)

   • Given a scenario (e.g., "Design a system to track NTC call center calls"), choose the appropriate collection and justify.
   • Example Question:

     "A bank wants to store customer accounts where each account has a unique ID and balance. Which collection should be used and why?" Answer: HashMap<String, Double> (key: account ID, value: balance) for O(1) balance checks.

4. Debugging (20%)

   • Identify errors in code snippets (e.g., incorrect iterator usage, missing generics).
   • Example Question:

     "What is wrong with this code?"

     List list = new ArrayList();
     list.add("Hello");
     list.add(123); // Compile-time error: raw type
     

Key Formulas/Concepts to Memorize

Common Pitfalls

• Raw Types: Avoid List list = new ArrayList(); → use List<String> list = new ArrayList<>();.
• ConcurrentModificationException: Never modify a collection while iterating (use iterator’s remove()).
• HashCode/Equals Contract: Override both or neither in custom objects for HashSet/HashMap.
• PriorityQueue Order: By default, it’s a min-heap. Use Collections.reverseOrder() for max-heap.

Practice Questions for Self-Assessment

1. Implement a Stack using ArrayList with push(), pop(), and peek().
2. Write a method to merge two sorted List<Integer> into one sorted list using Collections.sort().
3. Design a Library class with HashMap<String, Book> to store books by title and TreeSet<Book> to track overdue books.
4. Explain why LinkedHashMap preserves insertion order while HashMap does not.
5. Given a List<String>, count the frequency of each word using HashMap<String, Integer>.

Recommended Resources

• Books:
  • Java: The Complete Reference (Herbert Schildt) – Collections chapter.
  • Effective Java (Joshua Bloch) – Item 28 (prefer lists to arrays).
• Online:
  • Oracle’s Collections Framework Tutorial.
  • GeeksforGeeks’ Java Collections.
• Tools:
  • Use VisualVM to analyze memory usage of collections.
  • Practice on HackerRank (Java Collections section).