Series: Java Core for Beginners Lecture: 08 of 12 Topics: Collection hierarchy · ArrayList vs LinkedList · HashSet & TreeSet · HashMap & TreeMap · Iterating collections · Choosing the right collection
Why Collections?
In Lecture 7 you worked with arrays — Java’s built-in fixed-size sequence. Arrays are fast and memory-efficient, but they have a fundamental limitation: the size is fixed at creation. If you need to add a tenth element to a nine-element array, you must allocate a new larger array, copy all elements, and discard the old one — manually.
The Java Collections Framework (JCF) solves this and much more. It provides a rich set of data structures — lists, sets, queues, maps — each with different performance characteristics and behavioral guarantees, all backed by carefully engineered implementations. Every collection grows and shrinks automatically.
Beyond resizability, collections give you:
- Rich APIs — sorting, searching, filtering, converting to arrays
- Interoperability — all collections implement common interfaces, so code written against
Listworks with anyListimplementation - Generics — type-safe containers that eliminate casting and catch type errors at compile time
- Null handling and ordering guarantees that vary by implementation
Almost all real Java programs use collections far more than raw arrays. Mastering the JCF is a prerequisite for effective Java development.
The Collection Hierarchy
The JCF is built around a hierarchy of interfaces. Understanding which interface each class implements tells you what it can do.
java.lang.Iterable
└── java.util.Collection
├── List (ordered, indexed, duplicates allowed)
│ ├── ArrayList
│ └── LinkedList
├── Set (no duplicates)
│ ├── HashSet
│ ├── LinkedHashSet
│ └── TreeSet
└── Queue (FIFO access)
└── LinkedList (also implements Deque)
java.util.Map (key-value pairs — NOT a Collection)
├── HashMap
├── LinkedHashMap
└── TreeMap
Key interfaces to know:
Collection— the root interface. Definesadd(),remove(),contains(),size(),isEmpty(),clear(), and iteration.List— an ordered collection where elements have indices. Allows duplicates. Defines index-based access:get(i),set(i, e),add(i, e),remove(i).Set— a collection that contains no duplicate elements. Does not guarantee order (unless usingLinkedHashSetorTreeSet).Map— maps keys to values. Each key maps to exactly one value. Not aCollection, but part of the framework.
Always program to the interface, not the implementation. Declare variables with the interface type:
// Good — code depends only on List behavior, not ArrayList specifics
List<String> names = new ArrayList<>();
// Avoid — ties you to ArrayList, harder to swap implementations later
ArrayList<String> names = new ArrayList<>();
ArrayList
ArrayList is the most commonly used collection in Java. It is a resizable array — it wraps a regular array internally but automatically grows when capacity is exceeded (typically doubling in size).
Creating an ArrayList
import java.util.ArrayList;
import java.util.List;
List<String> names = new ArrayList<>(); // empty list
List<Integer> scores = new ArrayList<>(50); // initial capacity hint — no elements yet
List<String> copy = new ArrayList<>(otherList); // copy constructor
The type parameter (e.g., String objects. The compiler enforces this at compile time, eliminating the need for casts when retrieving elements.
Core operations
List<String> fruits = new ArrayList<>();
// Adding elements
fruits.add("Apple"); // adds to the end
fruits.add("Banana");
fruits.add("Cherry");
fruits.add(1, "Blueberry"); // inserts at index 1, shifts others right
System.out.println(fruits); // [Apple, Blueberry, Banana, Cherry]
// Accessing elements
String first = fruits.get(0); // "Apple"
String last = fruits.get(fruits.size() - 1); // "Cherry"
// Modifying elements
fruits.set(2, "Mango"); // replaces element at index 2
System.out.println(fruits); // [Apple, Blueberry, Mango, Cherry]
// Size and emptiness
System.out.println(fruits.size()); // 4
System.out.println(fruits.isEmpty()); // false
// Checking membership
System.out.println(fruits.contains("Apple")); // true
System.out.println(fruits.indexOf("Mango")); // 2 — first occurrence index
System.out.println(fruits.indexOf("Grape")); // -1 — not found
// Removing elements
fruits.remove("Blueberry"); // removes by value (first occurrence)
fruits.remove(0); // removes by index
System.out.println(fruits); // [Mango, Cherry]
// Clearing
fruits.clear();
System.out.println(fruits.isEmpty()); // true
Important: removing by index vs by value
When your list holds Integer objects, calling remove(2) removes the element at index 2, not the element with the value 2. To remove by value, wrap it:
List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30, 20, 40));
numbers.remove(2); // removes at index 2 → [10, 20, 20, 40]
numbers.remove(Integer.valueOf(20)); // removes first occurrence of value 20 → [10, 20, 40]
Adding all elements of another collection
List<String> a = new ArrayList<>(List.of("Alice", "Bob"));
List<String> b = new ArrayList<>(List.of("Charlie", "Dave"));
a.addAll(b); // appends all of b to a
System.out.println(a); // [Alice, Bob, Charlie, Dave]
a.addAll(1, b); // inserts b starting at index 1
Sorting
List<String> names = new ArrayList<>(List.of("Charlie", "Alice", "Bob"));
Collections.sort(names); // natural order
System.out.println(names); // [Alice, Bob, Charlie]
names.sort(Comparator.reverseOrder()); // reverse order
System.out.println(names); // [Charlie, Bob, Alice]
names.sort(Comparator.comparingInt(String::length)); // by length
System.out.println(names); // [Bob, Alice, Charlie]
Converting between arrays and lists
// Array → List
String[] arr = {"Alice", "Bob", "Charlie"};
List<String> list = new ArrayList<>(Arrays.asList(arr));
// List → Array
String[] back = list.toArray(new String[0]);
Performance characteristics of ArrayList
| Operation | Time complexity | Notes |
|---|---|---|
get(i) |
O(1) | Direct index access |
set(i, e) |
O(1) | Direct index access |
add(e) (end) |
O(1) amortized | Occasional resizing |
add(i, e) (middle) |
O(n) | Shifts elements right |
remove(i) (middle) |
O(n) | Shifts elements left |
contains(e) |
O(n) | Linear search |
LinkedList
LinkedList implements both List and Deque (double-ended queue). Internally it is a doubly linked list — each element holds a reference to the previous and next elements rather than being stored in a contiguous array.
import java.util.LinkedList;
LinkedList<String> queue = new LinkedList<>();
// Standard List operations work the same
queue.add("Alice");
queue.add("Bob");
queue.add("Charlie");
// Deque operations — efficient at both ends
queue.addFirst("Zara"); // inserts at the front
queue.addLast("Dave"); // appends to the back
System.out.println(queue); // [Zara, Alice, Bob, Charlie, Dave]
String first = queue.peekFirst(); // "Zara" — looks without removing
String last = queue.peekLast(); // "Dave"
queue.pollFirst(); // removes and returns the first element
queue.pollLast(); // removes and returns the last element
System.out.println(queue); // [Alice, Bob, Charlie]
LinkedList as a stack
LinkedList<Integer> stack = new LinkedList<>();
stack.push(10); // same as addFirst
stack.push(20);
stack.push(30);
System.out.println(stack); // [30, 20, 10]
int top = stack.pop(); // same as removeFirst — returns 30
System.out.println(stack); // [20, 10]
System.out.println(stack.peek()); // 20 — look without removing
Performance characteristics of LinkedList
| Operation | Time complexity | Notes |
|---|---|---|
get(i) |
O(n) | Must traverse from head/tail |
add(e) (end) |
O(1) | Direct tail pointer update |
add(i, e) (middle) |
O(n) | Traversal to position, then O(1) insert |
addFirst/addLast |
O(1) | Direct head/tail update |
removeFirst/removeLast |
O(1) | Direct head/tail update |
contains(e) |
O(n) | Linear traversal |
ArrayList vs LinkedList — Choosing Between Them
This is one of the most common questions in Java. The practical answer for most applications is simple: use ArrayList by default.
| Criterion | ArrayList | LinkedList |
|---|---|---|
Random access get(i) |
O(1) — fast | O(n) — slow |
| Append to end | O(1) amortized | O(1) |
| Insert/delete at middle | O(n) — slow | O(n) — fast at node, slow to find it |
| Insert/delete at front | O(n) — slow | O(1) — fast |
| Memory overhead | Low (one array) | High (two pointers per node) |
| Cache performance | Excellent (contiguous memory) | Poor (scattered nodes) |
Choose ArrayList when:
- You access elements by index frequently
- You mostly add to the end
- Memory efficiency matters
- Cache performance matters (almost always)
Choose LinkedList when:
- You need a queue or deque and frequently add/remove from both ends
- You are implementing a stack, queue, or deque explicitly
In practice, even for frequent middle insertions, ArrayList often outperforms LinkedList on modern hardware because of CPU cache effects — sequential memory access is dramatically faster than pointer-chasing through scattered nodes.
HashSet and TreeSet
A Set is a collection that does not allow duplicate elements. Adding an element that already exists is silently ignored (returns false). Sets are the right tool when you need to track membership, remove duplicates, or perform mathematical set operations.
HashSet
HashSet is backed by a hash table. It offers O(1) average-time performance for add, remove, and contains. It makes no guarantee about iteration order.
import java.util.HashSet;
import java.util.Set;
Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("programming");
tags.add("beginner");
tags.add("java"); // duplicate — silently ignored
tags.add("programming"); // duplicate — silently ignored
System.out.println(tags.size()); // 3
System.out.println(tags.contains("java")); // true
System.out.println(tags); // [programming, beginner, java] — order varies
tags.remove("beginner");
System.out.println(tags); // [programming, java]
Removing duplicates from a list
One of the most common uses of HashSet:
List<Integer> withDuplicates = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5));
Set<Integer> unique = new HashSet<>(withDuplicates); // removes duplicates
List<Integer> deduplicated = new ArrayList<>(unique); // back to list if needed
System.out.println(withDuplicates); // [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
System.out.println(unique); // [1, 2, 3, 4, 5, 6, 9] — order not guaranteed
Set operations
Set<String> setA = new HashSet<>(Set.of("Alice", "Bob", "Charlie"));
Set<String> setB = new HashSet<>(Set.of("Bob", "Charlie", "Dave"));
// Union: all elements from both sets
Set<String> union = new HashSet<>(setA);
union.addAll(setB);
System.out.println(union); // [Alice, Bob, Charlie, Dave]
// Intersection: elements in both sets
Set<String> intersection = new HashSet<>(setA);
intersection.retainAll(setB);
System.out.println(intersection); // [Bob, Charlie]
// Difference: elements in A but not in B
Set<String> difference = new HashSet<>(setA);
difference.removeAll(setB);
System.out.println(difference); // [Alice]
HashSet and equals/hashCode
HashSet uses hashCode() to determine the bucket and equals() to check for true equality. For HashSet to work correctly with custom objects, you must override both equals() and hashCode() consistently (as discussed in Lecture 5). This is why Java’s built-in types like String, Integer, and LocalDate work correctly in sets — they all properly implement both methods.
Set<String> set = new HashSet<>();
set.add("hello");
set.add("hello"); // same content → equals() returns true → not added
System.out.println(set.size()); // 1
TreeSet
TreeSet is backed by a red-black tree. It stores elements in sorted order (natural ordering for types like String and Integer, or a custom Comparator) and offers O(log n) performance for add, remove, and contains.
import java.util.TreeSet;
Set<Integer> sorted = new TreeSet<>();
sorted.add(5);
sorted.add(1);
sorted.add(3);
sorted.add(2);
sorted.add(4);
System.out.println(sorted); // [1, 2, 3, 4, 5] — always sorted
// TreeSet-specific navigation methods
TreeSet<Integer> ts = new TreeSet<>(sorted);
System.out.println(ts.first()); // 1
System.out.println(ts.last()); // 5
System.out.println(ts.floor(3)); // 3 — largest element ≤ 3
System.out.println(ts.ceiling(3)); // 3 — smallest element ≥ 3
System.out.println(ts.lower(3)); // 2 — largest element < 3
System.out.println(ts.higher(3)); // 4 — smallest element > 3
System.out.println(ts.headSet(3)); // [1, 2] — elements < 3
System.out.println(ts.tailSet(3)); // [3, 4, 5] — elements ≥ 3
System.out.println(ts.subSet(2, 5)); // [2, 3, 4] — [2, 5)
LinkedHashSet
A middle ground between HashSet and TreeSet: it maintains insertion order while still offering O(1) average performance. Use it when you need unique elements in the order they were added:
Set<String> ordered = new LinkedHashSet<>();
ordered.add("banana");
ordered.add("apple");
ordered.add("cherry");
ordered.add("apple"); // duplicate — ignored
System.out.println(ordered); // [banana, apple, cherry] — insertion order preserved
HashSet vs TreeSet vs LinkedHashSet
| HashSet | TreeSet | LinkedHashSet | |
|---|---|---|---|
| Order | None | Sorted | Insertion order |
| Performance | O(1) average | O(log n) | O(1) average |
| Null elements | One allowed | Not allowed | One allowed |
| Use when | Fastest lookup, order irrelevant | Sorted iteration needed | Insertion order needed |
HashMap and TreeMap
A Map stores key-value pairs. Each key maps to exactly one value. Keys must be unique — adding a second entry with an existing key replaces the value.
HashMap
HashMap is backed by a hash table. It offers O(1) average-time performance for put, get, and remove. Order is not guaranteed.
import java.util.HashMap;
import java.util.Map;
Map<String, Integer> scores = new HashMap<>();
// Adding entries
scores.put("Alice", 95);
scores.put("Bob", 82);
scores.put("Charlie", 67);
scores.put("Alice", 98); // replaces Alice's previous score
System.out.println(scores); // {Bob=82, Alice=98, Charlie=67} — order varies
System.out.println(scores.size()); // 3
// Retrieving values
System.out.println(scores.get("Alice")); // 98
System.out.println(scores.get("Dave")); // null — key not present
// Safe retrieval with default
System.out.println(scores.getOrDefault("Dave", 0)); // 0
// Checking keys and values
System.out.println(scores.containsKey("Bob")); // true
System.out.println(scores.containsValue(82)); // true
// Removing entries
scores.remove("Charlie");
System.out.println(scores); // {Bob=82, Alice=98}
// Conditional put — only adds if key is absent
scores.putIfAbsent("Charlie", 70);
System.out.println(scores.get("Charlie")); // 70
scores.putIfAbsent("Charlie", 99); // Charlie already exists — no change
System.out.println(scores.get("Charlie")); // 70
Iterating a HashMap
Map<String, Integer> scores = new HashMap<>(Map.of("Alice", 95, "Bob", 82, "Charlie", 67));
// Iterate over entries (most common)
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
System.out.println(entry.getKey() + " → " + entry.getValue());
}
// Iterate over keys only
for (String name : scores.keySet()) {
System.out.println(name);
}
// Iterate over values only
for (int score : scores.values()) {
System.out.println(score);
}
// Modern forEach with lambda
scores.forEach((name, score) ->
System.out.printf("%-10s: %d%n", name, score)
);
Common HashMap patterns
Counting occurrences (frequency map):
String text = "the quick brown fox jumps over the lazy dog";
Map<Character, Integer> frequency = new HashMap<>();
for (char c : text.toCharArray()) {
if (c != ' ') {
frequency.put(c, frequency.getOrDefault(c, 0) + 1);
}
}
System.out.println(frequency.get('o')); // 4
Grouping elements:
List<String> words = List.of("ant", "bear", "cat", "ape", "bat", "cobra");
Map<Character, List<String>> byFirstLetter = new HashMap<>();
for (String word : words) {
char key = word.charAt(0);
byFirstLetter.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}
System.out.println(byFirstLetter);
// {a=[ant, ape], b=[bear, bat], c=[cat, cobra]}
computeIfAbsent(key, mappingFunction) creates the value (here, a new ArrayList) only if the key is absent, then returns it. This eliminates the null check boilerplate.
Merging counts:
Map<String, Integer> sales = new HashMap<>();
String[] items = {"apple", "banana", "apple", "cherry", "banana", "apple"};
for (String item : items) {
sales.merge(item, 1, Integer::sum);
// If key absent: put(item, 1)
// If key present: put(item, existingValue + 1)
}
System.out.println(sales); // {banana=2, cherry=1, apple=3}
TreeMap
TreeMap stores entries sorted by key using natural ordering or a custom Comparator. It offers O(log n) performance for put, get, and remove.
import java.util.TreeMap;
Map<String, Integer> sorted = new TreeMap<>();
sorted.put("Charlie", 67);
sorted.put("Alice", 95);
sorted.put("Bob", 82);
System.out.println(sorted); // {Alice=95, Bob=82, Charlie=67} — always sorted by key
// TreeMap-specific navigation
TreeMap<String, Integer> tm = new TreeMap<>(sorted);
System.out.println(tm.firstKey()); // "Alice"
System.out.println(tm.lastKey()); // "Charlie"
System.out.println(tm.floorKey("B")); // "Alice" — largest key ≤ "B"
System.out.println(tm.ceilingKey("B")); // "Bob" — smallest key ≥ "B"
System.out.println(tm.headMap("Charlie")); // {Alice=95, Bob=82} — keys < "Charlie"
System.out.println(tm.tailMap("Bob")); // {Bob=82, Charlie=67} — keys ≥ "Bob"
LinkedHashMap
Like LinkedHashSet, LinkedHashMap preserves insertion order:
Map<String, String> config = new LinkedHashMap<>();
config.put("host", "localhost");
config.put("port", "5432");
config.put("database", "mydb");
config.put("username", "admin");
config.forEach((k, v) -> System.out.println(k + "=" + v));
// host=localhost
// port=5432
// database=mydb
// username=admin
HashMap vs TreeMap vs LinkedHashMap
| HashMap | TreeMap | LinkedHashMap | |
|---|---|---|---|
| Key order | None | Sorted by key | Insertion order |
| Performance | O(1) average | O(log n) | O(1) average |
| Null keys | One allowed | Not allowed | One allowed |
| Use when | Fastest lookup | Sorted key iteration | Insertion order needed |
Iterating Collections
Java offers several ways to iterate over collections. Knowing which to use in each context makes your code cleaner and more expressive.
Enhanced for loop (for-each)
The cleanest option for simple iteration. Works with any Iterable:
List<String> names = List.of("Alice", "Bob", "Charlie");
for (String name : names) {
System.out.println(name);
}
Limitation: you cannot modify the collection while iterating (throws ConcurrentModificationException), and you cannot access the current index.
Iterator
Iterator gives explicit control. Use it when you need to safely remove elements during iteration:
List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Charlie", "Dave"));
Iterator<String> it = names.iterator();
while (it.hasNext()) {
String name = it.next();
if (name.startsWith("C")) {
it.remove(); // safe removal during iteration
}
}
System.out.println(names); // [Alice, Bob, Dave]
Never call list.remove() inside a for-each loop — it causes ConcurrentModificationException. Use iterator.remove() instead.
ListIterator
ListIterator extends Iterator with bidirectional traversal and the ability to add and set elements during iteration:
List<String> names = new ArrayList<>(List.of("alice", "bob", "charlie"));
ListIterator<String> lit = names.listIterator();
while (lit.hasNext()) {
String name = lit.next();
lit.set(name.substring(0, 1).toUpperCase() + name.substring(1)); // capitalize
}
System.out.println(names); // [Alice, Bob, Charlie]
forEach with lambda
The modern, functional-style iteration. Clean for simple operations:
List<String> names = List.of("Alice", "Bob", "Charlie");
names.forEach(name -> System.out.println(name));
// Or with a method reference
names.forEach(System.out::println);
// Map
Map<String, Integer> scores = Map.of("Alice", 95, "Bob", 82);
scores.forEach((name, score) -> System.out.println(name + ": " + score));
removeIf
Removes all elements matching a predicate — cleaner than using an iterator for filtering:
List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
numbers.removeIf(n -> n % 2 == 0); // remove all even numbers
System.out.println(numbers); // [1, 3, 5, 7, 9]
replaceAll
Replaces each element with the result of applying a function — cleaner than an indexed loop for transformations:
List<String> names = new ArrayList<>(List.of("alice", "bob", "charlie"));
names.replaceAll(String::toUpperCase);
System.out.println(names); // [ALICE, BOB, CHARLIE]
Utility Methods — Collections and List.of
Collections utility class
java.util.Collections provides static utility methods for working with collections:
import java.util.Collections;
List<Integer> numbers = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));
Collections.sort(numbers); // [1, 1, 2, 3, 4, 5, 6, 9]
Collections.reverse(numbers); // [9, 6, 5, 4, 3, 2, 1, 1]
Collections.shuffle(numbers); // random order
System.out.println(Collections.min(numbers)); // smallest element
System.out.println(Collections.max(numbers)); // largest element
System.out.println(Collections.frequency(numbers, 1)); // count occurrences of 1
Collections.sort(numbers);
int idx = Collections.binarySearch(numbers, 5); // index of 5 (list must be sorted)
Collections.fill(numbers, 0); // set all elements to 0
Collections.swap(numbers, 0, numbers.size() - 1); // swap first and last
// Unmodifiable view — wraps a modifiable list, throws on mutation attempts
List<Integer> immutable = Collections.unmodifiableList(numbers);
Factory methods — List.of, Set.of, Map.of (Java 9+)
Since Java 9, you can create immutable collections concisely:
// Immutable List — no add, remove, or set allowed
List<String> names = List.of("Alice", "Bob", "Charlie");
// Immutable Set
Set<String> tags = Set.of("java", "programming", "oop");
// Immutable Map
Map<String, Integer> codes = Map.of(
"Alice", 101,
"Bob", 102,
"Charlie", 103
);
// Map with more than 10 entries — use Map.ofEntries
Map<String, Integer> large = Map.ofEntries(
Map.entry("Alice", 101),
Map.entry("Bob", 102),
Map.entry("Charlie", 103),
Map.entry("Dave", 104)
// ... up to any number of entries
);
These factory-created collections are truly immutable — any attempt to add, remove, or modify throws UnsupportedOperationException. They are also slightly more memory-efficient than their mutable counterparts.
To create a mutable collection from an immutable one, wrap it:
List<String> mutable = new ArrayList<>(List.of("Alice", "Bob", "Charlie"));
mutable.add("Dave"); // fine — mutable copy
Choosing the Right Collection
The most important design skill with collections is picking the right one. Use this guide:
Do you need key-value pairs?
Yes → Use a Map:
- Order does not matter →
HashMap(fastest, O(1)) - Sorted by key →
TreeMap(O(log n)) - Insertion order →
LinkedHashMap(O(1))
No → Use a Collection:
Do you need unique elements?
Yes → Use a Set:
- Order does not matter →
HashSet(fastest, O(1)) - Sorted order →
TreeSet(O(log n)) - Insertion order →
LinkedHashSet(O(1))
No → Use a List:
- General purpose / random access →
ArrayList(almost always) - Frequent insert/delete at both ends →
LinkedList(as aDeque)
Quick decision table
| Need | Best choice |
|---|---|
| Ordered list with duplicates | ArrayList |
| Key → value lookup | HashMap |
| Unique elements, no order | HashSet |
| Unique elements, sorted | TreeSet |
| Sorted key → value | TreeMap |
| Queue (FIFO) | LinkedList as Queue / ArrayDeque |
| Stack (LIFO) | ArrayDeque (or LinkedList) |
| Insertion order, unique | LinkedHashSet |
| Insertion order, key-value | LinkedHashMap |
| Immutable list | List.of(...) |
| Immutable set | Set.of(...) |
| Immutable map | Map.of(...) |
A note on null
HashMap,HashSet,ArrayList,LinkedList,LinkedHashMap,LinkedHashSet— all allownullvalues (and onenullkey for maps/sets)TreeMapandTreeSet— do not allownull(the comparator would throwNullPointerException)List.of(),Set.of(),Map.of()— do not allownull(throwsNullPointerExceptionat creation)
Summary
- The Java Collections Framework provides
List,Set, andMapinterfaces with multiple implementations, each with different performance characteristics. - Program to the interface: declare variables as
List,Set, orMap, not asArrayList,HashSet, etc. ArrayListis a resizable array. O(1) random access, O(n) middle insert/delete. Use it by default for ordered sequences.LinkedListis a doubly linked list implementing bothListandDeque. O(1) at both ends, O(n) random access. Use it when you need a queue or deque.HashSetstores unique elements with no ordering, O(1) average.TreeSetstores them sorted, O(log n).LinkedHashSetpreserves insertion order.HashMapstores key-value pairs with no ordering, O(1) average.TreeMapstores them sorted by key.LinkedHashMappreserves insertion order.- Use
Iterator.remove()— neverlist.remove()— to remove elements during iteration. removeIf()andreplaceAll()are clean, modern alternatives to manual iteration for filtering and transformation.List.of(),Set.of(),Map.of()create immutable collections. Wrap them in a mutable constructor if you need to add elements.- The
Collectionsutility class providessort(),reverse(),shuffle(),min(),max(),frequency(),binarySearch(), and more.
Exercises
Exercise 1 — ArrayList word list Read the sentence "to be or not to be that is the question" and split it into words. Store the words in an ArrayList. Then: (a) sort alphabetically, (b) remove duplicates by converting to a LinkedHashSet and back, (c) find the longest word, (d) count how many words have more than 2 characters. Print results for each step.
Exercise 2 — HashSet duplicate detection Write a method List that returns a list of all values that appear more than once in the input. Use a HashSet to track seen values and a second HashSet to avoid reporting the same duplicate twice. Test with [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5].
Exercise 3 — Frequency map Write a program that takes the text "to be or not to be that is the question", builds a HashMap counting each word’s frequency, then: (a) prints all words and their counts sorted by frequency (most frequent first), (b) prints the top 3 most frequent words, (c) prints words that appear exactly once.
Exercise 4 — Phone book with TreeMap Implement a simple phone book using TreeMap (name → phone number). Provide methods: add(name, phone), lookup(name), delete(name), listAll() (prints entries in alphabetical order), and search(prefix) (returns all names starting with the given prefix — use TreeMap.subMap() or iterate). Demonstrate all operations in main.
Exercise 5 — Grouping and aggregation You have a list of transactions, each with a category (String) and amount (double). Model this as a simple class Transaction. Build a Map grouping transactions by category using computeIfAbsent. Then compute and print the total amount per category, sorted by total (highest first). Use the categories: "Food", "Transport", "Entertainment", "Utilities".
Exercise 6 — Inventory manager Build an InventoryManager class backed by a HashMap (product name → quantity). Implement: addStock(product, quantity), sellStock(product, quantity) (throws if insufficient stock), getQuantity(product), getLowStockItems(int threshold) returning a sorted list of products with quantity below the threshold, and printInventory() printing items in alphabetical order. Write a main that performs a sequence of operations and prints the inventory state after each.
Up next: Lecture 9 — Generics — where you will understand how Java’s type parameter system works under the hood, write your own generic classes and methods, and master wildcards to write flexible, reusable code.
