Choosing the Right Collection

Decision Framework

Choosing the right collection is one of the most impactful design decisions. Use this framework:

Step 1: What is the primary access pattern?

• Indexed access → List
• Key-value lookup → Map
• Uniqueness → Set
• Ordering (FIFO/LIFO/priority) → Queue/Deque/Stack

Step 2: What performance do you need?

• O(1) lookup → HashMap, HashSet, ArrayDeque
• O(log n) sorted → TreeMap, TreeSet
• O(n) scan → any collection

Step 3: What ordering guarantees?

• No ordering → HashMap, HashSet
• Insertion order → LinkedHashMap, LinkedHashSet
• Sorted → TreeMap, TreeSet
• Access order (LRU) → LinkedHashMap

import java.util.*;

public class DecisionFramework {
    public static void main(String[] args) {
        // Example: Counting words in a document
        // Need: key-value pairs, fast lookup by word
        // Choice: HashMap<String, Integer>
        Map<String, Integer> wordCount = new HashMap<>();
        String[] words = "the cat sat on the mat the cat".split(" ");
        for (String w : words) {
            wordCount.merge(w, 1, Integer::sum);
        }
        System.out.println("Word count: " + wordCount);

        // Example: Find unique characters in order
        // Need: unique elements, insertion order
        // Choice: LinkedHashSet
        String text = "programming";
        Set<Character> uniqueOrdered = new LinkedHashSet<>();
        for (char c : text.toCharArray()) {
            uniqueOrdered.add(c);
        }
        System.out.println("Unique ordered: " + uniqueOrdered);

        // Example: Recently accessed items (LRU)
        // Need: access order, bounded size
        // Choice: LinkedHashMap with accessOrder=true
        LinkedHashMap<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
                return size() > 3;
            }
        };
        lru.put("a", 1); lru.put("b", 2); lru.put("c", 3);
        lru.get("a"); lru.put("d", 4);
        System.out.println("LRU: " + lru); // {c=3, a=1, d=4}

        // Example: Process tasks by priority
        // Need: priority ordering
        // Choice: PriorityQueue
        PriorityQueue<String> tasks = new PriorityQueue<>();
        tasks.offer("Low priority");
        tasks.offer("High priority");
        tasks.offer("Medium priority");
        System.out.println("Next task: " + tasks.poll()); // High priority
    }
}

Quick reference:

• Need fast lookup? → HashMap
• Need sorted? → TreeMap or TreeSet
• Need queue? → ArrayDeque or PriorityQueue
• Need indexed access? → ArrayList
• Need uniqueness with order? → LinkedHashSet

Common Scenarios

Real-world collection selection patterns:

import java.util.*;

public class CommonScenarios {
    public static void main(String[] args) {
        // Scenario 1: Cache / Lookup Table
        // Use: HashMap
        Map<String, Object> cache = new HashMap<>();

        // Scenario 2: Duplicate-free collection with order
        // Use: LinkedHashSet
        List<String> input = Arrays.asList("c", "a", "b", "a", "c");
        Set<String> uniqueOrdered = new LinkedHashSet<>(input);
        System.out.println("Unique ordered: " + uniqueOrdered); // [c, a, b]

        // Scenario 3: Sorted unique elements
        // Use: TreeSet
        TreeSet<Integer> sorted = new TreeSet<>(Arrays.asList(5, 3, 1, 4, 2));
        System.out.println("Sorted: " + sorted); // [1, 2, 3, 4, 5]

        // Scenario 4: Stack operations
        // Use: ArrayDeque
        Deque<String> stack = new ArrayDeque<>();
        stack.push("a"); stack.push("b"); stack.push("c");
        System.out.println("Pop: " + stack.pop()); // c

        // Scenario 5: Queue / BFS
        // Use: ArrayDeque
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(1); queue.offer(2); queue.offer(3);
        System.out.println("Poll: " + queue.poll()); // 1

        // Scenario 6: Priority scheduling
        // Use: PriorityQueue
        PriorityQueue<int[]> jobs = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[1])
        );
        jobs.offer(new int[]{1, 5}); // [id, priority]
        jobs.offer(new int[]{2, 1});
        jobs.offer(new int[]{3, 3});
        System.out.println("Next job: " + Arrays.toString(jobs.poll())); // [2, 1]

        // Scenario 7: Frequency counting
        // Use: HashMap with merge()
        String text = "hello world hello java world hello";
        Map<String, Integer> freq = new HashMap<>();
        for (String word : text.split(" ")) {
            freq.merge(word, 1, Integer::sum);
        }
        System.out.println("Frequency: " + freq);

        // Scenario 8: Group by key
        // Use: HashMap + List
        List<String> names = Arrays.asList("Alice", "Bob", "Anna", "Bill", "Charlie");
        Map<Character, List<String>> grouped = new HashMap<>();
        for (String name : names) {
            grouped.computeIfAbsent(name.charAt(0), k -> new ArrayList<>()).add(name);
        }
        System.out.println("Grouped: " + grouped);

        // Scenario 9: Thread-safe collection
        // Use: Collections.synchronizedList() or ConcurrentHashMap
        List<String> syncList = Collections.synchronizedList(new ArrayList<>());
        Map<String, Integer> concurrentMap = new java.util.concurrent.ConcurrentHashMap<>();
    }
}

Scenario → Collection mapping:

Scenario	Collection
Cache / Lookup	HashMap
Unique + Order	LinkedHashSet
Sorted Unique	TreeSet
Stack	ArrayDeque
Queue / BFS	ArrayDeque
Priority Queue	PriorityQueue
Frequency Count	HashMap + merge()
Group By Key	HashMap + List
LRU Cache	LinkedHashMap
Thread-Safe	ConcurrentHashMap

DSA Patterns and Collection Choices

Many algorithm patterns have specific collection requirements:

import java.util.*;

public class DSAPatterns {
    // Pattern 1: Two Sum - HashMap for O(n) lookup
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{};
    }

    // Pattern 2: Top K - min-heap of size K
    public static List<Integer> topK(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) minHeap.poll();
        }
        return new ArrayList<>(minHeap);
    }

    // Pattern 3: BFS - Queue
    public static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();
        List<Integer> order = new ArrayList<>();
        queue.offer(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        return order;
    }

    // Pattern 4: DFS - Stack (or recursion)
    public static List<Integer> dfs(Map<Integer, List<Integer>> graph, int start) {
        Deque<Integer> stack = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();
        List<Integer> order = new ArrayList<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (visited.contains(node)) continue;
            visited.add(node);
            order.add(node);
            for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
        return order;
    }

    // Pattern 5: Sliding Window - Deque
    public static int[] slidingWindowMax(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println("Two Sum: " + Arrays.toString(twoSum(new int[]{2,7,11,15}, 9)));
        System.out.println("Top K: " + topK(new int[]{3,1,5,12,2}, 2));
        System.out.println("Sliding max: " + Arrays.toString(slidingWindowMax(new int[]{1,3,-1,-3,5,3,6,7}, 3)));
    }
}

DSA → Collection mapping:

Pattern	Collections Used
Two Sum / Hash Map	HashMap
Top K Elements	PriorityQueue (min-heap of size K)
BFS	ArrayDeque (Queue) + HashSet (visited)
DFS	ArrayDeque (Stack) + HashSet (visited)
Sliding Window Max	ArrayDeque (monotonic deque)
Merge K Sorted	PriorityQueue + indices
Median Stream	Two PriorityQueues (max + min heap)
LRU Cache	LinkedHashMap (access order)