Java Collections Framework: Lists, Sets, Maps & Algorithms

TAKEAWAYS:

• Understand the hierarchy of Collection interfaces (Collection → List/Set/Queue → Map) and their concrete implementations (e.g., ArrayList vs. LinkedList).
• Know when to use each: HashSet for uniqueness, TreeMap for sorted keys, PriorityQueue for scheduling, and ArrayList for random access.
• Master iterators (Iterator, ListIterator) and comparators (Comparator, Comparable) for custom ordering.
• Memorize time complexities of core operations (e.g., HashMap.get() is O(1), ArrayList.add() is O(n) for shifting).
• Apply Collections algorithms (Collections.sort(), Arrays.binarySearch()) and stream operations (filter(), map(), reduce()).
• Debug common pitfalls: ConcurrentModificationException, NullPointerException in HashMap, and unsupported operations (e.g., add() on Set).

1. Introduction to Collections Framework

The Java Collections Framework (JCF) is a unified architecture for storing and manipulating groups of objects. It provides:

• Interfaces (e.g., List, Set, Map, Queue) defining contracts.
• Implementations (e.g., ArrayList, HashSet, HashMap) providing concrete behavior.
• Algorithms (e.g., sorting, searching) for common operations.
• Utilities (e.g., Collections, Arrays) for static operations.

Why use JCF?

• Avoid reinventing the wheel (e.g., no need to write your own linked list).
• Optimized for performance (e.g., HashMap uses hashing for O(1) lookups).
• Thread-safe alternatives (e.g., Vector, Hashtable, or ConcurrentHashMap).

2. Core Interfaces and Implementations

2.1 Collection Interface Hierarchy

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) // No duplicates
    }
    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

2.2 Key Implementations

3. Lists: ArrayList vs. LinkedList

3.1 ArrayList

• Underlying Structure: Dynamic array (resizes when full).
• Operations:
  • get(int index): O(1) (direct access).
  • add(E e): O(1) amortized (resizing may take O(n)).
  • add(int index, E e): O(n) (shifts elements).
  • remove(int index): O(n) (shifts elements).

Example: Student Gradebook

ArrayList<Double> grades = new ArrayList<>();
grades.add(85.5);  // [85.5]
grades.add(90.0);  // [85.5, 90.0]
grades.add(1, 78.0); // [85.5, 78.0, 90.0] (O(n) shift)

Visual: ArrayList Resizing

3.2 LinkedList

• Underlying Structure: Doubly-linked list (nodes with prev/next pointers).
• Operations:
  • get(int index): O(n) (traverse from head).
  • add(E e): O(1) (append to tail).
  • add(int index, E e): O(n) (traverse to index).
  • remove(int index): O(n) (traverse to index).

Example: Undo/Redo Stack (Pathao Order History)

LinkedList<String> orderHistory = new LinkedList<>();
orderHistory.add("Order #123");  // [123]
orderHistory.addFirst("Order #124"); // [124, 123] (O(1))
orderHistory.removeLast();       // [124] (undo last order)

Visual: LinkedList Operations

3.3 When to Use Which?

4. Sets: HashSet, LinkedHashSet, and TreeSet

4.1 HashSet

• Underlying Structure: Backed by a HashMap (keys only).
• Properties:
  • No duplicates (uses hashCode() and equals()).
  • Unordered (unless using LinkedHashSet).
  • Allows one null value.

Example: Unique Users in eSewa

Set<String> activeUsers = new HashSet<>();
activeUsers.add("user123");  // {user123}
activeUsers.add("user123");  // No change (duplicate)
activeUsers.add(null);       // {user123, null}

Visual: HashSet Internals

4.2 TreeSet

• Underlying Structure: Red-Black Tree (self-balancing BST).
• Properties:
  • Sorted (natural order or Comparator).
  • No null allowed.
  • O(log n) for add()/remove()/contains().

Example: Sorted Product Prices (Daraz)

Set<Double> prices = new TreeSet<>();
prices.add(1500.0);  // {1500.0}
prices.add(999.99);  // {999.99, 1500.0}
prices.add(1200.50); // {999.99, 1200.50, 1500.0}

Visual: TreeSet Insertion Steps

4.3 LinkedHashSet

• Underlying Structure: Hash table + linked list (maintains insertion order).
• Use Case: LRU cache, access-order tracking.

5. Maps: HashMap, TreeMap, and LinkedHashMap

5.1 HashMap

• Underlying Structure: Array of buckets + linked lists (or trees for collision resolution).
• Properties:
  • O(1) average-case for get()/put().
  • No ordering (use LinkedHashMap/TreeMap for order).
  • Allows one null key and multiple null values.

Example: User Profiles (Khalti)

Map<String, String> profiles = new HashMap<>();
profiles.put("user123", "Prem");  // {user123=Prem}
profiles.put("user456", null);    // {user123=Prem, user456=null}
profiles.put(null, "Guest");     // {null=Guest, user123=Prem, user456=null}

Visual: HashMap Collision Handling

5.2 TreeMap

• Underlying Structure: Red-Black Tree.
• Properties:
  • Sorted by keys (natural order or Comparator).
  • O(log n) for get()/put().
  • No null keys/values.

Example: Word Frequency (Nepali Dictionary)

Map<String, Integer> wordCount = new TreeMap<>();
wordCount.put("काठमाडौं", 15);
wordCount.put("नेपाल", 20);
// Sorted keys: {काठमाडौं=15, नेपाल=20}

Visual: TreeMap Insertion

5.3 LinkedHashMap

• Underlying Structure: Hash table + doubly-linked list (maintains insertion/access order).
• Use Case: LRU cache (e.g., browser history).

6. Queues and Priority Queues

graph TD
    A["Task 1 (Priority 3)"] --> B["Task 2 (Priority 1)"]
    C["Task 3 (Priority 2)"] --> B
    B --> D["Execute Task 2"]
    D --> E["Next Task"]

6.1 Queue Implementations

Example: Order Processing (Daraz)

Queue<String> orderQueue = new LinkedList<>();
orderQueue.offer("Order123");  // [Order123]
orderQueue.offer("Order456");  // [Order123, Order456]
String nextOrder = orderQueue.poll(); // "Order123" (FIFO)

Visual: Queue Operations

6.2 PriorityQueue

• Underlying Structure: Min-heap (or max-heap with Comparator).
• Properties:
  • O(log n) for add()/remove().
  • No null elements.
  • Unordered iteration (use Arrays.sort() for ordered output).

Example: Task Scheduler (NTC Network Traffic)

PriorityQueue<Integer> bandwidthTasks = new PriorityQueue<>((a, b) -> b - a);
bandwidthTasks.offer(100);  // [100]
bandwidthTasks.offer(50);   // [100, 50]
int highestPriority = bandwidthTasks.poll(); // 100 (max-heap)

Visual: PriorityQueue as Max-Heap

7. Iterators and Comparators

7.1 Iterator

• Purpose: Traverse collections without exposing internal structure.
• Methods:
  • hasNext(): Checks for remaining elements.
  • next(): Returns next element.
  • remove(): Removes last returned element (optional).

Example: Safe Removal (Avoiding ConcurrentModificationException)

List<String> names = new ArrayList<>();
names.add("Ramesh"); names.add("Sita");
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
    String name = iterator.next();
    if (name.equals("Sita")) {
        iterator.remove(); // Safe removal
    }
}
// names = ["Ramesh"]

7.2 Comparator vs. Comparable

Example: Sorting Students by GPA

class Student implements Comparable<Student> {
    String name;
    double gpa;
    public int compareTo(Student other) {
        return Double.compare(this.gpa, other.gpa);
    }
}
List<Student> students = new ArrayList<>();
students.add(new Student("A", 3.8));
students.add(new Student("B", 3.5));
Collections.sort(students); // Sorted by GPA

Example: Custom Comparator (Sort by Name Length)

Comparator<String> byLength = (s1, s2) -> Integer.compare(s1.length(), s2.length());
List<String> names = Arrays.asList("Prem", "Sita", "Ramesh");
Collections.sort(names, byLength); // ["Prem", "Sita", "Ramesh"]

8. Collections Algorithms

8.1 Sorting

Example: Sorting a List of Integers

List<Integer> numbers = Arrays.asList(5, 2, 8, 1);
Collections.sort(numbers); // [1, 2, 5, 8]

8.2 Binary Search

• Requirement: List must be sorted.
• Time Complexity: O(log n).

Example: Finding a Student by ID

List<Integer> studentIds = Arrays.asList(101, 105, 110, 120);
int index = Collections.binarySearch(studentIds, 110); // 2

8.3 Shuffling

• Use Case: Randomizing order (e.g., lottery).
• Method: Collections.shuffle(List).

Example: Randomizing a Deck of Cards

List<String> deck = Arrays.asList("Ace", "King", "Queen");
Collections.shuffle(deck); // ["Queen", "Ace", "King"]

8.4 Stream Operations (Java 8+)

• Purpose: Functional-style operations on collections.
• Common Methods:
  • filter(Predicate): Select elements.
  • map(Function): Transform elements.
  • reduce(BinaryOperator): Aggregate (e.g., sum).
  • collect(Collector): Convert to another collection.

Example: Filter and Sum Even Numbers

List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
int sum = numbers.stream()
                 .filter(n -> n % 2 == 0)
                 .mapToInt(Integer::intValue)
                 .sum(); // 6 (2 + 4)

9. Time and Space Complexity

*Amortized for ArrayList/HashMap due to resizing.

10. Common Pitfalls and Best Practices

10.1 Pitfalls

1. ConcurrentModificationException:

   • Cause: Modifying a collection while iterating (e.g., for (E e : list)).
   • Fix: Use Iterator.remove() or ConcurrentHashMap.

2. NullPointerException in HashMap:

   • Cause: Using null as a key in a TreeMap or multiple null keys in HashMap.
   • Fix: Avoid null keys in TreeMap; use HashMap for one null key.

3. Unsupported Operations:

   • Cause: Calling add() on a Set or put() with duplicate keys in a Map.
   • Fix: Use List/Map implementations appropriately.

10.2 Best Practices

• Use ArrayList for frequent random access.
• Use LinkedList for frequent insertions/deletions at ends.
• Use HashSet for uniqueness checks (e.g., deduplication).
• Use TreeSet/TreeMap for sorted data.
• Prefer ArrayDeque over LinkedList for queues (better performance).
• Use streams for functional-style operations (e.g., filtering, mapping).
• Thread Safety: Use Collections.synchronizedList() or ConcurrentHashMap for multi-threaded access.

11. Real-World Applications

11.1 eSewa: User Authentication

• Data Structure: HashSet<String> for storing unique user IDs.
• Why?
  • O(1) contains() to check if a user exists.
  • No duplicates (each user ID is unique).
• Code Snippet:

  Set<String> authenticatedUsers = new HashSet<>();
  if (authenticatedUsers.add(userId)) {
      System.out.println("Login successful!");
  }
  

11.2 Khalti: Transaction Processing

• Data Structure: PriorityQueue<Transaction> (sorted by priority).
• Why?
  • High-priority transactions (e.g., emergency payments) are processed first.
  • O(log n) insertion for new transactions.
• Code Snippet:

  PriorityQueue<Transaction> queue = new PriorityQueue<>((t1, t2) -> t2.priority - t1.priority);
  queue.offer(new Transaction("Emergency", 5));
  Transaction next = queue.poll(); // Highest priority
  

11.3 Daraz: Order Queue

• Data Structure: LinkedList<Order> for FIFO order processing.
• Why?
  • First-come-first-served (FCFS) ensures fairness.
  • O(1) add()/remove() for enqueue/dequeue.
• Code Snippet:

  Queue<Order> orderQueue = new LinkedList<>();
  orderQueue.offer(new Order("Order123"));
  Order nextOrder = orderQueue.poll(); // Process oldest order
  

11.4 NTC: Network Traffic Routing

• Data Structure: TreeMap<String, Integer> for sorted routing tables.
• Why?
  • Keys (IP prefixes) are sorted for efficient lookup.
  • O(log n) for get()/put() operations.
• Code Snippet:

  Map<String, Integer> routes = new TreeMap<>();
  routes.put("192.168.1.", 1); // Sorted by IP prefix
  Integer cost = routes.get("192.168.1.100"); // O(log n)
  

11.5 NEPSE: Stock Price Tracking

• Data Structure: HashMap<String, Double> for real-time stock prices.
• Why?
  • O(1) get()/put() for quick price updates.
  • Handles null values (e.g., unlisted stocks).
• Code Snippet:

  Map<String, Double> stockPrices = new HashMap<>();
  stockPrices.put("NTC", 120.50);
  Double price = stockPrices.get("NTC"); // O(1)
  

12. Worked Example: Bank Loan Interest Calculation

Problem: A bank uses a TreeMap to store loan amounts and their corresponding interest rates (sorted by loan amount). Write a program to:

1. Add loans with amounts and rates.
2. Find the loan with the highest interest rate.
3. Calculate the total interest for loans above a threshold.

Solution:

import java.util.*;

public class BankLoan {
    public static void main(String[] args) {
        // TreeMap to store loan amounts (sorted) and rates
        Map<Double, Double> loans = new TreeMap<>();
        loans.put(10000.0, 8.5);  // {10000.0=8.5}
        loans.put(5000.0, 7.2);    // {5000.0=7.2, 10000.0=8.5}
        loans.put(20000.0, 9.0);   // {5000.0=7.2, 10000.0=8.5, 20000.0=9.0}

        // Find loan with highest interest rate
        double maxRate = Collections.max(loans.values());
        System.out.println("Highest interest rate: " + maxRate + "%");

        // Calculate total interest for loans > 10000
        double totalInterest = 0;
        for (Map.Entry<Double, Double> entry : loans.entrySet()) {
            if (entry.getKey() > 10000) {
                totalInterest += entry.getKey() * (entry.getValue() / 100);
            }
        }
        System.out.println("Total interest for loans > 10000: " + totalInterest);
    }
}

Output:

Highest interest rate: 9.0%
Total interest for loans > 10000: 1800.0 (20000 * 9%)

Visual: TreeMap State After Insertions

13. Exam Tip

13.1 What to Expect

• Theory Questions (20-30%):
  • Differences between ArrayList/LinkedList/HashSet/TreeSet.
  • Time complexities of operations (e.g., HashMap.get() vs. TreeMap.get()).
  • When to use Comparator vs. Comparable.
• Code Questions (50-60%):
  • Implementing custom comparators.
  • Writing methods to manipulate collections (e.g., merge two lists, find duplicates).
  • Debugging code with ConcurrentModificationException or NullPointerException.
• Scenario-Based (20-30%):
  • Choosing the right collection for a real-world problem (e.g., "Design a system for a hospital to manage patient appointments").
  • Explaining trade-offs (e.g., "Why use LinkedHashMap over HashMap for a cache?").

13.2 Key Formulas to Remember

1. Hashing:
   • hashCode() must follow the contract: equal objects → equal hashCode().
   • Collision resolution: chaining (linked lists) or open addressing.
2. Time Complexities:
   • ArrayList: O(1) random access, O(n) insertions/deletions in middle.
   • LinkedList: O(1) insertions/deletions at ends, O(n) random access.
   • HashSet/HashMap: O(1) average-case for add()/get().
   • TreeSet/TreeMap: O(log n) for all operations.
3. Stream Operations:
   • filter() → map() → collect() pipeline.

13.3 Common Mistakes to Avoid

• Assuming HashSet is ordered: Use LinkedHashSet for insertion order or TreeSet for sorting.
• Ignoring null in HashMap: Only one null key is allowed; multiple null values are allowed.
• Using == instead of .equals(): Always override equals() and hashCode() for custom objects in collections.
• Modifying a collection during iteration: Use Iterator.remove() or forEach with a separate list.

13.4 Quick Revision Table

14. Practice Problems

1. Merge Two Sorted Lists: Write a method to merge two ArrayList<Integer> into one sorted list.
2. Find Duplicates: Given a List<String>, use a Set to find and print duplicate elements.
3. Custom Comparator: Sort a List<Student> by GPA (descending) and then by name (ascending).
4. LRU Cache: Implement an LRU cache using LinkedHashMap (remove least recently used entry when full).
5. Word Frequency: Use a TreeMap to count word frequencies in a text and print them in sorted order.

15. Summary

• Lists: Use ArrayList for random access, LinkedList for frequent modifications.
• Sets: Use HashSet for uniqueness, TreeSet for sorting.
• Maps: Use HashMap for speed, TreeMap for sorting.
• Queues: Use PriorityQueue for scheduling, LinkedList for FIFO.
• Iterators: Always use Iterator.remove() for safe removal during iteration.
• Comparators: Prefer Comparator for flexible sorting; use Comparable for natural ordering.
• Streams: Leverage filter()/map()/reduce() for functional-style operations.

Final Tip: Practice coding collection-based problems under time constraints to build intuition for choosing the right data structure!

In the real world

• eSewa: Uses HashSet to track unique transactions (e.g., Set<String> transactionIDs) to prevent duplicate processing of the same payment request.
• Pathao: Implements PriorityQueue for driver assignment (e.g., PriorityQueue<Driver> availableDrivers sorted by proximity to the rider).
• Nepali Banks (e.g., NMB): Employs TreeMap to maintain sorted customer accounts by account number (e.g., TreeMap<String, Account>) for efficient binary-search-based lookups.