Collections Framework

1import java.util.*;
2
3// ArrayList: backed by a resizable array
4// O(1) amortized add to end, O(1) get by index, O(n) insert/remove at middle
5List<String> arrayList = new ArrayList<>();
6arrayList.add("Alice");     // O(1) amortized
7arrayList.add("Bob");
8arrayList.add(0, "Admin"); // O(n) — shifts all elements
9System.out.println(arrayList.get(1));  // O(1) — "Alice"
10
11// Pre-allocate when size is known (avoids resizing)
12List<Integer> preallocated = new ArrayList<>(10_000);
13
14// LinkedList: doubly-linked list
15// O(1) insert/remove at head/tail, O(n) get by index
16List<String> linkedList = new LinkedList<>();
17linkedList.add("Alice");
18linkedList.add(0, "First");  // O(1) at head — vs O(n) for ArrayList
19System.out.println(linkedList.get(1)); // O(n) traversal — vs O(1) for ArrayList
20
21// Decision guide:
22// ArrayList: random access, read-heavy, append-heavy
23// LinkedList: frequent head/tail inserts, queue/deque usage
24
25// Immutable lists (Java 9+) — cannot add, remove, or set
26List<String> immutable = List.of("Alice", "Bob", "Charlie");
27// immutable.add("Dave");  // UnsupportedOperationException
28
29// Mutable copy of immutable
30List<String> mutable = new ArrayList<>(immutable);
31mutable.add("Dave");  // OK
32
33// Common List operations
34List<Integer> numbers = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));
35Collections.sort(numbers);         // [1, 1, 2, 3, 4, 5, 6, 9]
36numbers.sort(Comparator.reverseOrder()); // [9, 6, 5, 4, 3, 2, 1, 1]
37numbers.remove(Integer.valueOf(1)); // removes FIRST occurrence of value 1
38numbers.removeIf(n -> n % 2 == 0); // removes all even numbers
39System.out.println(Collections.frequency(numbers, 1)); // count of 1s
40int idx = Collections.binarySearch(numbers, 5);        // index of 5 (sorted required)

1// HashMap: O(1) get/put/remove, NO ordering guarantee
2Map<String, Integer> scores = new HashMap<>();
3scores.put("Alice", 95);
4scores.put("Bob",   78);
5scores.put("Charlie", 88);
6
7// Reading values
8System.out.println(scores.get("Alice"));      // 95
9System.out.println(scores.get("Diana"));      // null (not found)
10System.out.println(scores.getOrDefault("Diana", 0)); // 0 (safe default)
11System.out.println(scores.containsKey("Bob")); // true
12System.out.println(scores.size());             // 3
13
14// Iteration
15for (Map.Entry<String, Integer> entry : scores.entrySet()) {
16    System.out.printf("%s: %d%n", entry.getKey(), entry.getValue());
17}
18scores.forEach((name, score) -> System.out.printf("%s: %d%n", name, score));
19
20// Computed updates (thread-safe-ish for single-threaded code)
21scores.compute("Alice", (k, v) -> v == null ? 1 : v + 1); // increment or init
22scores.computeIfAbsent("Diana", k -> 0); // only if key absent
23scores.merge("Bob", 5, Integer::sum);    // add 5 to existing, or put 5 if absent
24
25// LinkedHashMap: insertion-ordered, O(1) operations
26Map<String, Integer> ordered = new LinkedHashMap<>();
27ordered.put("Charlie", 88);
28ordered.put("Alice", 95);
29ordered.put("Bob", 78);
30ordered.keySet().forEach(System.out::println); // Charlie, Alice, Bob (insertion order)
31
32// LRU cache using LinkedHashMap (access-order mode)
33Map<Integer, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
34    @Override protected boolean removeEldestEntry(Map.Entry<Integer,String> eldest) {
35        return size() > 100;  // evict when over 100 entries
36    }
37};
38
39// TreeMap: sorted by key, O(log n) operations
40Map<String, Integer> sorted = new TreeMap<>(scores);
41sorted.keySet().forEach(System.out::println); // Alice, Bob, Charlie (alphabetical)
42
43TreeMap<Integer, String> calendar = new TreeMap<>();
44calendar.put(3, "March");
45calendar.put(1, "January");
46calendar.put(12, "December");
47System.out.println(calendar.firstKey());  // 1
48System.out.println(calendar.lastKey());   // 12
49System.out.println(calendar.headMap(7));  // {1=January, 3=March}
50
51// Immutable map (Java 9+)
52Map<String, Integer> config = Map.of(
53    "timeout", 30,
54    "maxRetries", 3,
55    "pageSize", 20
56);

1// HashSet: O(1) add/remove/contains, NO ordering
2Set<String> cities = new HashSet<>();
3cities.add("London");
4cities.add("Paris");
5cities.add("London");  // duplicate — ignored
6System.out.println(cities.size());           // 2
7System.out.println(cities.contains("Paris")); // true
8
9// Set operations (mathematical)
10Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4, 5));
11Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6, 7));
12
13Set<Integer> union = new HashSet<>(a); union.addAll(b); // {1,2,3,4,5,6,7}
14Set<Integer> intersection = new HashSet<>(a); intersection.retainAll(b); // {3,4,5}
15Set<Integer> difference  = new HashSet<>(a); difference.removeAll(b);   // {1,2}
16
17// Removing duplicates from a list — preserve order with LinkedHashSet
18List<String> withDups = List.of("apple", "banana", "apple", "cherry", "banana");
19List<String> unique   = new ArrayList<>(new LinkedHashSet<>(withDups));
20System.out.println(unique); // [apple, banana, cherry] — order preserved!
21
22// TreeSet: sorted, O(log n) operations
23TreeSet<Integer> scores = new TreeSet<>(Set.of(85, 92, 78, 95, 88));
24System.out.println(scores);            // [78, 85, 88, 92, 95] sorted
25System.out.println(scores.first());    // 78
26System.out.println(scores.last());     // 95
27System.out.println(scores.headSet(90)); // [78, 85, 88] — less than 90
28System.out.println(scores.tailSet(88)); // [88, 92, 95] — >= 88
29
30// TreeSet with custom Comparator (case-insensitive)
31TreeSet<String> names = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
32names.add("Bob");
33names.add("alice");
34names.add("CHARLIE");
35System.out.println(names); // [alice, Bob, CHARLIE]

1// ArrayDeque: efficient double-ended queue
2// Use instead of Stack (deprecated) and instead of LinkedList for queue
3Deque<String> queue = new ArrayDeque<>();
4
5// Queue operations (FIFO: First In, First Out)
6queue.offer("first");   // add to tail (returns false if full)
7queue.offer("second");
8queue.offer("third");
9
10System.out.println(queue.peek());   // "first" — see head without removing
11System.out.println(queue.poll());   // "first" — remove and return head
12System.out.println(queue.size());   // 2
13
14// Stack operations (LIFO: Last In, First Out)
15Deque<String> stack = new ArrayDeque<>();
16stack.push("bottom");    // push to head
17stack.push("middle");
18stack.push("top");
19
20System.out.println(stack.peek());   // "top" — see top without removing
21System.out.println(stack.pop());    // "top" — remove and return top
22
23// Priority Queue: elements dequeued by priority (natural ordering or comparator)
24Queue<Integer> pq = new PriorityQueue<>();
25pq.offer(5);
26pq.offer(1);
27pq.offer(3);
28System.out.println(pq.poll()); // 1 — smallest first (min-heap)
29System.out.println(pq.poll()); // 3
30System.out.println(pq.poll()); // 5
31
32// Max-heap: reverse natural ordering
33Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
34maxHeap.addAll(List.of(5, 1, 3));
35System.out.println(maxHeap.poll()); // 5 — largest first
36
37// Task scheduling example
38record Task(int priority, String name) implements Comparable<Task> {
39    @Override
40    public int compareTo(Task other) {
41        return Integer.compare(this.priority, other.priority);
42    }
43}
44
45Queue<Task> tasks = new PriorityQueue<>();
46tasks.offer(new Task(3, "Low priority report"));
47tasks.offer(new Task(1, "Critical: payment failure"));
48tasks.offer(new Task(2, "Send welcome email"));
49
50while (!tasks.isEmpty()) {
51    Task t = tasks.poll();
52    System.out.println("Processing: " + t.name() + " (priority " + t.priority() + ")");
53}
54// Critical: payment failure (1)
55// Send welcome email (2)
56// Low priority report (3)

1import java.util.Collections;
2
3List<Integer> nums = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));
4
5// Sorting
6Collections.sort(nums);                            // natural order
7Collections.sort(nums, Comparator.reverseOrder()); // reverse
8nums.sort(Comparator.naturalOrder());              // List method (Java 8+)
9
10// Searching (requires sorted list)
11Collections.sort(nums);
12int idx = Collections.binarySearch(nums, 5);  // index >= 0 if found
13
14// Min/Max
15System.out.println(Collections.min(nums)); // smallest element
16System.out.println(Collections.max(nums)); // largest element
17
18// Shuffle and reverse
19Collections.shuffle(nums);   // randomize order
20Collections.reverse(nums);   // reverse in place
21
22// Fill and copy
23List<String> filled = new ArrayList<>(Collections.nCopies(5, "x")); // [x,x,x,x,x]
24List<Integer> dest = new ArrayList<>(nums);  // same size
25Collections.copy(dest, nums);  // copy src into dest
26
27// Frequency and disjoint
28System.out.println(Collections.frequency(nums, 1)); // how many times 1 appears
29System.out.println(Collections.disjoint(Set.of(1, 2), Set.of(3, 4))); // true (no overlap)
30
31// Unmodifiable wrappers — safe to expose publicly
32List<String> mutableList = new ArrayList<>(List.of("a", "b", "c"));
33List<String> readOnly    = Collections.unmodifiableList(mutableList);
34// readOnly.add("d");  // UnsupportedOperationException
35
36// BETTER: use List.copyOf() for true snapshot
37List<String> snapshot = List.copyOf(mutableList);  // changes to mutableList not reflected
38
39// Singleton collections
40List<String>  singleList = Collections.singletonList("only");
41Set<String>   singleSet  = Collections.singleton("only");
42Map<String,Integer> singleMap = Collections.singletonMap("one", 1);
43
44// Thread-safe wrappers (for legacy code — prefer ConcurrentHashMap in new code)
45Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());