Java Collections — Complete Reference for DSA & Daily Use

A categorized guide to Java's Collection Framework covering the most-used methods in competitive programming, DSA problem solving, and everyday development.

---

Table of Contents

1. Collection Framework Overview
2. List Interface
   • ArrayList
   • LinkedList
3. Stack
4. Queue & Deque
   • PriorityQueue (Heap)
   • ArrayDeque
   • LinkedList as Queue/Deque
5. Set Interface
   • HashSet
   • LinkedHashSet
   • TreeSet
6. Map Interface
   • HashMap
   • LinkedHashMap
   • TreeMap
7. Utility Classes
   • Collections
   • Arrays
8. DSA Quick-Pick Guide
9. Complexity Cheat Sheet

---

Collection Framework Overview

java.util
│
├── Collection (Interface)
│   ├── List          → ArrayList, LinkedList, Stack, Vector
│   ├── Set           → HashSet, LinkedHashSet, TreeSet
│   └── Queue         → PriorityQueue, ArrayDeque, LinkedList
│
└── Map (Interface)   → HashMap, LinkedHashMap, TreeMap, Hashtable

Key Properties at a glance:

Class	Order	Duplicates	Null	Thread-safe
ArrayList	Insertion	✅	✅	❌
LinkedList	Insertion	✅	✅	❌
HashSet	None	❌	1 null	❌
LinkedHashSet	Insertion	❌	1 null	❌
TreeSet	Sorted	❌	❌	❌
HashMap	None	Keys: ❌	1 null key	❌
LinkedHashMap	Insertion	Keys: ❌	1 null key	❌
TreeMap	Sorted Key	Keys: ❌	❌	❌
PriorityQueue	Natural/Comparator	✅	❌	❌
ArrayDeque	Insertion	✅	❌	❌

---

List Interface

ArrayList

Best for: Random access, frequent reads, index-based operations.

import java.util.ArrayList;

ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>(initialCapacity); // pre-allocate

Most Used Methods

// ─── Add ───────────────────────────────────────────────
list.add(10);               // Append to end         → O(1) amortized
list.add(0, 99);            // Insert at index        → O(n)
list.addAll(otherList);     // Append all elements    → O(k)
list.addAll(2, otherList);  // Insert all at index    → O(n+k)

// ─── Access ────────────────────────────────────────────
list.get(2);                // Get by index           → O(1)
list.size();                // Number of elements     → O(1)
list.isEmpty();             // true if size == 0      → O(1)
list.contains(5);           // Linear search          → O(n)
list.indexOf(5);            // First index of value   → O(n)
list.lastIndexOf(5);        // Last index of value    → O(n)

// ─── Update ────────────────────────────────────────────
list.set(1, 42);            // Replace at index       → O(1)

// ─── Remove ────────────────────────────────────────────
list.remove(Integer.valueOf(5)); // Remove by value   → O(n)
list.remove(2);             // Remove by index        → O(n)
list.removeAll(otherList);  // Remove all matches     → O(n*k)
list.clear();               // Empty the list         → O(n)

// ─── Sublist & Conversion ──────────────────────────────
list.subList(1, 4);         // View [1, 4)            → O(1)
list.toArray();             // Convert to Object[]    → O(n)
Collections.sort(list);     // Sort ascending         → O(n log n)
Collections.reverse(list);  // Reverse in-place       → O(n)

// ─── DSA Patterns ──────────────────────────────────────
// Two-pointer swap
Collections.swap(list, i, j);

// Frequency count
Collections.frequency(list, 5);

// Binary search (only on sorted list)
Collections.binarySearch(list, 5);   // O(log n)

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

Daily Usage Examples

// Building result list in DSA
List<List<Integer>> result = new ArrayList<>();
List<Integer> row = new ArrayList<>(Arrays.asList(1, 2, 3));
result.add(new ArrayList<>(row)); // Always copy when reusing!

// String split to list
String[] arr = s.split(",");
List<String> words = new ArrayList<>(Arrays.asList(arr));

---

LinkedList

Best for: Frequent insertions/deletions at head/tail, implementing Deque.

import java.util.LinkedList;

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

Most Used Methods

// ─── Add ───────────────────────────────────────────────
ll.add(5);              // Add at tail                → O(1)
ll.addFirst(1);         // Add at head                → O(1)
ll.addLast(9);          // Add at tail                → O(1)
ll.add(2, 7);           // Add at index               → O(n)

// ─── Access ────────────────────────────────────────────
ll.get(0);              // By index (slow)            → O(n)
ll.getFirst();          // Peek head                  → O(1)
ll.getLast();           // Peek tail                  → O(1)
ll.peek();              // Peek head (null-safe)       → O(1)
ll.peekFirst();         // Same as peek               → O(1)
ll.peekLast();          // Peek tail (null-safe)       → O(1)

// ─── Remove ────────────────────────────────────────────
ll.remove();            // Remove head (throws if empty) → O(1)
ll.removeFirst();       // Remove head                → O(1)
ll.removeLast();        // Remove tail                → O(1)
ll.poll();              // Remove head (null-safe)    → O(1)
ll.pollFirst();         // Same as poll               → O(1)
ll.pollLast();          // Remove tail (null-safe)    → O(1)

// ─── Stack-like ────────────────────────────────────────
ll.push(x);             // Push to front (addFirst)   → O(1)
ll.pop();               // Pop from front (removeFirst)→ O(1)

---

Stack

Best for: DFS, backtracking, expression evaluation, undo operations.

⚠️ Prefer Deque<Integer> stack = new ArrayDeque<>() over Stack<> in DSA — it's faster (no synchronization overhead).

import java.util.Stack;
Stack<Integer> stack = new Stack<>();

// Preferred in DSA:
Deque<Integer> stack = new ArrayDeque<>();

Most Used Methods

// Using Stack class
stack.push(10);         // Push                       → O(1)
stack.pop();            // Pop & return top           → O(1)
stack.peek();           // View top (no remove)       → O(1)
stack.isEmpty();        // Check empty                → O(1)
stack.size();           // Size                       → O(1)
stack.search(5);        // 1-based position from top  → O(n)

// Using ArrayDeque as Stack (preferred)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);         // addFirst()                 → O(1)
stack.pop();            // removeFirst()              → O(1)
stack.peek();           // peekFirst()                → O(1)

DSA Patterns

// Monotonic Stack (Next Greater Element)
Deque<Integer> mono = new ArrayDeque<>();
for (int num : nums) {
    while (!mono.isEmpty() && mono.peek() < num)
        mono.pop();
    mono.push(num);
}

// Valid Parentheses
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
    if (c == '(') st.push(c);
    else if (!st.isEmpty()) st.pop();
    else return false;
}
return st.isEmpty();

---

Queue & Deque

PriorityQueue (Heap)

Best for: Dijkstra's, Top-K problems, scheduling, greedy algorithms.

import java.util.PriorityQueue;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();               // Min-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Max-heap
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // Custom comparator

Most Used Methods

pq.offer(5);            // Insert (preferred)         → O(log n)
pq.add(5);              // Insert (throws on fail)    → O(log n)
pq.peek();              // View min (no remove)       → O(1)
pq.poll();              // Remove & return min        → O(log n)
pq.remove();            // Same as poll (throws)      → O(log n)
pq.contains(5);         // Linear search              → O(n)
pq.size();              // Size                       → O(1)
pq.isEmpty();           // Check empty                → O(1)
pq.clear();             // Empty heap                 → O(n)

DSA Patterns

// Top K Largest elements
PriorityQueue<Integer> minH = new PriorityQueue<>();
for (int n : nums) {
    minH.offer(n);
    if (minH.size() > k) minH.poll(); // keep only k largest
}

// Dijkstra's shortest path
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{src, 0}); // {node, dist}
while (!pq.isEmpty()) {
    int[] curr = pq.poll();
    // ... relax edges
}

// Merge K sorted lists
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

---

ArrayDeque

Best for: BFS, sliding window, palindrome checks, double-ended queue operations.

import java.util.ArrayDeque;

Deque<Integer> dq = new ArrayDeque<>();
Queue<Integer> q = new ArrayDeque<>(); // Use as Queue in BFS

Most Used Methods

// ─── Add ───────────────────────────────────────────────
dq.offerFirst(1);       // Add to front               → O(1)
dq.offerLast(9);        // Add to back                → O(1)
dq.offer(5);            // Add to back (Queue mode)   → O(1)
dq.addFirst(1);         // Add to front (throws)      → O(1)
dq.addLast(9);          // Add to back (throws)       → O(1)

// ─── Peek ──────────────────────────────────────────────
dq.peekFirst();         // View front                 → O(1)
dq.peekLast();          // View back                  → O(1)
dq.peek();              // View front (Queue mode)    → O(1)

// ─── Remove ────────────────────────────────────────────
dq.pollFirst();         // Remove from front          → O(1)
dq.pollLast();          // Remove from back           → O(1)
dq.poll();              // Remove front (Queue mode)  → O(1)

// ─── Size ──────────────────────────────────────────────
dq.size();              // Size                       → O(1)
dq.isEmpty();           // Check empty                → O(1)

DSA Patterns

// BFS (Tree/Graph)
Queue<Integer> bfs = new ArrayDeque<>();
bfs.offer(root);
while (!bfs.isEmpty()) {
    int node = bfs.poll();
    // process node
    bfs.offer(node.left);
    bfs.offer(node.right);
}

// Sliding Window Maximum (Monotonic Deque)
Deque<Integer> dq = new ArrayDeque<>(); // stores indices
for (int i = 0; i < nums.length; i++) {
    while (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
        dq.pollFirst();
    while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
        dq.pollLast();
    dq.offerLast(i);
    if (i >= k - 1) result[i - k + 1] = nums[dq.peekFirst()];
}

---

LinkedList as Queue/Deque

Queue<Integer> queue = new LinkedList<>();
queue.offer(1); queue.offer(2); queue.offer(3);
while (!queue.isEmpty()) {
    System.out.print(queue.poll() + " "); // 1 2 3
}

Prefer ArrayDeque over LinkedList as a queue — no node allocation overhead.

---

Set Interface

HashSet

Best for: Deduplication, O(1) lookup, visited tracking in BFS/DFS.

import java.util.HashSet;

HashSet<Integer> set = new HashSet<>();
Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 3)); // Init from array

Most Used Methods

set.add(5);             // Add element                → O(1) avg
set.remove(5);          // Remove element             → O(1) avg
set.contains(5);        // Check presence             → O(1) avg
set.size();             // Count elements             → O(1)
set.isEmpty();          // Check empty                → O(1)
set.clear();            // Remove all                 → O(n)
set.addAll(list);       // Add collection (union)     → O(k)

// Set operations
Set<Integer> a = new HashSet<>(set1);
a.retainAll(set2);      // Intersection               → O(n)
a.removeAll(set2);      // Difference                 → O(n)
a.addAll(set2);         // Union                      → O(n)

DSA Patterns

// Two Sum (O(n))
Set<Integer> seen = new HashSet<>();
for (int n : nums) {
    if (seen.contains(target - n)) return true;
    seen.add(n);
}

// Longest Consecutive Sequence (O(n))
Set<Integer> s = new HashSet<>(Arrays.asList(nums));
for (int n : s) {
    if (!s.contains(n - 1)) { // start of sequence
        int len = 1;
        while (s.contains(n + len)) len++;
        max = Math.max(max, len);
    }
}

// Detect Cycle (Floyd or HashSet)
Set<ListNode> visited = new HashSet<>();
while (node != null) {
    if (!visited.add(node)) return true; // add returns false if duplicate
    node = node.next;
}

---

LinkedHashSet

Best for: Deduplication while preserving insertion order.

LinkedHashSet<String> lhs = new LinkedHashSet<>();
lhs.add("banana"); lhs.add("apple"); lhs.add("cherry");
// Iteration: banana → apple → cherry (insertion order)

Same methods as HashSet. Only difference: iteration order is insertion order.

---

TreeSet

Best for: Sorted unique elements, range queries, floor/ceiling operations.

import java.util.TreeSet;

TreeSet<Integer> ts = new TreeSet<>();
TreeSet<Integer> desc = new TreeSet<>(Collections.reverseOrder());

Most Used Methods

ts.add(5);              // Insert                     → O(log n)
ts.remove(5);           // Delete                     → O(log n)
ts.contains(5);         // Search                     → O(log n)
ts.size();              // Count                      → O(1)

// ─── Navigation (unique to TreeSet) ────────────────────
ts.first();             // Smallest element           → O(log n)
ts.last();              // Largest element            → O(log n)
ts.floor(5);            // Largest ≤ 5                → O(log n)
ts.ceiling(5);          // Smallest ≥ 5               → O(log n)
ts.lower(5);            // Largest < 5 (strict)       → O(log n)
ts.higher(5);           // Smallest > 5 (strict)      → O(log n)
ts.pollFirst();         // Remove & return smallest   → O(log n)
ts.pollLast();          // Remove & return largest    → O(log n)
ts.headSet(5);          // All elements < 5           → O(log n)
ts.tailSet(5);          // All elements ≥ 5           → O(log n)
ts.subSet(3, 8);        // Elements in [3, 8)         → O(log n)
ts.descendingSet();     // Reverse view               → O(1)

DSA Patterns

// Contains Duplicate III (sliding window + TreeSet)
TreeSet<Long> window = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
    Long floor = window.floor((long)nums[i] + t);
    if (floor != null && floor >= (long)nums[i] - t) return true;
    window.add((long)nums[i]);
    if (i >= k) window.remove((long)nums[i - k]);
}

// Closest value in BST set
ts.floor(target);   // ≤ target
ts.ceiling(target); // ≥ target

---

Map Interface

HashMap

Best for: Frequency counting, memoization, graph adjacency, grouping.

import java.util.HashMap;

HashMap<String, Integer> map = new HashMap<>();
Map<Integer, List<Integer>> adj = new HashMap<>(); // adjacency list

Most Used Methods

// ─── Put / Update ──────────────────────────────────────
map.put("a", 1);            // Insert/overwrite       → O(1) avg
map.putIfAbsent("a", 0);    // Insert only if missing → O(1) avg

// ─── Frequency Pattern ─────────────────────────────────
map.getOrDefault("a", 0);   // Get or default value   → O(1)
map.merge("a", 1, Integer::sum);  // key++ elegantly  → O(1)

// Java 8+ compute
map.compute("a", (k, v) -> v == null ? 1 : v + 1); // manual merge
map.computeIfAbsent("a", k -> new ArrayList<>());    // init lists

// ─── Access ────────────────────────────────────────────
map.get("a");               // Get value (null if absent) → O(1)
map.containsKey("a");       // Check key              → O(1)
map.containsValue(5);       // Check value (slow)     → O(n)
map.size();                 // Number of entries      → O(1)
map.isEmpty();              // Check empty            → O(1)

// ─── Remove ────────────────────────────────────────────
map.remove("a");            // Remove by key          → O(1)
map.remove("a", 5);         // Remove only if value = 5→ O(1)

// ─── Iterate ───────────────────────────────────────────
for (Map.Entry<String, Integer> e : map.entrySet()) {
    System.out.println(e.getKey() + " → " + e.getValue());
}
for (String key : map.keySet()) { ... }
for (int val : map.values()) { ... }

// ─── Replace ───────────────────────────────────────────
map.replace("a", 99);       // Replace value for key  → O(1)
map.replaceAll((k, v) -> v * 2); // Transform all values → O(n)

DSA Patterns

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

// Group Anagrams
Map<String, List<String>> groups = new HashMap<>();
for (String s : strs) {
    char[] ch = s.toCharArray();
    Arrays.sort(ch);
    groups.computeIfAbsent(new String(ch), k -> new ArrayList<>()).add(s);
}

// Memoization (top-down DP)
Map<Integer, Long> memo = new HashMap<>();
long fib(int n) {
    if (n <= 1) return n;
    return memo.computeIfAbsent(n, k -> fib(k-1) + fib(k-2));
}

// Two Sum
Map<Integer, Integer> idx = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    if (idx.containsKey(target - nums[i]))
        return new int[]{idx.get(target - nums[i]), i};
    idx.put(nums[i], i);
}

// Subarray Sum = K (prefix sum)
Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1);
int sum = 0, count = 0;
for (int n : nums) {
    sum += n;
    count += prefixCount.getOrDefault(sum - k, 0);
    prefixCount.merge(sum, 1, Integer::sum);
}

---

LinkedHashMap

Best for: LRU Cache, ordered maps, preserving insertion order.

LinkedHashMap<Integer, Integer> lru = new LinkedHashMap<>(capacity, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
};
// accessOrder=true → access order (LRU); false → insertion order

Same methods as HashMap. Key extras: removeEldestEntry, access-order mode.

---

TreeMap

Best for: Sorted maps, range queries, scheduling, time-series data.

import java.util.TreeMap;

TreeMap<Integer, String> tm = new TreeMap<>();
TreeMap<Integer, Integer> desc = new TreeMap<>(Collections.reverseOrder());

Most Used Methods

tm.put(3, "c");             // Insert                 → O(log n)
tm.get(3);                  // Get by key             → O(log n)
tm.remove(3);               // Delete                 → O(log n)
tm.containsKey(3);          // Key exists             → O(log n)
tm.size();                  // Count                  → O(1)

// ─── Navigation (unique to TreeMap) ────────────────────
tm.firstKey();              // Smallest key           → O(log n)
tm.lastKey();               // Largest key            → O(log n)
tm.floorKey(5);             // Largest key ≤ 5        → O(log n)
tm.ceilingKey(5);           // Smallest key ≥ 5       → O(log n)
tm.lowerKey(5);             // Largest key < 5        → O(log n)
tm.higherKey(5);            // Smallest key > 5       → O(log n)
tm.pollFirstEntry();        // Remove & return min    → O(log n)
tm.pollLastEntry();         // Remove & return max    → O(log n)
tm.headMap(5);              // Keys < 5               → O(log n)
tm.tailMap(5);              // Keys ≥ 5               → O(log n)
tm.subMap(3, 8);            // Keys in [3, 8)         → O(log n)
tm.firstEntry();            // Min key-value pair     → O(log n)
tm.lastEntry();             // Max key-value pair     → O(log n)

DSA Patterns

// Meeting Rooms / Interval Scheduling
TreeMap<Integer, Integer> timeline = new TreeMap<>();
for (int[] interval : intervals) {
    timeline.merge(interval[0], 1, Integer::sum);   // +1 at start
    timeline.merge(interval[1], -1, Integer::sum);  // -1 at end
}

// Car Fleet / Sweep Line
TreeMap<Integer, String> events = new TreeMap<>();
for (int[] ev : schedule)
    events.put(ev[0], "start");

// Count of Smaller Numbers After Self
// (use TreeMap<value, count> or BIT/Merge Sort)

// Stock price range queries
TreeMap<Integer, Integer> prices = new TreeMap<>();
int maxInRange = prices.subMap(lo, hi).values().stream().max(Integer::compare).orElse(0);

---

Utility Classes

Collections Utility

import java.util.Collections;

List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5));

// ─── Sorting ───────────────────────────────────────────
Collections.sort(list);                         // Ascending       O(n log n)
Collections.sort(list, Collections.reverseOrder()); // Descending  O(n log n)
Collections.sort(list, (a, b) -> b - a);        // Custom         O(n log n)

// ─── Search ────────────────────────────────────────────
Collections.binarySearch(list, 4);              // Must be sorted  O(log n)

// ─── Min / Max ─────────────────────────────────────────
Collections.min(list);                          //                 O(n)
Collections.max(list);                          //                 O(n)
Collections.min(list, comparator);              // Custom          O(n)

// ─── Shuffle & Reverse ─────────────────────────────────
Collections.shuffle(list);                      // Random order    O(n)
Collections.reverse(list);                      // In-place        O(n)

// ─── Copy & Fill ───────────────────────────────────────
Collections.fill(list, 0);                      // Set all to 0    O(n)
List<Integer> copy = new ArrayList<>(list);     // Preferred copy
Collections.copy(dest, src);                    // dest.size ≥ src O(n)

// ─── Frequency & Disjoint ──────────────────────────────
Collections.frequency(list, 1);                 // Count of value  O(n)
Collections.disjoint(list1, list2);             // No common elems O(n)

// ─── Swap & Rotate ─────────────────────────────────────
Collections.swap(list, i, j);                   //                 O(1)
Collections.rotate(list, k);                    // Shift right k   O(n)

// ─── Immutable Wrappers ─────────────────────────────────
List<Integer> immutable = Collections.unmodifiableList(list);
Set<Integer> singleton = Collections.singleton(42);
List<Integer> nCopies = Collections.nCopies(5, 0); // [0,0,0,0,0]
List<Integer> empty = Collections.emptyList();

---

Arrays Utility

import java.util.Arrays;

int[] arr = {5, 3, 1, 4, 2};

// ─── Sort ──────────────────────────────────────────────
Arrays.sort(arr);                               // Primitive       O(n log n)
Arrays.sort(arr, 2, 5);                         // Range sort      O(k log k)
Integer[] boxed = {3,1,2};
Arrays.sort(boxed, Collections.reverseOrder()); // Reverse (boxed) O(n log n)
Arrays.sort(boxed, (a, b) -> b - a);            // Custom         O(n log n)

// ─── Search ────────────────────────────────────────────
Arrays.binarySearch(arr, 3);                    // Sorted only     O(log n)

// ─── Copy ──────────────────────────────────────────────
int[] copy = Arrays.copyOf(arr, arr.length);    // Full copy       O(n)
int[] part = Arrays.copyOfRange(arr, 1, 4);     // [1, 4)          O(k)

// ─── Fill ──────────────────────────────────────────────
Arrays.fill(arr, 0);                            // Fill all        O(n)
Arrays.fill(arr, 2, 5, -1);                     // Fill range      O(k)

// ─── Compare ───────────────────────────────────────────
Arrays.equals(arr1, arr2);                      // Element-wise    O(n)
Arrays.deepEquals(matrix1, matrix2);            // 2D arrays       O(n*m)

// ─── Convert ───────────────────────────────────────────
List<Integer> list = Arrays.asList(1, 2, 3);    // Fixed-size list O(1)
String s = Arrays.toString(arr);                // "[5, 3, 1...]"  O(n)
String s2 = Arrays.deepToString(matrix);        // 2D print        O(n*m)

// ─── Stream ────────────────────────────────────────────
int sum = Arrays.stream(arr).sum();             //                 O(n)
int max = Arrays.stream(arr).max().getAsInt();  //                 O(n)
int[] filtered = Arrays.stream(arr).filter(x -> x > 2).toArray();

---

DSA Quick-Pick Guide

Problem Type	Best Collection	Key Method
Sliding Window Max	ArrayDeque (monotonic)	peekFirst(), pollLast()
Top-K Elements	PriorityQueue (min-heap)	offer(), poll(), peek()
BFS / Level Order	ArrayDeque as Queue	offer(), poll()
DFS / Backtracking	ArrayDeque as Stack	push(), pop()
Frequency Count	HashMap	merge(), getOrDefault()
Two Sum / Fast Lookup	HashSet / HashMap	contains(), get()
Sorted Unique Values	TreeSet	floor(), ceiling()
Range Queries (map)	TreeMap	floorKey(), subMap()
LRU Cache	LinkedHashMap	removeEldestEntry()
Anagram Grouping	HashMap<String, List>	computeIfAbsent()
Graph Adjacency	HashMap<Node, List<Node>>	computeIfAbsent()
Cycle Detection	HashSet	add() returns false if dup
Merge K Sorted Lists	PriorityQueue	offer(), poll()
Valid Parentheses	ArrayDeque as Stack	push(), pop(), isEmpty()
Next Greater Element	ArrayDeque (mono stack)	peek(), pop(), push()
Memoization	HashMap	computeIfAbsent()
Intervals / Sweep Line	TreeMap	merge(), entrySet()
Deduplicate + Order	LinkedHashSet	add(), iteration

---

Complexity Cheat Sheet

Time Complexity

Operation	ArrayList	LinkedList	HashSet	TreeSet	HashMap	TreeMap	PriorityQueue
Add	O(1)*	O(1)	O(1)*	O(log n)	O(1)*	O(log n)	O(log n)
Remove	O(n)	O(1)	O(1)*	O(log n)	O(1)*	O(log n)	O(log n)
Get/Search	O(1)	O(n)	O(1)*	O(log n)	O(1)*	O(log n)	O(n)
Peek Min/Max	O(n)	O(1)†	O(n)	O(log n)	—	O(log n)	O(1)
Iteration	O(n)	O(n)	O(n)	O(n)	O(n)	O(n)	O(n)

*O(1) average, O(n) worst case for hash collisions
†Only for first/last elements

Space Complexity

All collections: O(n) where n = number of elements.

---

💡 Pro Tips:

• Always use Integer.valueOf() not == when comparing boxed integers in collections.
• Use new ArrayList<>(existingCollection) to copy — never assign directly.
• ArrayDeque is always preferred over Stack and LinkedList as queue in DSA.
• getOrDefault() + merge() are the two most powerful HashMap methods in DSA.
• For 2D DP tables, int[][] dp = new int[m][n] (primitives) is faster than ArrayList<ArrayList<Integer>>.