A categorized guide to Java's Collection Framework covering the most-used methods in competitive programming, DSA problem solving, and everyday development.
- Collection Framework Overview
- List Interface
- Stack
- Queue & Deque
- Set Interface
- Map Interface
- Utility Classes
- DSA Quick-Pick Guide
- Complexity Cheat Sheet
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 | ✅ | ❌ | ❌ |
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// ─── 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);// 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));Best for: Frequent insertions/deletions at head/tail, implementing Deque.
import java.util.LinkedList;
LinkedList<Integer> ll = new LinkedList<>();// ─── 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)Best for: DFS, backtracking, expression evaluation, undo operations.
⚠️ PreferDeque<Integer> stack = new ArrayDeque<>()overStack<>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<>();// 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)// 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();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 comparatorpq.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)// 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]);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// ─── 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)// 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()];
}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
ArrayDequeoverLinkedListas a queue — no node allocation overhead.
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 arrayset.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)// 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;
}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.
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());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)// 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); // ≥ targetBest 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// ─── 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)// 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);
}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 orderSame methods as HashMap. Key extras:
removeEldestEntry, access-order mode.
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());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)// 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);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();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();| 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 |
| 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
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.ArrayDequeis always preferred overStackandLinkedListas 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 thanArrayList<ArrayList<Integer>>.
Java Thread-Safe Collections — Complete Reference
Table of Contents
Concurrency Overview
Two Approaches to Thread Safety
Non-Thread-Safe → Thread-Safe Equivalents
ArrayListCopyOnWriteArrayListArrayListCollections.synchronizedList()HashSetCopyOnWriteArraySetHashSetCollections.synchronizedSet()TreeSetConcurrentSkipListSetHashMapConcurrentHashMapTreeMapConcurrentSkipListMapHashMapCollections.synchronizedMap()LinkedList(queue)ConcurrentLinkedQueueArrayDequeConcurrentLinkedDequePriorityQueuePriorityBlockingQueueStackConcurrentLinkedDequeLocking Strategies
synchronizedon entire objectVector,HashtableConcurrentHashMap< Java 8ConcurrentHashMap≥ Java 8,AtomicIntegerCopyOnWriteArrayListLinkedBlockingQueueConcurrentSkipListMap/SetThread-Safe List
CopyOnWriteArrayList
Thread-safe counterpart of
ArrayList. Every write creates a fresh copy of the underlying array. Reads are always lock-free.Best for: Read-heavy workloads (event listeners, observer lists, config snapshots).
Avoid when: Writes are frequent — each write is O(n).
Most Used Methods
Concurrency Patterns
Vector (Legacy)
Synchronized version of
ArrayList— every method acquires the intrinsic lock. Largely replaced byCopyOnWriteArrayListandCollections.synchronizedList().synchronizedList Wrapper
Wraps any
Listwith a mutex. Simpler thanCopyOnWriteArrayListfor write-heavy lists.Thread-Safe Stack
ConcurrentLinkedDeque as Stack
There is no dedicated thread-safe
Stackinjava.util.concurrent. UseConcurrentLinkedDeque.Thread-Safe Queue & Deque
ConcurrentLinkedQueue
Lock-free, unbounded FIFO queue based on Michael-Scott non-blocking algorithm. Best general-purpose concurrent queue.
Best for: Producer-consumer with multiple threads, task queues, work-stealing.
Most Used Methods
Concurrency Patterns
ConcurrentLinkedDeque
Lock-free, unbounded double-ended queue.
LinkedBlockingQueue
Optionally-bounded blocking queue backed by linked nodes. Separate head/tail locks = higher throughput than
ArrayBlockingQueuefor asymmetric producer-consumer loads.Best for: Classic producer-consumer with blocking behavior,
ThreadPoolExecutorwork queues.Most Used Methods
Concurrency Patterns
ArrayBlockingQueue
Bounded blocking queue backed by a fixed array. Single lock for both head and tail — simpler but lower throughput than
LinkedBlockingQueueunder high concurrency.Best for: Fixed-size bounded buffers, rate-limiting, backpressure.
PriorityBlockingQueue
Unbounded blocking priority queue. Blocks only on
take()when empty. Never blocks onput()/offer().Best for: Priority-based task scheduling, Dijkstra's in multi-threaded context.
LinkedBlockingDeque
Optionally-bounded blocking double-ended queue. Supports blocking operations on both ends.
SynchronousQueue
Zero-capacity handoff queue. Each
put()blocks until another thread callstake(), and vice versa. No buffering — direct thread-to-thread transfer.Best for: Direct handoff patterns,
Executors.newCachedThreadPool()work queue.DelayQueue
Unbounded blocking queue where elements become available only after their delay has expired. Elements must implement
Delayed.Best for: Scheduled task execution, cache expiration, retry-after mechanisms.
Thread-Safe Set
CopyOnWriteArraySet
Thread-safe
Setbacked by aCopyOnWriteArrayList. Every write copies the whole array.Best for: Small sets with rare writes (subscriber lists, whitelist/allowlist).
ConcurrentSkipListSet
Thread-safe, sorted
Setequivalent ofTreeSet. Based on a skip list (probabilistic balanced structure). Lock-free for most operations.Best for: Sorted sets with concurrent access, range queries in multi-threaded code.
Most Used Methods
Concurrency Pattern
synchronizedSet Wrapper
Thread-Safe Map
ConcurrentHashMap
⭐ The most important concurrent collection in Java. Lock-free reads (via
volatile), fine-grained CAS writes per bucket. ReplacedHashtablecompletely in modern Java.Best for: Concurrent caches, frequency counters, shared state maps in any multi-threaded app.
Most Used Methods
Concurrency Patterns
ConcurrentSkipListMap
Thread-safe sorted
Mapequivalent ofTreeMap. Lock-free, based on skip lists.Best for: Sorted concurrent maps, time-series data, range queries across threads.
Most Used Methods
Concurrency Pattern
Hashtable (Legacy)
The original thread-safe map — every method locks on the entire object. Entirely superseded by
ConcurrentHashMap.synchronizedMap Wrapper
Atomic Variables
Atomic types use CPU-level Compare-And-Swap (CAS) — no locks, no blocking, very fast.
AtomicInteger / AtomicLong
Most Used Methods
Concurrency Patterns
AtomicReference
Atomic reference to any object. Enables lock-free updates to shared objects.
Concurrency Pattern
AtomicBoolean
Non-Thread-Safe → Thread-Safe Migration
Drop-in Replacements
Common Mistakes to Avoid
Concurrency Quick-Pick Guide
ConcurrentHashMapConcurrentHashMap.merge()ConcurrentHashMap.computeIfAbsent()ConcurrentSkipListMapConcurrentHashMap.newKeySet()ConcurrentSkipListSetCopyOnWriteArrayListConcurrentLinkedQueueLinkedBlockingQueueArrayBlockingQueuePriorityBlockingQueueDelayQueueSynchronousQueueConcurrentLinkedDequeLinkedBlockingDequeLongAdder(striped)AtomicInteger/AtomicLongAtomicBoolean.compareAndSet()AtomicReferenceLinkedHashMap+synchronizedorConcurrentHashMap+ custom evictionCollections.synchronized*()+ manual lock for iterationComplexity & Locking Cheat Sheet
Time Complexity
*
ConcurrentHashMap.size()is an approximation under concurrent modification.Locking Behavior
ConcurrentHashMapConcurrentSkipListMap/SetCopyOnWriteArrayList/SetConcurrentLinkedQueue/DequeLinkedBlockingQueueArrayBlockingQueuePriorityBlockingQueueSynchronousQueueHashtableVectorCollections.synchronized*AtomicInteger/Long/Reference