Collections

advanced

Part of Advanced Java

Theory

The Java Collections Framework (JCF) is a unified architecture for storing and manipulating groups of objects. It provides interfaces, implementations, and algorithms that make working with data structures convenient and efficient.

Collection Framework Overview

The framework is organized around core interfaces:

Collection (interface)
    ├── List (ordered, allows duplicates)
    │   ├── ArrayList
    │   └── LinkedList
    ├── Set (no duplicates)
    │   ├── HashSet
    │   └── TreeSet
    └── Queue (FIFO)
        └── PriorityQueue

Map (interface — separate from Collection)
    ├── HashMap
    └── TreeMap

List — ArrayList and LinkedList

ArrayList is a resizable array implementation. It provides fast random access (O(1)) but slower insertions/deletions in the middle (O(n)).

LinkedList is a doubly-linked list. It provides fast insertions/deletions (O(1) at ends) but slower random access (O(n)).

import java.util.*;
 
List<String> arrayList = new ArrayList<>();
arrayList.add("Apple");
arrayList.add("Banana");
arrayList.add("Cherry");
System.out.println(arrayList.get(0)); // Apple
arrayList.set(1, "Blueberry");
arrayList.remove(2);
 
List<Integer> linkedList = new LinkedList<>();
linkedList.add(10);
linkedList.addFirst(5);  // Only LinkedList has addFirst
linkedList.addLast(15);

Set — HashSet and TreeSet

HashSet stores elements in a hash table. It offers O(1) operations but no guaranteed order.

TreeSet stores elements in a sorted tree structure (red-black tree). Operations are O(log n).

Set<String> hashSet = new HashSet<>();
hashSet.add("Java");
hashSet.add("Python");
hashSet.add("Java");  // Duplicate — ignored
System.out.println(hashSet.size()); // 2
 
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(30);
treeSet.add(10);
treeSet.add(20);
System.out.println(treeSet); // [10, 20, 30] — sorted

Map — HashMap and TreeMap

Maps store key-value pairs. Keys are unique; values can be duplicated.

HashMap offers O(1) lookup with no guaranteed order.

TreeMap maintains keys in sorted order (O(log n) operations).

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.put("Charlie", 92);
 
System.out.println(scores.get("Alice"));   // 95
System.out.println(scores.containsKey("Bob"));  // true
 
// Iterate over entries
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

Generics

Generics provide type safety by allowing you to specify the type of elements a collection can hold:

// Without generics (old way) — unsafe
List list = new ArrayList();
list.add("Hello");
list.add(123);  // No compile-time error
String s = (String) list.get(1);  // ClassCastException at runtime!
 
// With generics — type safe
List<String> safeList = new ArrayList<>();
safeList.add("Hello");
// safeList.add(123);  // Compile-time error!
String s = safeList.get(0);  // No cast needed

You can also create your own generic classes:

public class Box<T> {
    private T content;
 
    public void set(T content) { this.content = content; }
    public T get() { return content; }
}
 
Box<String> stringBox = new Box<>();
stringBox.set("Hello");
String value = stringBox.get();

Iterating Collections

There are several ways to iterate over collections:

For-each loop (most common):

for (String item : list) {
    System.out.println(item);
}

Iterator (use when you need to remove elements during iteration):

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if (item.startsWith("A")) {
        iterator.remove();  // Safe removal
    }
}

Streams API (Java 8+):

list.stream()
    .filter(s -> s.length() > 3)
    .map(String::toUpperCase)
    .forEach(System.out::println);

Collections Utility Class

java.util.Collections provides static utility methods:

List<Integer> numbers = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9));
 
Collections.sort(numbers);         // [1, 1, 3, 4, 5, 9]
Collections.reverse(numbers);      // [9, 5, 4, 3, 1, 1]
Collections.shuffle(numbers);      // Random order
Collections.max(numbers);          // 9
Collections.min(numbers);          // 1
Collections.frequency(numbers, 1); // 2
Collections.binarySearch(numbers, 5); // index (list must be sorted first)

Always use the interface type (List, Set, Map) for variable declarations, not the implementation type (ArrayList, HashSet, HashMap). This makes it easy to switch implementations later.

Practical Examples

Example 1: Student Grade Management

java

Example 2: Word Frequency Counter

java

When you need predictable iteration order, use LinkedHashMap or LinkedHashSet instead of HashMap/HashSet. They maintain insertion order with slightly more memory.

Exercises

List Operations

easy

Write a program that creates an ArrayList of integers (1 through 10). Then: remove all even numbers, add the square of each remaining number, and sort the list in descending order.

Expected Output:

[81, 49, 25, 9, 1]

Phone Directory with Map

medium

Create a phone directory using a TreeMap that stores names (keys) and phone numbers (values). Implement methods: addContact, removeContact, findContact, and listAllContacts (sorted by name).

Expected Output:

Alice: 555-1234\nBob: 555-5678\nCharlie: 555-9012\nAlice: 555-1234

Set Intersection and Union

medium

Write a program that takes two arrays of integers, converts them to HashSet, and computes their union, intersection, and symmetric difference (elements in one set but not both).

Expected Output:

Union: [1, 2, 3, 4, 5, 6, 7, 8, 9]\nIntersection: [4, 5, 6]\nSymmetric Diff: [1, 2, 3, 7, 8, 9]

Mini Quiz

Mini Project

Mini Project: Task Manager Application

Build a task manager that allows users to add, remove, search, and filter tasks. Use appropriate collections for different operations: ArrayList for all tasks, TreeSet for sorted display, and HashMap for quick lookup by ID.

Requirements:

Bonus Challenge

Add a deadline field (LocalDate) and a method getOverdueTasks() that returns tasks past their deadline with status not DONE. Add persistence by saving/loading tasks to a file.