Collections Compared — Key Differences

Interviewers love asking "what's the difference between X and Y?" for Java collections. This page covers every important comparison you need to know.

ArrayList vs LinkedList

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph AL["ArrayList (Dynamic Array)"]
        direction LR
        A0["[0]"] --- A1["[1]"] --- A2["[2]"] --- A3["[3]"] --- A4["[4]"]
    end

    subgraph LL["LinkedList (Doubly Linked)"]
        direction LR
        N0["prev|A|next"] <--> N1["prev|B|next"] <--> N2["prev|C|next"]
    end

    style AL fill:#EFF6FF,stroke:#DBEAFE,color:#1E40AF
    style LL fill:#ECFDF5,stroke:#6EE7B7,color:#1E40AF

Verdict: Use ArrayList 99% of the time. LinkedList's theoretical O(1) insert advantage rarely matters because finding the insert position is still O(n), and ArrayList benefits from CPU cache locality.

HashMap vs Hashtable vs ConcurrentHashMap

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    Q(("Need a Map?"))
    Q -->|"Single thread?"| HM(["HashMap"])
    Q -->|"Multi-threaded?"| CHM(["ConcurrentHashMap"])
    Q -->|"Sorted keys?"| TM(["TreeMap"])
    Q -->|"Insertion order?"| LHM(["LinkedHashMap"])

    style HM fill:#ECFDF5,stroke:#6EE7B7,color:#1E40AF
    style CHM fill:#EFF6FF,stroke:#DBEAFE,color:#1E40AF
    style TM fill:#FEF3C7,stroke:#FCD34D,color:#1E40AF
    style LHM fill:#EFF6FF,stroke:#93C5FD,color:#1E40AF

How ConcurrentHashMap Achieves Concurrency (Java 8+)

    HashMap (single-threaded):
    ┌───┬───┬───┬───┬───┬───┬───┬───┐
    │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │  ← one big array, no protection
    └───┴───┴───┴───┴───┴───┴───┴───┘

    ConcurrentHashMap (Java 8+):
    ┌───┬───┬───┬───┬───┬───┬───┬───┐
    │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │  ← CAS for insert, synchronized per bucket
    └─┬─┴───┴─┬─┴───┴───┴─┬─┴───┴───┘
      │       │           │
      ▼       ▼           ▼
    [node]  [node]      [node→node]   ← only lock the specific bucket being written

• Reads: No locking — uses volatile reads
• Writes: CAS (Compare-And-Swap) for insert, synchronized on the node/bin for collisions
• Size calculation: Distributed counters (not a single counter)

HashMap vs TreeMap vs LinkedHashMap

// TreeMap — sorted by key
TreeMap<String, Integer> tree = new TreeMap<>();
tree.put("banana", 2);
tree.put("apple", 1);
tree.put("cherry", 3);
tree.firstKey();                        // "apple"
tree.subMap("apple", "cherry");         // {apple=1, banana=2}

// LinkedHashMap — insertion order (or access order for LRU)
LinkedHashMap<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 100;  // evict when over 100 entries
    }
};

HashSet vs TreeSet vs LinkedHashSet

Comparable vs Comparator

// Comparable — built into the class (ONE sort order)
public class Employee implements Comparable<Employee> {
    private String name;
    private int salary;

    @Override
    public int compareTo(Employee other) {
        return Integer.compare(this.salary, other.salary);  // natural order: by salary
    }
}

// Comparator — external (MULTIPLE sort orders)
Comparator<Employee> byName = Comparator.comparing(Employee::getName);
Comparator<Employee> bySalaryDesc = Comparator.comparingInt(Employee::getSalary).reversed();
Comparator<Employee> byNameThenSalary = byName.thenComparingInt(Employee::getSalary);

employees.sort(byName);             // sort by name
employees.sort(bySalaryDesc);       // sort by salary descending
employees.sort(byNameThenSalary);   // sort by name, then salary

Iterator vs ListIterator vs Enumeration

fail-fast vs fail-safe (Weakly Consistent)

// Fail-fast — throws ConcurrentModificationException
List<String> list = new ArrayList<>(List.of("A", "B", "C"));
for (String s : list) {
    if (s.equals("B")) list.remove(s);  // EXCEPTION!
}

// Safe alternatives:
// 1. Use Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("B")) it.remove();
}

// 2. Use removeIf (Java 8+)
list.removeIf(s -> s.equals("B"));

// 3. Use CopyOnWriteArrayList (multi-threaded)
List<String> safe = new CopyOnWriteArrayList<>(List.of("A", "B", "C"));
for (String s : safe) {
    if (s.equals("B")) safe.remove(s);  // NO exception — iterates over snapshot
}

Array vs ArrayList

// Array — use for fixed-size, primitive-heavy workloads
int[] scores = new int[1000];  // primitive array, no boxing

// ArrayList — use for dynamic collections
List<Integer> scores = new ArrayList<>();  // autoboxes int → Integer
scores.add(95);
scores.remove(Integer.valueOf(95));

Interview Questions