🟢 Junior Level

Short answer: In the vast majority of cases, use ArrayList.

Exceptions for LinkedList: (1) Removal via iterator in lists with 100k+ elements, where removeIf() (Java 8+) cannot be used. (2) Specialized data structures (LRU cache based on doubly-linked list).

// ✅ 99% of the time:
List<String> list = new ArrayList<>();

// ❌ LinkedList — don't use without a reason
List<String> list = new LinkedList<>();

The only reason for LinkedList:

• Very large list (millions of elements)
• And you need to remove elements via iterator during traversal

For queue/stack use ArrayDeque:

// ❌ LinkedList as queue
Deque<String> queue = new LinkedList<>();

// ✅ ArrayDeque (faster!)
Deque<String> queue = new ArrayDeque<>();

---

🟡 Middle Level

ArrayList: when to use

// ✅ Random access by index
list.get(100);  // O(1) — instant

// ✅ Iteration (traversing all elements)
for (String s : list) { ... }  // Fast (cache locality)

// ✅ Appending to end
list.add(e);  // O(1)* — amortized

// ✅ If size is known
ArrayList<String> list = new ArrayList<>(10000);
// → No resizes

LinkedList: when (rarely) to use

// ⚠️ The only case:
// 1. Huge list (100,000+ elements)
// 2. Frequent removals VIA ITERATOR
// 3. During traversal

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (shouldRemove(it.next())) {
        it.remove();  // O(1) for LinkedList, O(n) for ArrayList
    }
}

// BUT! In Java 8+ better to use:
list.removeIf(this::shouldRemove);  // O(n) for both

ArrayDeque: for queues and stacks

// Stack (LIFO)
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.pop();

// Queue (FIFO)
Deque<String> queue = new ArrayDeque<>();
queue.offer("A");
queue.poll();

// → Faster than LinkedList, less memory

Practical comparison

Scenario	ArrayList	LinkedList	ArrayDeque
Many reads	✅	❌	N/A
Appending	✅	✅	✅
Insert at start	❌	✅	✅
Delete by index	❌	❌	N/A
Delete via iterator	❌	✅	N/A
Memory	✅	❌	✅
GC pressure	✅	❌	✅

---

🔴 Senior Level

Cache Locality — the main argument

CPU Cache Lines: 64 bytes
Cache line — minimum memory block CPU loads from RAM to cache. Even if you need 1 byte, CPU loads all 64 bytes around it. So adjacent data in array is "free".

ArrayList:
  [ref1][ref2][ref3][ref4][ref5][ref6][ref7][ref8]
  → One read → 8 refs in L1 cache
  → Next 7 elements = 0 latency!

LinkedList:
  [Node1]......[Node2]......[Node3]
     ↓             ↓             ↓
  RAM access: 100+ cycles EACH
  → Cache miss on EVERY element!

System.arraycopy vs Node Creation

// ArrayList.add(0, e):
// → System.arraycopy() → SIMD instructions
// → 1000 elements → ~1 μs

// LinkedList.add(0, e):
// → new Node() → heap allocation
// → 3 refs (item, next, prev)
// → 1000 elements → ~5 μs + GC overhead

// ArrayList is faster up to ~10-20k elements!
// (Based on JMH benchmarks on modern JVMs. Exact threshold depends on CPU, JVM version and access pattern.)

GC Pressure Deep Dive

LinkedList: 1M elements
  → 1M Node objects
  → 32 MB overhead only
  → Minor GC: scan 1M objects
  → STW pauses!

ArrayList: 1M elements
  → 1 Object[] array
  → 4 MB
  → GC: one ref → instantly

removeIf optimization

// ❌ Manual removal via iterator
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    if (condition(it.next())) {
        it.remove();  // O(n) for ArrayList (shift each time)
    }
}

// ✅ removeIf (Java 8+)
list.removeIf(e -> condition(e));
// → First finds all to remove (O(n))
// → Then ONE shift (O(n))
// → Total: O(n) instead of O(n²)!

When ArrayList also loses

// Frequent insertions at START of large list (> 100k elements)
// ArrayList: shift 100k elements each time

// Solution:
// 1. ArrayDeque (if insertion at both ends)
// 2. Or two ArrayLists (head + tail)
// 3. Or rethink architecture

Production Experience

Real case #1: LinkedList → ArrayList

• Log: 500,000 lines in LinkedList
• Memory: 800 MB
• Iteration: 5 seconds
• Solution: ArrayList
• Result: 80 MB, 100 ms (50x speedup!)

Real case #2: LinkedList as queue

• Message queue: LinkedList
• GC: every 2 seconds (Node creation)
• Solution: ArrayDeque
• Result: GC once per minute

Best Practices

1. ArrayList — 99% of cases
2. ArrayDeque — queues/stacks
3. removeIf() instead of iteration with removal
4. ensureCapacity() for known size
5. Avoid LinkedList without good reason
6. Cache Locality > algorithmic complexity
7. GC pressure matters in collection choice

Summary for Senior

• ArrayList — default choice (cache locality)
• LinkedList — anti-pattern for modern CPUs
• ArrayDeque — for stacks and queues
• removeIf() > iteration with removal
• Cache Locality > Big O in practice
• GC Pressure — hidden cost of LinkedList
• System.arraycopy faster than creating Node
• Valhalla (future): Inline Types will widen the gap

---

🎯 Interview Cheat Sheet

Must know:

• ArrayList — default choice for 99% scenarios
• Cache locality > algorithmic complexity: CPU loads 64-byte cache line at once, getting 8-16 refs “for free”
• System.arraycopy() = SIMD instructions — faster than new Node() for lists up to 10-20k elements
• removeIf() is better than manual iterator removal: one pass + one shift = O(n) instead of O(n²)
• ArrayDeque — for stacks and queues (faster than LinkedList, less memory, no GC pressure)
• GC Pressure: LinkedList 1M elements = 32 MB garbage, ArrayList = 0 new objects
• ensureCapacity() saves 30+ resizes when size is known
• Real case: replacing LinkedList → ArrayList gave 50-200x speedup and 10x memory reduction

Common follow-up questions:

• When can LinkedList win? — Frequent insertions at START of list >100k elements; removal via iterator in huge lists
• What is cache line and why it matters? — 64-byte block, CPU loads it entirely; ArrayList uses it, LinkedList — no
• Why removeIf() faster than iterator loop? — First finds all elements to remove, then ONE array shift
• When does ArrayList also lose? — Frequent insertions at start of large list (>100k) — then ArrayDeque

Red flags (NOT to say):

• ❌ “LinkedList is better for frequent insertions” — ArrayList is faster up to 10-20k elements thanks to SIMD
• ❌ “Use LinkedList for queue” — ArrayDeque is always better (faster, less memory)
• ❌ “Big O determines performance” — cache locality and constants matter more in practice
• ❌ “Iterator removal is normal practice” — use removeIf() in Java 8+

Related topics:

• [[What is the difference between ArrayList and LinkedList]]
• [[What is the time complexity of operations in ArrayList]]
• [[What is the time complexity of operations in LinkedList]]
• [[What is Deque]]
• [[What is Vector and how does it differ from ArrayList]]