Collections Framework

### LinkedHashMap

`LinkedHashMap<K,V>` extends `HashMap` and maintains a doubly-linked list that runs through all its
Entries. This linked list defines the iteration order, which is **insertion order by default** or
**access order** (least-recently-used to most-recently-used) if constructed with
`accessOrder = true`.

```java
// Insertion-ordered LinkedHashMap
Map<String, Integer> insertionOrder = new LinkedHashMap<>();
insertionOrder.put("C", 3);
insertionOrder.put("A", 1);
insertionOrder.put("B", 2);
System.out.println(insertionOrder.keySet());  // [C, A, B] -- insertion order

// Access-ordered LinkedHashMap (LRU cache basis)
Map<String, Integer> lruOrder = new LinkedHashMap<>(16, 0.75f, true);
lruOrder.put("C", 3);
lruOrder.put("A", 1);
lruOrder.put("B", 2);
lruOrder.get("C");  // accessing C moves it to the end
System.out.println(lruOrder.keySet());  // [A, B, C] -- access order (C moved to end)

// Simple LRU cache built on LinkedHashMap
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxEntries;

    public LRUCache(int maxEntries) {
        super(maxEntries, 0.75f, true);  // accessOrder = true
        this.maxEntries = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxEntries;
    }
}

// Basic usage -- thread-safe without external synchronization
ConcurrentHashMap<String, AtomicInteger> counts = new ConcurrentHashMap<>();

// Atomic compound operations (not possible with synchronizedMap)
counts.computeIfAbsent("key", k -> new AtomicInteger(0));
counts.computeIfPresent("key", (k, v) -> { v.incrementAndGet(); return v; });

// putIfAbsent is atomic -- avoids the check-then-act race condition
counts.putIfAbsent("key", new AtomicInteger(0));  // atomic

// The following is NOT atomic with synchronizedMap -- a race condition exists:
// if (!map.containsKey("key")) { map.put("key", value); }  // WRONG in concurrent code

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Charlie"));
Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String name = it.next();
    if (name.startsWith("B")) {
        it.remove();  // safe -- uses Iterator.remove(), not List.remove()
    }
}
// names is now [Alice, Charlie]

public interface ListIterator<E> extends Iterator<E> {
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void set(E e);       // replaces the last element returned by next() or previous()
    void add(E e);       // inserts element before the implicit cursor
}

List<String> list = new ArrayList<>(List.of("A", "B", "C", "D"));
ListIterator<String> it = list.listIterator(2);  // cursor starts at index 2 (before "C")

it.next();     // "C" -- cursor now at 3
it.set("X");   // replaces "C" with "X" -- list is now [A, B, X, D]
it.previous(); // "X" -- cursor back at 2
it.add("Y");   // inserts "Y" before cursor -- list is now [A, B, Y, X, D]

// Simplified ArrayList.Itr
private class Itr implements Iterator<E> {
    int expectedModCount = modCount;  // captured at iterator creation

    public E next() {
        checkForComodification();     // throws CME if modCount changed
        // ...
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("A", 1);
map.put("B", 2);

Iterator<String> it = map.keySet().iterator();
while (it.hasNext()) {
    String key = it.next();
    map.put("C", 3);  // modifying the map during iteration -- NO exception
}

Collection<String> sync = Collections.synchronizedCollection(list);
synchronized (sync) {  // must synchronize manually during iteration
    for (String s : sync) {
        if (s.startsWith("A")) {
            sync.remove(s);
        }
    }
}

public interface Comparable<T> {
    int compareTo(T o);
    // Returns negative if this < o, zero if this == o, positive if this > o
}

public record Person(String name, int age) implements Comparable<Person> {
    @Override
    public int compareTo(Person other) {
        int cmp = this.name.compareTo(other.name);
        return cmp != 0 ? cmp : Integer.compare(this.age, other.age);
    }
}

List<Person> people = List.of(
    new Person("Charlie", 30),
    new Person("Alice", 25),
    new Person("Bob", 30)
);
people.stream().sorted().forEach(System.out::println);
// Alice(25), Bob(30), Charlie(30) -- sorted by name, then age

public interface Comparator<T> {
    int compare(T o1, T o2);
    boolean equals(Object obj);

    // Comparator has many useful default methods (Java 8+)
    default Comparator<T> reversed();
    default Comparator<T> thenComparing(Comparator<? super T> other);
    default <U> Comparator<T> thenComparing(Function<? super T, ? extends U> keyExtractor,
                                             Comparator<? super U> keyComparator);
    static <T extends Comparable<? super T>> Comparator<T> naturalOrder();
    static <T> Comparator<T> reverseOrder();
    static <T> Comparator<T> nullsFirst(Comparator<? super T> comparator);
    static <T> Comparator<T> nullsLast(Comparator<? super T> comparator);
}

// Chained comparators using default methods
Comparator<Person> byName = Comparator.comparing(Person::name);
Comparator<Person> byAge = Comparator.comparing(Person::age);
Comparator<Person> byNameThenAge = byName.thenComparing(byAge);

Comparator<Person> byAgeDesc = Comparator.comparing(Person::age).reversed();

// Null-safe comparators
Comparator<String> nullSafe = Comparator.nullsFirst(Comparator.naturalOrder());
List<String> mixed = List.of("Charlie", null, "Alice");
mixed.stream().sorted(nullSafe).forEach(System.out::println);
// null, Alice, Charlie -- null comes first

List<Integer> numbers = new ArrayList<>(List.of(5, 3, 1, 4, 2));

Collections.sort(numbers);                  // natural ordering: [1, 2, 3, 4, 5]
Collections.sort(numbers, Comparator.reverseOrder());  // [5, 4, 3, 2, 1]

// binarySearch requires the list to be SORTED; returns the index if found,
// or (-(insertion point) - 1) if not found
int index = Collections.binarySearch(numbers, 3);  // 2
int notFound = Collections.binarySearch(numbers, 6);  // negative value

// binarySearch with a Comparator must use the SAME Comparator used for sorting
Collections.sort(numbers, Comparator.naturalOrder());
Collections.binarySearch(numbers, 3, Comparator.naturalOrder());

List<String> mutable = new ArrayList<>(List.of("A", "B", "C"));
List<String> unmodifiable = Collections.unmodifiableList(mutable);

unmodifiable.add("D");  // UnsupportedOperationException

// WARNING: the unmodifiable wrapper is a VIEW -- changes to the backing list are visible
mutable.add("D");
System.out.println(unmodifiable);  // [A, B, C, D] -- the wrapper reflects the change

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

// Each individual operation is thread-safe
syncList.add("hello");  // synchronized internally

// BUT iteration requires manual synchronization
synchronized (syncList) {
    for (String s : syncList) {
        System.out.println(s);
    }
}

// Reversing and rotating
Collections.reverse(list);
Collections.rotate(list, 2);  // rotate right by 2 positions

// Shuffling (uses ThreadLocalRandom internally)
Collections.shuffle(list);

// Frequency and disjoint
int count = Collections.frequency(list, "target");
boolean noOverlap = Collections.disjoint(list1, list2);

// Singleton and empty collections
Set<String> single = Collections.singleton("only");
List<String> empty = Collections.emptyList();
Map<String, Integer> emptyMap = Collections.emptyMap();

// min/max
int max = Collections.max(numbers);
int min = Collections.min(numbers, Comparator.reverseOrder());

// addAll
Collections.addAll(list, "D", "E", "F");

int[] numbers = {5, 3, 1, 4, 2};
Arrays.sort(numbers);                            // [1, 2, 3, 4, 5]
int index = Arrays.binarySearch(numbers, 3);     // 2

// Parallel sort -- uses ForkJoinPool for large arrays
int[] large = new int[1_000_000];
Arrays.fill(large, 0);
Arrays.parallelSort(large);

// Array to List
String[] words = {"hello", "world"};
List<String> list = Arrays.asList(words);
// WARNING: Arrays.asList returns a fixed-size LIST BACKED BY THE ARRAY
// list.add("new") throws UnsupportedOperationException
// But: list.set(0, "hi") modifies the original array

// Safe copy
List<String> copy = new ArrayList<>(Arrays.asList(words));

// fill and equals
Arrays.fill(numbers, 0);
boolean same = Arrays.equals(arr1, arr2);  // deep element-by-element comparison
boolean deepSame = Arrays.deepEquals(matrix1, matrix2);  // for nested arrays

// toString for debugging
System.out.println(Arrays.toString(numbers));     // [1, 2, 3, 4, 5]
System.out.println(Arrays.deepToString(matrix));   // [[1, 2], [3, 4]]

// List.of -- up to 10 elements have dedicated overloads for performance
List<String> empty = List.of();
List<String> one = List.of("A");
List<String> three = List.of("A", "B", "C");
List<String> fromArray = List.of("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K");

// Set.of -- duplicates throw IllegalArgumentException
Set<String> unique = Set.of("A", "B", "C");
// Set.of("A", "A");  // IllegalArgumentException: duplicate element: A

// Map.of -- duplicate keys throw IllegalArgumentException
Map<String, Integer> map = Map.of("A", 1, "B", 2, "C", 3);
Map<String, Integer> fromEntries = Map.ofEntries(
    Map.entry("A", 1),
    Map.entry("B", 2),
    Map.entry("C", 3)
);

// HashMap places null keys at bucket index 0 (since hash(null) = 0)
static final int hash(Object key) {
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// The null key is stored in bucket[0] and compared with ==
// (not .equals()) since null.equals() would throw NPE
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

// TreeSet with natural ordering -- null is not allowed
Set<String> treeSet = new TreeSet<>();
// treeSet.add(null);  // NullPointerException: cannot compare null

// TreeSet with a null-safe Comparator -- null IS allowed
Set<String> nullSafeTree = new TreeSet<>(Comparator.nullsFirst(Comparator.naturalOrder()));
nullSafeTree.add(null);
nullSafeTree.add("Alice");
System.out.println(nullSafeTree);  // [null, Alice]