Collections and Streams in Java

import java.util.ArrayList;
import java.util.List;

// Empty list
ArrayList<Integer> list = new ArrayList<>();

// With initial capacity (avoids resizing early — good for performance)
ArrayList<Integer> list2 = new ArrayList<>(100);

// From an existing collection
ArrayList<Integer> list3 = new ArrayList<>(List.of(1, 2, 3, 4, 5));

// Using the interface type (best practice)
List<String> names = new ArrayList<>();

List<String> fruits = new ArrayList<>();

fruits.add("Apple");            // adds to end → ["Apple"]
fruits.add("Banana");           // → ["Apple", "Banana"]
fruits.add(0, "Mango");         // insert at index 0 → ["Mango", "Apple", "Banana"]

fruits.addAll(List.of("Kiwi", "Grape")); // add entire collection at end
fruits.addAll(1, List.of("Peach"));      // add collection at index 1

String first = fruits.get(0);   // "Mango" — O(1)
int size = fruits.size();        // total number of elements

// Iterate with for-each
for (String f : fruits) {
    System.out.println(f);
}

// Iterate with index
for (int i = 0; i < fruits.size(); i++) {
    System.out.println(i + ": " + fruits.get(i));
}

// forEach with lambda
fruits.forEach(f -> System.out.println(f));

boolean has = fruits.contains("Apple");      // true — O(n)
int idx = fruits.indexOf("Apple");           // first occurrence index, or -1
int lastIdx = fruits.lastIndexOf("Apple");   // last occurrence index, or -1

fruits.set(0, "Papaya");   // replace element at index 0 — O(1)

fruits.remove(0);              // remove by index — O(n) due to shifting
fruits.remove("Banana");       // remove by value (first occurrence) — O(n)
fruits.removeAll(List.of("Kiwi", "Grape")); // remove all matching
fruits.retainAll(List.of("Apple", "Mango")); // keep ONLY these
fruits.clear();                // remove everything

List<Integer> nums = new ArrayList<>(List.of(5, 2, 8, 1));

Collections.sort(nums);                           // natural order → [1, 2, 5, 8]
Collections.sort(nums, Collections.reverseOrder()); // reverse → [8, 5, 2, 1]
nums.sort(Comparator.naturalOrder());             // same as Collections.sort
nums.sort(Comparator.reverseOrder());
nums.sort((a, b) -> a - b);                      // custom lambda comparator

List<Integer> sub = nums.subList(1, 3);  // [index 1, index 3) — view, not copy!

// List → Array
Integer[] arr = nums.toArray(new Integer[0]);

// Array → List (fixed size!)
List<Integer> fromArr = Arrays.asList(1, 2, 3);  // cannot add/remove
// Mutable version:
List<Integer> mutable = new ArrayList<>(Arrays.asList(1, 2, 3));

// Removing by int vs Integer!
List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
list.remove(1);       // removes by INDEX → list is [1, 3]
list.remove((Integer) 1); // removes by VALUE → list is [2, 3]

// ConcurrentModificationException — never modify while iterating
for (Integer n : list) {
    list.remove(n);  // CRASH! Use Iterator or removeIf instead
}
list.removeIf(n -> n % 2 == 0);  // safe removal

import java.util.LinkedList;

LinkedList<Integer> ll = new LinkedList<>();
LinkedList<String> ll2 = new LinkedList<>(List.of("a", "b", "c"));

LinkedList<String> ll = new LinkedList<>();

// Adding
ll.add("B");         // adds to end
ll.addFirst("A");    // adds to front → ["A", "B"]
ll.addLast("C");     // adds to end   → ["A", "B", "C"]
ll.add(1, "X");      // insert at index 1

// Accessing
String first = ll.getFirst();  // "A" — throws if empty
String last = ll.getLast();    // "C"
String elem = ll.get(1);       // "X" — O(n)

// Peeking (returns null if empty, does NOT throw)
String peekF = ll.peekFirst(); // look at front without removing
String peekL = ll.peekLast();  // look at back without removing

// Removing
ll.removeFirst();          // removes & returns front
ll.removeLast();           // removes & returns back
ll.remove(1);              // remove by index
ll.remove("B");            // remove by value

// Poll (returns null if empty, does NOT throw)
String polled = ll.pollFirst();
String polledL = ll.pollLast();

// Queue operations (uses the Queue interface)
ll.offer("Z");    // same as addLast
ll.poll();        // same as removeFirst
ll.peek();        // same as peekFirst

LinkedList<Integer> stack = new LinkedList<>();
stack.push(10);   // addFirst
stack.push(20);   // addFirst → [20, 10]
stack.pop();      // removeFirst → returns 20
stack.peek();     // peekFirst → returns 10

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

stack.push(1);    // [1]
stack.push(2);    // [1, 2]
stack.push(3);    // [1, 2, 3]

int top = stack.peek();  // 3 — look without removing
int popped = stack.pop(); // 3 — remove and return
boolean empty = stack.isEmpty(); // false
int size = stack.size();  // 2
boolean has = stack.contains(1); // true
int searchIdx = stack.search(2); // 1-based position from top

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> stack = new ArrayDeque<>();

stack.push(1);        // addFirst
stack.push(2);        // addFirst → top is 2
int top = stack.peek();  // 2
stack.pop();          // removes 2

import java.util.ArrayDeque;
import java.util.Queue;

Queue<String> queue = new ArrayDeque<>();

// Adding to rear
queue.add("A");      // throws NoSuchElementException if capacity exceeded
queue.offer("B");    // returns false if capacity exceeded (safer)
queue.offer("C");
// queue: [A, B, C] — front is A

// Peeking at front
String front = queue.peek();    // "A" — returns null if empty
String front2 = queue.element(); // "A" — throws if empty

// Removing from front
String removed = queue.poll();  // "A" — returns null if empty
String removed2 = queue.remove(); // "B" — throws if empty

queue.isEmpty();  // false
queue.size();     // 1

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> dq = new ArrayDeque<>();

// Adding
dq.addFirst(1);   // [1]
dq.addLast(2);    // [1, 2]
dq.offerFirst(0); // [0, 1, 2]
dq.offerLast(3);  // [0, 1, 2, 3]

// Peeking
dq.peekFirst();   // 0 — null if empty
dq.peekLast();    // 3 — null if empty

// Removing
dq.pollFirst();   // 0
dq.pollLast();    // 3
dq.removeFirst(); // 1 — throws if empty
dq.removeLast();  // 2 — throws if empty

// Size check
dq.isEmpty();
dq.size();

// Sliding window maximum — classic DSA problem
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] result = new int[nums.length - k + 1];
Deque<Integer> dq = new ArrayDeque<>();  // stores indices

for (int i = 0; i < nums.length; i++) {
    // Remove indices outside window
    while (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
        dq.pollFirst();
    // Remove smaller elements from back (they're useless)
    while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
        dq.pollLast();
    dq.offerLast(i);
    if (i >= k - 1)
        result[i - k + 1] = nums[dq.peekFirst()];
}

import java.util.PriorityQueue;

// Min-heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// OR
PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>((a, b) -> b - a);

// With initial capacity
PriorityQueue<Integer> pq = new PriorityQueue<>(100);

// Custom object heap (by second element of int[] pair)
PriorityQueue<int[]> pqCustom = new PriorityQueue<>((a, b) -> a[1] - b[1]);

PriorityQueue<Integer> pq = new PriorityQueue<>();

// Adding — O(log n)
pq.add(5);
pq.offer(1);
pq.add(3);
// Internal heap: [1, 5, 3] (heap order, not sorted!)

// Peek — O(1), does NOT remove
int min = pq.peek();  // 1 — returns null if empty
int min2 = pq.element(); // 1 — throws if empty

// Remove — O(log n)
int removed = pq.poll();   // 1 — returns null if empty
int removed2 = pq.remove(); // next min — throws if empty

// Size & check
pq.size();
pq.isEmpty();
pq.contains(3);    // O(n) — heap doesn't support fast search

// Iterate (NOT in sorted order!)
for (int n : pq) {
    System.out.println(n); // heap order, not guaranteed sorted
}

// To get sorted: keep polling
while (!pq.isEmpty()) {
    System.out.println(pq.poll()); // this IS sorted
}

// Keep a min-heap of size K; poll when size exceeds K
int[] nums = {1, 1, 1, 2, 2, 3};
int k = 2;

Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);

// Min-heap by frequency
PriorityQueue<Integer> pq = new PriorityQueue<>(
    (a, b) -> freq.get(a) - freq.get(b)
);

for (int key : freq.keySet()) {
    pq.offer(key);
    if (pq.size() > k) pq.poll(); // remove least frequent
}
// pq now contains top K frequent elements

import java.util.HashMap;
import java.util.Map;

HashMap<String, Integer> map = new HashMap<>();
HashMap<String, Integer> map2 = new HashMap<>(initialCapacity, loadFactor);
Map<String, Integer> map3 = new HashMap<>(Map.of("a", 1, "b", 2)); // copy

Map<String, Integer> map = new HashMap<>();

map.put("apple", 3);       // insert or update
map.put("banana", 5);
map.put("apple", 10);      // overwrites previous value

int val = map.get("apple");          // 10
int def = map.getOrDefault("cherry", 0);  // 0 — key doesn't exist

map.containsKey("apple");    // true — O(1) average
map.containsValue(10);       // true — O(n)
map.isEmpty();
map.size();

map.remove("banana");             // remove entry, returns old value
map.remove("apple", 10);          // remove ONLY if key maps to this exact value

// Over entries (most common)
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

// Over keys only
for (String key : map.keySet()) {
    System.out.println(key);
}

// Over values only
for (int value : map.values()) {
    System.out.println(value);
}

// forEach lambda
map.forEach((key, value) -> System.out.println(key + ": " + value));

// putIfAbsent — only inserts if key NOT already present
map.putIfAbsent("cherry", 7);

// getOrDefault — return default if key missing (read-only)
int count = map.getOrDefault("fig", 0);

// computeIfAbsent — compute & insert if absent (great for grouping)
Map<Character, List<String>> groups = new HashMap<>();
groups.computeIfAbsent('a', k -> new ArrayList<>()).add("apple");
groups.computeIfAbsent('a', k -> new ArrayList<>()).add("avocado");
// groups: {'a': ["apple", "avocado"]}

// compute — always recomputes
map.compute("apple", (key, oldVal) -> oldVal == null ? 1 : oldVal + 1);

// merge — BEST for frequency counting
String[] words = {"a", "b", "a", "c", "b", "a"};
Map<String, Integer> freq = new HashMap<>();
for (String w : words) {
    freq.merge(w, 1, Integer::sum);
    // If w not present: put w→1; if present: apply Integer::sum(old, 1)
}
// freq: {a=3, b=2, c=1}

// replaceAll — transform all values
map.replaceAll((key, oldVal) -> oldVal * 2);

String[] arr = {"cat", "dog", "cat", "bird", "dog", "cat"};
Map<String, Integer> freq = new HashMap<>();

// Way 1 — traditional
for (String s : arr) {
    freq.put(s, freq.getOrDefault(s, 0) + 1);
}

// Way 2 — merge (cleanest)
for (String s : arr) {
    freq.merge(s, 1, Integer::sum);
}

// Way 3 — compute
for (String s : arr) {
    freq.compute(s, (k, v) -> v == null ? 1 : v + 1);
}

import java.util.LinkedHashMap;

// Insertion order (default)
Map<String, Integer> map = new LinkedHashMap<>();
map.put("banana", 2);
map.put("apple", 5);
map.put("cherry", 1);
// Iteration order: banana, apple, cherry (insertion order)

// Access-order (for LRU Cache)
// Constructor: (initialCapacity, loadFactor, accessOrder)
LinkedHashMap<Integer, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > 3; // max 3 entries
    }
};
lru.put(1, 10);
lru.put(2, 20);
lru.put(3, 30);
lru.get(1);     // 1 becomes most recently used
lru.put(4, 40); // 2 is evicted (least recently used)
System.out.println(lru.keySet()); // [3, 1, 4]

import java.util.TreeMap;

TreeMap<Integer, String> tmap = new TreeMap<>();
tmap.put(5, "five");
tmap.put(1, "one");
tmap.put(3, "three");
tmap.put(7, "seven");
// Internal order: 1, 3, 5, 7

// Navigation methods
tmap.firstKey();        // 1 — smallest key
tmap.lastKey();         // 7 — largest key
tmap.floorKey(4);       // 3 — largest key ≤ 4
tmap.ceilingKey(4);     // 5 — smallest key ≥ 4
tmap.lowerKey(3);       // 1 — strictly < 3
tmap.higherKey(3);      // 5 — strictly > 3

// Submap views (from=inclusive, to=exclusive)
tmap.subMap(1, 5);      // {1=one, 3=three}
tmap.headMap(4);        // {1=one, 3=three} — keys < 4
tmap.tailMap(3);        // {3=three, 5=five, 7=seven} — keys ≥ 3

// Remove extremes
tmap.pollFirstEntry();  // removes & returns {1=one}
tmap.pollLastEntry();   // removes & returns {7=seven}

import java.util.HashSet;
import java.util.Set;

Set<Integer> set = new HashSet<>();

set.add(1);
set.add(2);
set.add(2);   // ignored — duplicate
set.add(3);
// set: {1, 2, 3} (order not guaranteed)

set.contains(2);   // true — O(1)
set.remove(2);     // true if removed
set.size();        // 2
set.isEmpty();

// Bulk operations
Set<Integer> a = new HashSet<>(List.of(1, 2, 3, 4));
Set<Integer> b = new HashSet<>(List.of(3, 4, 5, 6));

// Union (modifies a)
a.addAll(b);        // a = {1, 2, 3, 4, 5, 6}

// Intersection (modifies a)
a.retainAll(b);     // a = {3, 4, 5, 6}

// Difference (modifies a)
a.removeAll(b);     // removes b's elements from a

// Iterate
for (int n : set) {
    System.out.println(n);
}
set.forEach(System.out::println);

Set<String> lhs = new LinkedHashSet<>();
lhs.add("banana");
lhs.add("apple");
lhs.add("cherry");
lhs.add("apple");   // ignored

// Iterates in insertion order: banana, apple, cherry
for (String s : lhs) System.out.println(s);

import java.util.TreeSet;

TreeSet<Integer> ts = new TreeSet<>();
ts.add(5);
ts.add(1);
ts.add(8);
ts.add(3);
// ts: [1, 3, 5, 8]

ts.first();         // 1 — smallest
ts.last();          // 8 — largest
ts.floor(4);        // 3 — largest element ≤ 4
ts.ceiling(4);      // 5 — smallest element ≥ 4
ts.lower(5);        // 3 — strictly < 5
ts.higher(5);       // 8 — strictly > 5

ts.headSet(5);      // [1, 3] — elements < 5
ts.tailSet(5);      // [5, 8] — elements ≥ 5
ts.subSet(1, 6);    // [1, 3, 5] — 1 ≤ x < 6

ts.pollFirst();     // removes & returns 1
ts.pollLast();      // removes & returns 8

// Descending view
ts.descendingSet();  // NavigableSet in reverse order

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

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

// Sorting
Collections.sort(list);                           // [1, 1, 2, 3, 4, 5, 6, 9]
Collections.sort(list, Collections.reverseOrder()); // descending

// Min / Max
Collections.min(list);   // 1
Collections.max(list);   // 9

// Reverse
Collections.reverse(list);

// Shuffle
Collections.shuffle(list);            // random order
Collections.shuffle(list, new Random(42)); // with seed (reproducible)

// Binary Search (list must be sorted first!)
Collections.sort(list);
int idx = Collections.binarySearch(list, 5); // index of 5, or negative if absent

// Frequency count
Collections.frequency(list, 1);   // how many times 1 appears

// Fill — replace all elements with one value
Collections.fill(list, 0);

// Copy — copies src into dest (dest must be at least as large)
List<Integer> dest = new ArrayList<>(Arrays.asList(0, 0, 0, 0, 0, 0, 0, 0));
Collections.copy(dest, list);

// nCopies — immutable list of n copies of a value
List<String> repeated = Collections.nCopies(5, "hello"); // ["hello", "hello", ...]

// disjoint — true if two collections share no elements
Collections.disjoint(List.of(1,2,3), List.of(4,5,6)); // true

// Unmodifiable wrappers
List<Integer> immutable = Collections.unmodifiableList(list);
// immutable.add(1); // throws UnsupportedOperationException

// Synchronized wrappers (thread-safe)
List<Integer> synced = Collections.synchronizedList(list);

// Swap
Collections.swap(list, 0, list.size() - 1); // swap first and last

// Rotate
Collections.rotate(list, 2); // shift right by 2 positions

import java.util.stream.*;
import java.util.*;

// From a Collection
List<String> names = List.of("Alice", "Bob", "Charlie");
Stream<String> s1 = names.stream();

// From an Array
String[] arr = {"a", "b", "c"};
Stream<String> s2 = Arrays.stream(arr);
Stream<String> s3 = Stream.of("a", "b", "c");

// From a range of ints (IntStream)
IntStream range = IntStream.range(0, 5);    // 0, 1, 2, 3, 4
IntStream rangeC = IntStream.rangeClosed(1, 5); // 1, 2, 3, 4, 5

// Infinite streams
Stream<Integer> naturals = Stream.iterate(1, n -> n + 1); // 1, 2, 3, ...
Stream<Integer> naturalsV2 = Stream.iterate(1, n -> n <= 100, n -> n + 1); // with condition
Stream<Double> randoms = Stream.generate(Math::random); // infinite random doubles

// Empty stream
Stream<String> empty = Stream.empty();

// From a Map
Map<String, Integer> map = Map.of("a", 1, "b", 2);
Stream<Map.Entry<String, Integer>> entryStream = map.entrySet().stream();

List<Integer> nums = List.of(1, 2, 3, 4, 5, 6, 7, 8);

List<Integer> evens = nums.stream()
    .filter(n -> n % 2 == 0)
    .collect(Collectors.toList());
// [2, 4, 6, 8]

// Multiple filters chain cleanly
List<Integer> result = nums.stream()
    .filter(n -> n > 2)
    .filter(n -> n < 7)
    .collect(Collectors.toList());
// [3, 4, 5, 6]

List<String> words = List.of("hello", "world", "java");

// String → uppercase
List<String> upper = words.stream()
    .map(String::toUpperCase)
    .collect(Collectors.toList());
// ["HELLO", "WORLD", "JAVA"]

// String → length
List<Integer> lengths = words.stream()
    .map(String::length)
    .collect(Collectors.toList());
// [5, 5, 4]

// Object field extraction
record Person(String name, int age) {}
List<Person> people = List.of(new Person("Alice", 30), new Person("Bob", 25));

List<String> namesList = people.stream()
    .map(Person::name)
    .collect(Collectors.toList());
// ["Alice", "Bob"]

// Avoids boxing overhead when working with numbers
int[] doubled = IntStream.of(1, 2, 3)
    .map(n -> n * 2)
    .toArray();
// [2, 4, 6]

int sum = List.of(1, 2, 3, 4, 5).stream()
    .mapToInt(Integer::intValue)
    .sum();
// 15

// Or use the shortcut
int sum2 = List.of(1, 2, 3, 4, 5).stream()
    .mapToInt(n -> n)
    .sum();

// Each element maps to a stream; results are flattened into one stream
List<List<Integer>> nested = List.of(
    List.of(1, 2, 3),
    List.of(4, 5),
    List.of(6, 7, 8, 9)
);

List<Integer> flat = nested.stream()
    .flatMap(Collection::stream)
    .collect(Collectors.toList());
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

// Splitting sentences into words
List<String> sentences = List.of("hello world", "java streams");
List<String> words = sentences.stream()
    .flatMap(s -> Arrays.stream(s.split(" ")))
    .collect(Collectors.toList());
// ["hello", "world", "java", "streams"]

List<Integer> withDups = List.of(1, 2, 2, 3, 3, 3, 4);

List<Integer> unique = withDups.stream()
    .distinct()
    .collect(Collectors.toList());
// [1, 2, 3, 4]

List<Integer> nums = List.of(5, 2, 8, 1, 9, 3);

// Natural order
List<Integer> asc = nums.stream()
    .sorted()
    .collect(Collectors.toList());
// [1, 2, 3, 5, 8, 9]

// Reverse order
List<Integer> desc = nums.stream()
    .sorted(Comparator.reverseOrder())
    .collect(Collectors.toList());

// Custom comparator
List<String> words = List.of("banana", "apple", "kiwi", "mango");
List<String> byLength = words.stream()
    .sorted(Comparator.comparingInt(String::length))
    .collect(Collectors.toList());
// ["kiwi", "apple", "mango", "banana"]

// Chained comparators
List<String> byLengthThenAlpha = words.stream()
    .sorted(Comparator.comparingInt(String::length)
        .thenComparing(Comparator.naturalOrder()))
    .collect(Collectors.toList());

List<Integer> nums = List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

// limit — take first N elements
List<Integer> first5 = nums.stream()
    .limit(5)
    .collect(Collectors.toList());
// [1, 2, 3, 4, 5]

// skip — skip first N elements
List<Integer> skip3 = nums.stream()
    .skip(3)
    .collect(Collectors.toList());
// [4, 5, 6, 7, 8, 9, 10]

// Pagination pattern
int page = 2, pageSize = 3;
List<Integer> page2 = nums.stream()
    .skip((long)(page - 1) * pageSize)
    .limit(pageSize)
    .collect(Collectors.toList());
// [4, 5, 6]

// First 5 even numbers from an infinite stream
List<Integer> first5Evens = Stream.iterate(2, n -> n + 2)
    .limit(5)
    .collect(Collectors.toList());
// [2, 4, 6, 8, 10]