Sorting, choosing the right structure, and fail-fast iterators

Sorting with Comparable and Comparator

Comparable<T> is implemented by the element's own class to define its natural order:

public class Student implements Comparable<Student> {
    String name;
    int gpa;

    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.gpa, other.gpa); // ascending by GPA
    }
}

List<Student> roster = new ArrayList<>(...);
Collections.sort(roster);  // uses natural order

Comparator<T> is a separate strategy object used when you don't own the class, or need a different order:

// Sort students by name, then by GPA descending
Comparator<Student> byNameThenGpa =
    Comparator.comparing(Student::getName)
              .thenComparing(Comparator.comparingInt(Student::getGpa).reversed());

roster.sort(byNameThenGpa);
// or: Collections.sort(roster, byNameThenGpa);

Quick Big-O guide for choosing a collection

| Need | Best choice | Key reason | |---|---|---| | Fast index access | ArrayList | O(1) get | | Fast head/tail insert+remove | ArrayDeque | O(1) both ends | | Unique elements, fast lookup | HashSet | O(1) average | | Unique elements, sorted | TreeSet | O(log n), NavigableSet | | Key→value, fast lookup | HashMap | O(1) average | | Key→value, sorted keys | TreeMap | O(log n), NavigableMap | | Key→value, insertion order | LinkedHashMap | O(1), predictable |

Fail-fast iterators and ConcurrentModificationException

Most java.util collections use fail-fast iterators: they track a structural modification count (modCount). If the collection is modified while an iterator is active — other than through the iterator itself — the iterator throws ConcurrentModificationException:

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
    if (s.equals("b")) list.remove(s); // ConcurrentModificationException!
}

Safe removal patterns:

// Pattern 1: Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) it.remove(); // safe
}

// Pattern 2: removeIf (Java 8+, cleaner)
list.removeIf(s -> s.equals("b")); // internally uses iterator safely

Never call the collection's own add/remove while inside a for-each loop over it.