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

Comparable vs Comparator, chained comparators, a Big-O cheat-sheet, and the ConcurrentModificationException trap.

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.

The iterator saved the modification count when the loop began; calling list.remove bumps that count without telling the iterator, and the very next next() notices. Iterator.remove and removeIf update both counts together, which is why they are safe.