Collection Selection

TL;DR

• Choosing the wrong Collection type can degrade performance from O(1) to O(N), slowing down operations exponentially as data grows.
• Use ArrayList for fast reads by index.
• Use HashSet for fast uniqueness checks and lookups.
• Use HashMap for fast key-value lookups.
• Avoid LinkedList unless you are exclusively adding/removing from the absolute ends of a massive list.

Concept

Performance in collections is entirely about Big-O time complexity.

If you have a list of 1,000,000 blocked IP addresses and you want to check if a user’s IP is blocked:

• Using ArrayList.contains(ip) requires scanning every single element one by one. Worst case, it takes 1,000,000 operations (O(N)).
• Using HashSet.contains(ip) uses a hashing algorithm to instantly jump to the exact memory bucket where the IP should be. It takes 1 operation (O(1)).

Choosing the right collection is often the easiest and most impactful performance optimization you can make.

Examples

import java.util.*;

public class CollectionChoiceDemo {

    // ❌ BAD: Checking for duplicates in a List
    public boolean hasDuplicatesSlow(List<String> userEmails) {
        List<String> seen = new ArrayList<>();
        for (String email : userEmails) {
            // seen.contains() gets slower and slower as the list grows!
            if (seen.contains(email)) return true;
            seen.add(email);
        }
        return false;
    }

    // ✅ GOOD: Checking for duplicates using a Set
    public boolean hasDuplicatesFast(List<String> userEmails) {
        Set<String> seen = new HashSet<>();
        for (String email : userEmails) {
            // seen.contains() is virtually instant, regardless of size!
            if (!seen.add(email)) return true; 
        }
        return false;
    }
}

Interview Questions

Q: Why is ArrayList almost always preferred over LinkedList in modern Java?
A: A LinkedList consists of disjointed node objects scattered across the heap, connected by pointers. Iterating through it causes massive “CPU Cache Misses” because the CPU has to constantly fetch non-contiguous memory blocks.
An ArrayList is backed by a continuous array in memory. The CPU fetches contiguous blocks of memory extremely efficiently (Cache Locality). Even though inserting into the middle of an ArrayList is technically O(N) because it has to shift elements, the CPU handles this memory shift so fast that ArrayList still heavily outperforms LinkedList in real-world benchmarks for almost all operations.

Q: When would you use a TreeMap instead of a HashMap?
A: A HashMap stores items in random hash buckets, offering O(1) lookup time, but destroys any ordering.
A TreeMap uses a Red-Black Tree to keep all keys strictly sorted (e.g., alphabetically). It is slower (O(log N) for lookups), but you must use it if you need to fetch data in a sorted order, or if you need to perform range queries (e.g., map.subMap("A", "C") to get all keys starting with A and B).