1Z0-830 Collections - Java SE 21 Certification Prep

Collections Overview

Iterable
  |-- Collection
        |-- List (ordered, allows duplicates)
        |     |-- ArrayList
        |     |-- LinkedList
        |
        |-- Set (no duplicates)
        |     |-- HashSet
        |     |-- LinkedHashSet
        |     |-- TreeSet (sorted)
        |
        |-- Queue (FIFO)
              |-- LinkedList
              |-- PriorityQueue
              |-- Deque (double-ended)
                    |-- ArrayDeque
                    |-- LinkedList

• List: Ordered collection that allows duplicate elements. Elements can be accessed by their integer index.
• Set: Collection that does not allow duplicate elements. No ordering guarantees unless using LinkedHashSet or TreeSet.
• Queue: Collection designed for holding elements prior to processing. Typically FIFO but can vary (like PriorityQueue).
• Deque: Double-ended queue that allows element insertion and removal at both ends.
• Map: Not part of Collection interface but critical. Stores key-value pairs with unique keys.

// Creating collections
List<String> list = new ArrayList<>();
Set<Integer> set = new HashSet<>();
Map<String, Integer> map = new HashMap<>();
Queue<String> queue = new LinkedList<>();
Deque<String> deque = new ArrayDeque<>();

// Factory methods (immutable collections) - Java 9+
List<String> immutableList = List.of("a", "b", "c");
Set<Integer> immutableSet = Set.of(1, 2, 3);
Map<String, Integer> immutableMap = Map.of("a", 1, "b", 2);

// Factory methods rules - Important for exam:
// - Return immutable collections (cannot be modified)
// - Do not allow null values
// - Set.of() and Map.of() keys do not allow duplicates
immutableList.add("d");  // Throws UnsupportedOperationException
List.of(null);           // Throws NullPointerException
Set.of(1, 1);            // Throws IllegalArgumentException (duplicate)

List Interface

// List - ordered collection with duplicates allowed
List<String> list = new ArrayList<>();

// Adding elements
list.add("apple");           // Appends to end, returns true
list.add(0, "banana");       // Inserts at specific index
list.addAll(otherList);      // Adds all elements from another collection

// Accessing elements
String first = list.get(0);              // Retrieves element at index
int index = list.indexOf("apple");       // Index of first occurrence (-1 if not found)
int last = list.lastIndexOf("apple");    // Index of last occurrence

// Modifying elements
list.set(0, "cherry");       // Replaces element at index, returns old value
list.remove(0);              // Removes by index, returns removed element
list.remove("apple");        // Removes first occurrence by value, returns boolean
list.clear();                // Removes all elements

// Checking state
boolean has = list.contains("apple");    // Returns true if element exists
boolean empty = list.isEmpty();          // Returns true if no elements
int size = list.size();                  // Returns number of elements

// Sublist - creates a view, not a copy
List<String> sub = list.subList(1, 3);  // From index 1 (inclusive) to 3 (exclusive)
sub.clear();  // WARNING: This also clears elements from original list!

// ArrayList vs LinkedList performance characteristics
// ArrayList: 
//   - Fast random access: O(1) for get(index)
//   - Slow insertions/deletions in middle: O(n)
//   - Best for: frequent access, infrequent modifications
// LinkedList: 
//   - Slow random access: O(n) for get(index)
//   - Fast insertions/deletions at ends: O(1)
//   - Best for: frequent insertions/deletions, queue operations

// Sorting
Collections.sort(list);                            // Natural order (ascending)
Collections.sort(list, Comparator.reverseOrder()); // Reverse order
list.sort(Comparator.naturalOrder());              // Instance method (Java 8+)
list.sort(Comparator.comparing(String::length));   // Custom comparator

Set Interface

// Set - collection with no duplicates allowed
Set<String> set = new HashSet<>();
set.add("apple");
set.add("apple");  // Returns false, element not added again
set.size();        // Returns 1 (not 2)

// HashSet - no ordering guarantees, fastest performance
// Best for: membership testing, eliminating duplicates
// Time complexity: O(1) for add, remove, contains
Set<String> hashSet = new HashSet<>();
hashSet.add("c");
hashSet.add("a");
hashSet.add("b");
// Iteration order is unpredictable

// LinkedHashSet - maintains insertion order
// Best for: when you need predictable iteration order
// Time complexity: O(1) for add, remove, contains (slightly slower than HashSet)
Set<String> linkedSet = new LinkedHashSet<>();
linkedSet.add("c");
linkedSet.add("a");
linkedSet.add("b");
// Iteration order: c, a, b (insertion order)

// TreeSet - maintains sorted order
// Best for: sorted sets, range operations
// Time complexity: O(log n) for add, remove, contains
Set<String> treeSet = new TreeSet<>();
treeSet.addAll(List.of("c", "a", "b"));
// Iteration order: a, b, c (natural sorted order)

// TreeSet requires elements to be Comparable or provide a Comparator
// This will throw ClassCastException if Person is not Comparable:
// Set<Person> people = new TreeSet<>();

// Correct way - provide Comparator:
TreeSet<Person> people = new TreeSet<>(
    Comparator.comparing(Person::getName)
);

// TreeSet navigation methods (exam favorite)
TreeSet<Integer> nums = new TreeSet<>(List.of(1, 3, 5, 7, 9));

nums.first();           // Returns 1 (smallest element)
nums.last();            // Returns 9 (largest element)
nums.higher(5);         // Returns 7 (strictly greater than 5)
nums.lower(5);          // Returns 3 (strictly less than 5)
nums.ceiling(4);        // Returns 5 (greater than or equal to 4)
nums.floor(4);          // Returns 3 (less than or equal to 4)

nums.headSet(5);        // Returns [1, 3] (elements less than 5)
nums.tailSet(5);        // Returns [5, 7, 9] (elements >= 5)
nums.subSet(3, 7);      // Returns [3, 5] (from 3 inclusive to 7 exclusive)

// Additional useful methods
nums.pollFirst();       // Removes and returns 1
nums.pollLast();        // Removes and returns 9

Map Interface

// Map - stores key-value pairs with unique keys
Map<String, Integer> map = new HashMap<>();

// Adding and updating entries
map.put("apple", 1);         // Adds or updates, returns previous value (or null)
map.putIfAbsent("apple", 2); // Only adds if key is not present, returns current value
map.putAll(otherMap);        // Adds all entries from another map

// Retrieving values
Integer value = map.get("apple");           // Returns value or null if key not found
Integer safe = map.getOrDefault("pear", 0); // Returns default if key not found

// Checking for keys and values
boolean hasKey = map.containsKey("apple");     // Returns true if key exists
boolean hasValue = map.containsValue(1);       // Returns true if value exists (slow O(n))
boolean empty = map.isEmpty();                 // Returns true if no entries
int size = map.size();                         // Returns number of entries

// Removing entries
Integer removed = map.remove("apple");      // Removes by key, returns value
boolean success = map.remove("apple", 1);   // Removes only if value matches, returns boolean

// View collections (backed by the map)
Set<String> keys = map.keySet();                      // Set of all keys
Collection<Integer> values = map.values();            // Collection of all values
Set<Map.Entry<String, Integer>> entries = map.entrySet(); // Set of key-value pairs

// Iterating through entries
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + " = " + value);
}

// Lambda-based iteration (Java 8+)
map.forEach((key, value) -> System.out.println(key + " = " + value));

// Compute methods (exam favorite)
// compute() - computes value for specified key
map.compute("apple", (k, v) -> v == null ? 1 : v + 1);

// computeIfAbsent() - computes value only if key is absent
map.computeIfAbsent("pear", k -> 1);

// computeIfPresent() - computes value only if key is present
map.computeIfPresent("apple", (k, v) -> v + 1);

// merge() - combines existing value with new value using function
map.merge("apple", 1, Integer::sum);  // Adds 1 to existing value

// Map implementations comparison
// HashMap: No ordering guarantees, O(1) operations
//   - Best for: general-purpose use, fastest performance
// LinkedHashMap: Maintains insertion order, O(1) operations
//   - Best for: when iteration order matters, LRU caches
// TreeMap: Maintains sorted order by keys, O(log n) operations
//   - Best for: sorted keys, range operations

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("c", 3);
treeMap.put("a", 1);
treeMap.put("b", 2);
// Iteration order: a=1, b=2, c=3 (sorted by keys)

Queue and Deque

// Queue - FIFO (First In First Out) collection
Queue<String> queue = new LinkedList<>();

// Queue operations come in two forms:
// Operations that throw exceptions vs return special values
//
// Throws Exception    |  Returns Special Value  |  Operation
// --------------------|-------------------------|------------------
// add(e)              |  offer(e)               |  Insert element
// remove()            |  poll()                 |  Remove and return head
// element()           |  peek()                 |  Return head without removing

queue.offer("first");     // Adds element, returns true if successful
queue.offer("second");
String head = queue.poll();   // Removes and returns "first" (null if empty)
String peek = queue.peek();   // Returns "second" without removing (null if empty)

// add() vs offer(): add() throws exception if queue is full, offer() returns false
// remove() vs poll(): remove() throws exception if empty, poll() returns null
// element() vs peek(): element() throws exception if empty, peek() returns null

// PriorityQueue - elements ordered by natural ordering or Comparator
Queue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5, 1, 3, 2, 4));
pq.poll();  // Returns 1 (smallest element first)
pq.poll();  // Returns 2
pq.poll();  // Returns 3
// Elements are not fully sorted, but smallest is always at head

// Custom comparator for PriorityQueue
Queue<String> byLength = new PriorityQueue<>(
    Comparator.comparing(String::length)
);
byLength.addAll(List.of("apple", "pie", "a", "banana"));
byLength.poll();  // Returns "a" (shortest)
byLength.poll();  // Returns "pie" (next shortest)

// Deque - double-ended queue (can function as stack or queue)
Deque<String> deque = new ArrayDeque<>();

// Using Deque as Queue (FIFO)
deque.offerLast("first");   // Add to back
deque.offerLast("second");
deque.pollFirst();          // Remove from front - returns "first"

// Using Deque as Stack (LIFO - Last In First Out)
deque.push("first");   // Equivalent to addFirst()
deque.push("second");  // Now at front
deque.pop();           // Returns "second" - equivalent to removeFirst()
deque.peek();          // Returns "first" - equivalent to peekFirst()

// Complete Deque method reference:
// First element (head):
deque.addFirst(e);     // Throws exception if capacity restricted
deque.offerFirst(e);   // Returns false if capacity restricted
deque.removeFirst();   // Throws exception if empty
deque.pollFirst();     // Returns null if empty
deque.getFirst();      // Throws exception if empty
deque.peekFirst();     // Returns null if empty

// Last element (tail):
deque.addLast(e);      // Throws exception if capacity restricted
deque.offerLast(e);    // Returns false if capacity restricted
deque.removeLast();    // Throws exception if empty
deque.pollLast();      // Returns null if empty
deque.getLast();       // Throws exception if empty
deque.peekLast();      // Returns null if empty

Sequenced Collections (Java 21)

// New interfaces in Java 21:
// - SequencedCollection extends Collection
// - SequencedSet extends SequencedCollection and Set
// - SequencedMap (separate hierarchy)

// These interfaces provide consistent methods for accessing both ends
// and for creating reversed views.

// SequencedCollection methods
List<String> list = new ArrayList<>(List.of("a", "b", "c"));

list.addFirst("first");      // Adds at beginning - result: [first, a, b, c]
list.addLast("last");        // Adds at end - result: [first, a, b, c, last]

String first = list.getFirst();      // Returns "first" (throws if empty)
String last = list.getLast();        // Returns "last" (throws if empty)

list.removeFirst();          // Removes and returns "first"
list.removeLast();           // Removes and returns "last"

SequencedCollection<String> reversed = list.reversed();
// Returns reversed view: changes to reversed affect original and vice versa

// SequencedSet - available for LinkedHashSet and TreeSet
SequencedSet<String> set = new LinkedHashSet<>();
set.addAll(List.of("a", "b", "c"));

set.getFirst();              // Returns "a" (first in insertion order)
set.getLast();               // Returns "c" (last in insertion order)

SequencedSet<String> reversedSet = set.reversed();
// Returns reversed view maintaining set semantics

// Important: Regular HashSet does NOT implement SequencedSet
// because it has no defined ordering

// SequencedMap - available for LinkedHashMap and TreeMap
SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);

// Access first and last entries
Map.Entry<String, Integer> firstEntry = map.firstEntry();  // Returns a=1
Map.Entry<String, Integer> lastEntry = map.lastEntry();    // Returns c=3

// Remove and return first/last entries
Map.Entry<String, Integer> removed = map.pollFirstEntry(); // Removes and returns a=1
Map.Entry<String, Integer> removed2 = map.pollLastEntry(); // Removes and returns c=3

// Add at first or last position
map.putFirst("first", 0);    // Adds at beginning of insertion order
map.putLast("last", 4);      // Adds at end of insertion order

// Get reversed view of map
SequencedMap<String, Integer> reversedMap = map.reversed();
// Iteration over reversed map goes in reverse order

// Sequenced collections also provide reversed views of keySet(), values(), entrySet()
SequencedSet<String> reversedKeys = reversedMap.sequencedKeySet();
SequencedCollection<Integer> reversedValues = reversedMap.sequencedValues();
SequencedSet<Map.Entry<String, Integer>> reversedEntries = reversedMap.sequencedEntrySet();

Collection Utilities

// Collections utility class - all methods are static
List<Integer> list = new ArrayList<>(List.of(3, 1, 4, 1, 5));

// Sorting and ordering
Collections.sort(list);                  // Sorts in ascending order: [1, 1, 3, 4, 5]
Collections.reverse(list);               // Reverses order: [5, 4, 3, 1, 1]
Collections.shuffle(list);               // Randomizes order

// Element manipulation
Collections.swap(list, 0, 1);            // Swaps elements at indices 0 and 1
Collections.rotate(list, 2);             // Rotates elements right by 2 positions
Collections.fill(list, 0);               // Replaces all elements with 0

// Copy requires destination list to be at least as large as source
List<Integer> dest = new ArrayList<>(Arrays.asList(new Integer[5]));
Collections.copy(dest, list);            // Copies elements from list to dest

// Searching and frequency
Collections.sort(list);                  // Must be sorted before binary search
int index = Collections.binarySearch(list, 3);  // Returns index or negative insertion point
int count = Collections.frequency(list, 1);     // Counts occurrences of 1

// Min and max
Integer min = Collections.min(list);             // Finds minimum element
Integer max = Collections.max(list);             // Finds maximum element
Integer minCustom = Collections.min(list, Comparator.reverseOrder());  // With custom comparator

// Unmodifiable wrappers - creates read-only view
List<String> mutable = new ArrayList<>(List.of("a", "b", "c"));
List<String> unmodifiable = Collections.unmodifiableList(mutable);
unmodifiable.add("d");  // Throws UnsupportedOperationException
mutable.add("d");       // Original list can still be modified
// Now unmodifiable also contains "d" because it is just a view

// All collection types have unmodifiable wrappers:
Collections.unmodifiableList(list);
Collections.unmodifiableSet(set);
Collections.unmodifiableMap(map);
Collections.unmodifiableCollection(collection);

// Thread-safe wrappers - makes collection thread-safe with synchronized methods
List<String> syncList = Collections.synchronizedList(list);
Set<String> syncSet = Collections.synchronizedSet(set);
Map<String, Integer> syncMap = Collections.synchronizedMap(map);

// Note: You still need to manually synchronize iteration over synchronized collections
synchronized(syncList) {
    for(String s : syncList) {
        // Process element
    }
}

// Singleton collections - immutable single-element collection
List<String> single = Collections.singletonList("only");     // Immutable list with one element
Set<String> singleSet = Collections.singleton("only");       // Immutable set with one element
Map<String, Integer> singleMap = Collections.singletonMap("key", 1);  // Immutable map with one entry

// Empty collections - immutable empty collections
List<String> empty = Collections.emptyList();
Set<String> emptySet = Collections.emptySet();
Map<String, Integer> emptyMap = Collections.emptyMap();

// Checked collections - provides runtime type safety
List<String> checked = Collections.checkedList(list, String.class);
// Prevents ClassCastException by checking type at runtime

// Converting array to list
String[] arr = {"a", "b", "c"};
List<String> asList = Arrays.asList(arr);  // Fixed-size list backed by array
// WARNING: Cannot add or remove elements, but can modify existing ones
asList.set(0, "x");  // OK - modifies array too
asList.add("d");     // Throws UnsupportedOperationException

// To get a mutable list from array:
List<String> mutableList = new ArrayList<>(Arrays.asList(arr));

// Converting list to array
List<String> strList = List.of("a", "b", "c");
String[] back = strList.toArray(new String[0]);      // Using sized array
String[] back2 = strList.toArray(String[]::new);     // Using array generator (Java 11+)

// Disjoint - checks if two collections have no common elements
boolean noCommon = Collections.disjoint(list1, list2);  // Returns true if no overlap

// AddAll - adds multiple elements to collection
Collections.addAll(list, "a", "b", "c");  // More efficient than multiple add() calls