1. Java Collections Overview
Types of Collections:
- List:
- Implementation:
ArrayList, LinkedList.
- Use Case: Dynamic arrays, iteration.
- Time Complexity:
- Access:
O(1) (ArrayList), O(n) (LinkedList).
- Insert/Delete:
O(n) (ArrayList), O(1) (LinkedList for head/tail).
- Set:
- Implementation:
HashSet, TreeSet.
- Use Case: Unique elements.
- Time Complexity:
- HashSet: Add/Delete/Search →
O(1) (average), O(n) (worst case).
- TreeSet: Add/Delete/Search →
O(log n).
- Map:
- Implementation:
HashMap, TreeMap.
- Use Case: Key-value pairs.
- Time Complexity:
- HashMap: Insert/Search/Delete →
O(1) (average), O(n) (worst case).
- TreeMap: Insert/Search/Delete →
O(log n).
🌳 1. Tree-Specific Collections & Patterns
java
CopyEdit
// 🧱 Tree Node (Binary Tree)
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
// 📍 BFS Traversal — Level Order (uses Queue)
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
// 🧗 DFS Traversal — Preorder/Postorder/Inorder (use Stack or Recursion)
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
// process node
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
// 🧮 TreeMap — Sorted Map (Red-Black Tree internally)
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three"); // Sorted by key
treeMap.firstKey(); // Min
treeMap.lastKey(); // Max
// 🧮 TreeSet — Sorted Set (No duplicates, Red-Black Tree)
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.add(1);
treeSet.contains(5);
treeSet.higher(3); // Smallest > 3
// 📘 PriorityQueue — Min or Max Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap.offer(1);
minHeap.poll(); // Removes min
// 🔁 LinkedList as Deque (for Zigzag level order)
Deque<TreeNode> deque = new LinkedList<>();
deque.addFirst(node); // Acts like Stack
deque.addLast(node); // Acts like Queue
// 📝 Map<TreeNode, Integer> — For memoizing subtree info
Map<TreeNode, Integer> memo = new HashMap<>();
🔗 2. Graph-Specific Collections & Patterns
java
CopyEdit
// 📍 Graph using Adjacency List
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.putIfAbsent(1, new ArrayList<>());
graph.get(1).add(2); // Edge from 1 to 2
// 🔁 DFS using Stack
Set<Integer> visited = new HashSet<>();
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited.contains(node)) continue;
visited.add(node);
for (int nei : graph.getOrDefault(node, new ArrayList<>())) {
stack.push(nei);
}
}
// 🔁 DFS (recursive)
void dfs(int node, Set<Integer> visited) {
if (!visited.add(node)) return;
for (int nei : graph.getOrDefault(node, new ArrayList<>())) {
dfs(nei, visited);
}
}
// 🚎 BFS using Queue
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int nei : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(nei)) {
visited.add(nei);
queue.offer(nei);
}
}
}
// 🧱 Edge list or weighted graph (for Dijkstra)
class Pair {
int node, weight;
Pair(int node, int weight) {
this.node = node; this.weight = weight;
}
}
Map<Integer, List<Pair>> weightedGraph = new HashMap<>();
weightedGraph.computeIfAbsent(0, k -> new ArrayList<>()).add(new Pair(1, 5));
// 🛣️ PriorityQueue for Dijkstra’s Algorithm
PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
// 🧪 Union-Find (Disjoint Set)
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // Path compression
return parent[x];
}
void union(int a, int b) {
parent[find(a)] = find(b);
}
🛠️ Utility Java Collections Patterns
java
CopyEdit
// 🔢 Count frequency of elements
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
// 📋 Grouping elements
Map<Integer, List<String>> map = new HashMap<>();
map.computeIfAbsent(3, k -> new ArrayList<>()).add("abc");
// 🔁 Iterate Map
for (Map.Entry<Integer, List<String>> entry : map.entrySet()) {
int key = entry.getKey();
List<String> valList = entry.getValue();
}
Time Complexity Summary
Tree Collections
- Binary Tree:
- Binary Search Tree (BST):
- Insert/Delete/Search: Avg
O(log n), Worst O(n)
- AVL Tree:
- Insert/Delete/Search:
O(log n)