Java Collections Framework: Interfaces, Implementations & Algorithms

Core Concepts: Interfaces and Implementations

1. The Collections Framework Hierarchy

The JCF provides a unified architecture for storing and manipulating groups of objects. It consists of:

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>>
        +no duplicates
    }
    class Queue {
        <<interface>>
        +offer(E e)
        +poll()
    }
    class Map {
        <<interface>>
        +put(K key, V value)
        +get(Object key)
    }
    Collection <|-- List
    Collection <|-- Set
    Collection <|-- Queue
    Collection "1" --> "1" Iterator

Key Interfaces:

• List: Ordered collection (allows duplicates). Implementations: ArrayList, LinkedList, Vector.
• Set: No duplicates. Implementations: HashSet, LinkedHashSet, TreeSet.
• Map: Key-value pairs. Implementations: HashMap, LinkedHashMap, TreeMap.
• Queue/Deque: FIFO/LIFO operations. Implementations: PriorityQueue, ArrayDeque.

2. ArrayList vs. LinkedList: Trade-offs

Visual: ArrayList Resizing When adding the 6th element (threshold), the array doubles in size (new capacity = 16) and copies all elements.

Real-World Applications

1. E-Sewa Transaction Queue

• Data Structure Used: PriorityQueue (for urgent transactions) + HashMap (for user profiles).
• How It Works:
  • Transactions are stored in a PriorityQueue where higher-priority payments (e.g., electricity bills) are processed first.
  • User details (e.g., userID: UserProfile) are stored in a HashMap for O(1) access during verification.
  • Code Snippet:

    PriorityQueue<Transaction> queue = new PriorityQueue<>(Comparator.comparingInt(Transaction::getPriority));
    HashMap<String, User> users = new HashMap<>();
    
    // Add a high-priority transaction
    queue.offer(new Transaction("user123", "electricity", 5));
    

2. Daraz Order Processing

• Data Structure Used: LinkedList (for order history) + HashSet (for tracking duplicate orders).
• Why?:
  • Orders are added to a LinkedList to maintain insertion order (for user history).
  • A HashSet checks for duplicate orders in O(1) time to avoid fraud.
  • Example:

    LinkedList<Order> orderHistory = new LinkedList<>();
    HashSet<String> processedOrders = new HashSet<>();
    
    if (!processedOrders.contains(orderId)) {
        orderHistory.add(new Order(orderId, "Laptop"));
        processedOrders.add(orderId);
    }
    

3. Ncell Call Logs

• Data Structure Used: TreeMap (sorted by call duration) + ArrayList (for unsorted logs).
• Use Case:
  • TreeMap stores calls sorted by duration (for billing reports).
  • ArrayList logs all calls in real-time (for debugging).
  • Visual: TreeMap for Call Logs

Key Algorithms in Collections

1. Sorting a List

Algorithm: Use Collections.sort() (Timsort hybrid of merge sort + insertion sort) or list.sort() (Java 8+). Time Complexity: O(n log n).

Example: Sorting City Names

List<String> cities = new ArrayList<>(Arrays.asList("Kathmandu", "Pokhara", "Lalitpur", "Bhaktapur"));
Collections.sort(cities); // Natural order
System.out.println(cities);
// Output: [Bhaktapur, Kathmandu, Lalitpur, Pokhara]

Trace Table:

2. Finding Duplicates in a Set

Use Case: Detect duplicate orders in Daraz or repeated logins in eSewa. Solution: Use HashSet to track seen items.

List<String> orders = Arrays.asList("Laptop", "Phone", "Laptop", "Tablet");
Set<String> uniqueOrders = new HashSet<>(orders);
Set<String> duplicates = new HashSet<>(orders);
duplicates.removeAll(uniqueOrders); // {Laptop}
System.out.println("Duplicates: " + duplicates);

Visual: HashSet Collision Handling

3. PriorityQueue for Task Scheduling

Use Case: Pathao driver task assignment (highest-paying tasks first). Implementation: PriorityQueue with a custom comparator.

PriorityQueue<Task> tasks = new PriorityQueue<>(
    (t1, t2) -> Double.compare(t2.getPay(), t1.getPay())
);
tasks.offer(new Task("Deliver Pizza", 500.0));
tasks.offer(new Task("Grocery Run", 300.0));
System.out.println(tasks.poll().getDescription()); // "Deliver Pizza"

Trace Table:

Utility Classes: Collections and Arrays

1. Collections Class Methods

Example: Binary Search

List<Integer> numbers = Arrays.asList(10, 20, 30, 40, 50);
int index = Collections.binarySearch(numbers, 30); // Returns 2

2. Arrays Class Methods

Example: Converting Array to List

String[] cities = {"Kathmandu", "Pokhara", "Lalitpur"};
List<String> cityList = Arrays.asList(cities); // Fixed-size list!

Exam Tip

1. Interface vs. Implementation:

   • Always declare variables as interfaces (e.g., List<String>), not implementations (ArrayList<String>). This makes code flexible.
   • Example:

     // Good: Uses interface
     List<String> names = new ArrayList<>();
     // Bad: Tight coupling
     ArrayList<String> names = new ArrayList<>();
     

2. Time Complexity Questions:

   • Memorize the Big-O of operations for each collection:
     • HashSet: O(1) for add, contains (average case).
     • TreeSet: O(log n) for add, contains (sorted).
     • ArrayList: O(1) for get(index), O(n) for add/remove in middle.
   • Common Pitfall: Forgetting that LinkedList has O(n) get(index).

3. Real-World Scenarios:

   • Bank Loan Processing: Use PriorityQueue to prioritize high-interest loans.
   • NEPSE Stock Tracking: Use HashMap<String, Double> to store stock symbols and prices.
   • WhatsApp Chat History: Use LinkedList to maintain message order (newest first).

4. Code Snippets for Exams:

   • Always include import statements (e.g., import java.util.*;).
   • For sorting, show both Collections.sort() and list.sort() (Java 8+).
   • For duplicates, use HashSet + removeAll().

5. Common Exam Questions:

   • Differentiate between List, Set, and Map.
   • Explain why HashMap uses arrays + linked lists (for collision handling).
   • Write a program to reverse a list or find the second largest element in a PriorityQueue.

Pro Tip: Practice implementing a custom Comparator for sorting objects (e.g., sorting Student objects by GPA). This is a frequent exam question!