Collections, Generics & Java Data Structures: Lists, Sets, Maps & Type Safety

TAKEAWAYS:

• Collections Framework provides ready-to-use data structures (ArrayList, HashSet, HashMap) to store and manipulate groups of objects efficiently.
• Generics enable type-safe programming by allowing classes/methods to operate on objects of any type while enforcing compile-time checks.
• Autoboxing/Unboxing automatically converts between primitive types and their wrapper classes (e.g., int ↔ Integer), but generics bypass this for strict type safety.
• Common Interfaces like List, Set, and Map define behaviors for collections, while implementations like ArrayList or HashMap provide concrete functionality.
• Real-world use: eSewa uses Queue for transaction processing, Daraz uses HashMap for inventory tracking, and banks use List for transaction history.
• Exam focus: Write generic methods/classes, explain autoboxing vs. generics, and compare List, Set, and Map with code examples and traces.

1. Introduction to Collections Framework

Java’s Collections Framework is a unified architecture for storing and manipulating groups of objects. It provides:

• Interfaces (e.g., List, Set, Map) defining behaviors.
• Implementations (e.g., ArrayList, HashSet, HashMap) providing concrete functionality.
• Algorithms (e.g., sorting, searching) to perform operations on collections.

Why Use Collections?

• Avoid manual array management (fixed size, primitive-only).
• Built-in methods for common operations (e.g., add(), remove(), contains()).
• Type safety and performance optimizations.

2. Core Interfaces and Implementations

A. List Interface

Stores elements in an ordered sequence (allows duplicates). Common Implementations:

Visual: ArrayList vs. LinkedList

graph LR
    A["ArrayList (Contiguous Memory)"] -->|"Add/Remove at End"| B["O(1)"]
    A -->|"Add/Remove in Middle"| C["O(n)"]
    D["LinkedList (Nodes with Pointers)"] -->|"Add/Remove at End"| E["O(1)"]
    D -->|"Add/Remove in Middle"| F["O(1)"]

B. Set Interface

Stores unique elements (no duplicates). Common Implementations:

Visual: HashSet Insertion

C. Map Interface

Stores key-value pairs (no duplicate keys). Common Implementations:

Visual: HashMap Operations

3. Generics: Type-Safe Programming

Generics allow classes/methods to operate on objects of any type while enforcing type safety at compile time.

Why Generics?

• Type Safety: Avoid ClassCastException by specifying types.
• Code Reusability: Write once, use for any type (e.g., List<Integer>, List<String>).
• Cleaner Code: No need for casts (e.g., (Integer) 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);
    }
}

Autoboxing vs. Generics

Worked Example: Generic Method for Sum

public class GenericSum {
    public static <T extends Number> double sum(T[] numbers) {
        double sum = 0;
        for (T num : numbers) {
            sum += num.doubleValue();
        }
        return sum;
    }

    public static void main(String[] args) {
        Integer[] intNumbers = {1, 2, 3, 4, 5};
        Double[] doubleNumbers = {1.1, 2.2, 3.3};
        System.out.println("Sum of integers: " + sum(intNumbers)); // 15.0
        System.out.println("Sum of doubles: " + sum(doubleNumbers)); // 6.6
    }
}

Trace Table for sum(intNumbers):

4. Real-World Applications

A. eSewa: Transaction Queue (Queue Interface)

• Use Case: Processing payments in FIFO order.
• Implementation: LinkedList (fast insertions/removals at both ends).
• Why?:
  • Ensures fairness (first transaction processed first).
  • Thread-safe operations for concurrent users.

Visual: eSewa Transaction Queue

B. Daraz: Inventory Management (HashMap)

• Use Case: Mapping product IDs to stock quantities.
• Implementation: HashMap<String, Integer>.
• Why?:
  • O(1) lookup time for product availability.
  • Easy updates (e.g., map.put("Laptop101", 5)).

Visual: Daraz Inventory HashMap

C. NEPSE: Stock Price Leaderboard (TreeSet)

• Use Case: Displaying stocks sorted by price.
• Implementation: TreeSet<Stock> (natural ordering by price).
• Why?:
  • Automatically sorted (no manual sorting needed).
  • Efficient insertion/deletion (O(log n)).

5. Common Pitfalls and Best Practices

A. Autoboxing vs. Generics

• Mistake: Using generics with primitives (e.g., List<int> is invalid).
• Fix: Use wrapper classes (List<Integer>).

B. Type Erasure

• Generics are erased at runtime (e.g., List<String> and List<Integer> become List).
• Implication: Cannot use primitives in generics (no List<int>).

C. Wildcards (?)

• Upper Bounded: List<? extends Number> (accepts Number or subclasses).
• Lower Bounded: List<? super Integer> (accepts Integer or superclasses like Number).

Example:

void printList(List<? extends Number> list) {
    for (Number num : list) {
        System.out.println(num);
    }
}

6. Exam Tip

What Examiners Look For

1. Definitions:

   • Clearly define List, Set, Map, and generics.
   • Example: "A Set is a collection that does not allow duplicate elements."

2. Code Examples:

   • Write a generic class/method (e.g., Box<T> or sum()).
   • Include a trace table for algorithms (e.g., ArrayList insertion).

3. Comparisons:

   • Compare ArrayList vs. LinkedList (time complexity for operations).
   • Compare HashSet vs. TreeSet (ordering and performance).

4. Real-World Scenarios:

   • Relate to eSewa (Queue), Daraz (HashMap), or NEPSE (TreeSet).
   • Example: "eSewa uses a Queue to process transactions in FIFO order, ensuring fairness."

5. Autoboxing vs. Generics:

   • Explain why List<int> is invalid but List<Integer> works.
   • Example: "Generics enforce type safety at compile time, while autoboxing converts primitives to objects at runtime."

Sample Exam Questions and Answers

Q1: What is generic programming? Why is it needed? A: Generic programming allows classes/methods to operate on objects of any type while maintaining type safety. It is needed to:

• Avoid ClassCastException by specifying types at compile time.
• Write reusable code (e.g., a Box<T> class for any type).
• Improve readability and maintainability.

Q2: Write a Java program to find whether the integer at even indices of an array is odd or not, and display the sum of those odd integers. A:

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

public class EvenIndexOddCheck {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        List<Integer> oddNumbers = new ArrayList<>();
        int sum = 0;

        for (int i = 0; i < numbers.length; i += 2) {
            if (numbers[i] % 2 != 0) {
                oddNumbers.add(numbers[i]);
                sum += numbers[i];
            }
        }

        System.out.println("Odd numbers at even indices: " + oddNumbers);
        System.out.println("Sum of odd numbers: " + sum);
    }
}

Output:

Odd numbers at even indices: [1, 3, 5, 7, 9]
Sum of odd numbers: 25

Q3: Why do we need generics? A: Generics are needed for:

1. Type Safety: Prevents ClassCastException by enforcing types at compile time.
   • Example: List<String> cannot store integers.
2. Code Reusability: Write a single method/class for multiple types.
   • Example: A Box<T> class for any object type.
3. Cleaner Code: Eliminates the need for casts (e.g., (String) list.get(0)).
4. Performance: Avoids runtime type checks (unlike autoboxing).

7. Summary Table: Collections and Generics

8. Practice Problems

1. Write a generic method to find the maximum element in an array of any type that implements Comparable.
2. Compare ArrayList and LinkedList with a table showing time complexity for add(), remove(), and get().
3. Explain why List<int> is invalid in Java, but List<Integer> is valid.
4. Write a program to simulate a bank transaction history using List<Transaction>, where Transaction is a class with fields amount and date.