Collections — List, Set, Map

# Collections Framework

The hierarchy

Collection
├── List      ordered, duplicates allowed     → ArrayList, LinkedList
├── Set       unique elements                  → HashSet, LinkedHashSet, TreeSet
└── Queue     FIFO / priority                  → ArrayDeque, PriorityQueue
Map  (NOT a Collection)  key → value          → HashMap, LinkedHashMap, TreeMap

Always code to the interface

List<String> names = new ArrayList<>();   // good
Map<String,Integer> ages = new HashMap<>();

The diamond <> lets the compiler infer the type arguments (Java 7+).

ArrayList vs LinkedList

op	ArrayList	LinkedList
get(i)	O(1)	O(n)
add at end	amortised O(1)	O(1)
insert middle	O(n)	O(1) (with iterator)
memory	low	high (node per element)

Use ArrayList by default. LinkedList is rarely the right answer.

HashSet vs LinkedHashSet vs TreeSet

• HashSet — unordered, O(1) add/contains
• LinkedHashSet — *insertion* order preserved
• TreeSet — sorted (natural or by Comparator), O(log n)

HashMap vs LinkedHashMap vs TreeMap

Same trade-offs as the Set variants — HashMap is the default.

Iteration

for (String s : names) System.out.println(s);
for (var e : ages.entrySet())
    System.out.println(e.getKey() + " = " + e.getValue());
names.forEach(System.out::println);    // Java 8+

Immutable factories (Java 9+)

List<Integer>     a = List.of(1, 2, 3);
Set<String>       b = Set.of("x", "y");
Map<String,Integer> c = Map.of("a", 1, "b", 2);

These throw UnsupportedOperationException on add/put.

Collections utility class

Collections.sort(list);                 // natural order, in place
Collections.sort(list, Comparator.reverseOrder());
Collections.reverse(list);
Collections.shuffle(list);
int min = Collections.min(list);
int max = Collections.max(list);

Common map idioms

// frequency count
Map<String,Integer> freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum);
// default if missing
int v = freq.getOrDefault("xyz", 0);
// compute if absent
Map<String,List<Integer>> groups = new HashMap<>();
groups.computeIfAbsent("evens", k -> new ArrayList<>()).add(2);