Junior Level

ArrayList and LinkedList — two implementations of the List interface.

Main difference:

	ArrayList	LinkedList
Structure	Dynamic array	Doubly-linked list
Index read	Fast get(0)	Slow (iteration)
Insert at start	Slow (shift)	Fast
Memory	Low	High (object per element)

Simple rule:

• ArrayList — for most cases ✅
• LinkedList — covers less than 1% of real scenarios. The only practical case: removal via iterator in huge lists (100k+ elements) where removeIf() cannot be used. ❌

Example:

List<String> arrayList = new ArrayList<>();
arrayList.get(0);  // Instant!

List<String> linkedList = new LinkedList<>();
linkedList.get(0);  // Iterates all elements!

Tip: If you need LinkedList as a queue or stack — use ArrayDeque instead. ArrayDeque is 3-10x faster than LinkedList during iteration and 2-5x faster for insert/remove.

---

Middle Level

ArrayList: Dynamic Array

// Inside: Object[] array
// Access: array[index] → O(1)

// Adding:
list.add(e)        // O(1)* amortized
list.add(0, e)     // O(n) array shift
list.remove(0)     // O(n) array shift

// Resize: when full → new array × 1.5
// System.arraycopy() → very fast (SIMD instructions)
// SIMD (Single Instruction, Multiple Data) — CPU copies multiple elements in one clock cycle command.

LinkedList: Doubly-Linked List

// Inside: chain of Node objects
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

// Access:
list.get(0)        // O(n) iteration from start/end
list.add(e)        // O(1) at end
list.add(0, e)     // O(1) at start
list.remove(iterator)  // O(1) if you have the iterator

Comparison

Operation	ArrayList	LinkedList
get(index)	O(1)	O(n)
add(e)	O(1)*	O(1)
add(0, e)	O(n)	O(1)
remove(0)	O(n)	O(1)
contains(e)	O(n)	O(n)
iterator.remove()	O(n)	O(1)
Memory	4-8 bytes/el	24-32 bytes/el

Cache Locality

ArrayList: [A][B][C][D]  ← adjacent in memory
  → CPU loads cache line (64 bytes)
  → A, B, C, D already in L1 cache!
  → Iteration: very fast

LinkedList: [A]...[B]...[C]...[D]  ← scattered
  → Each reference = cache miss
  → Wait from RAM: 100+ CPU cycles
  → Iteration: very slow

When LinkedList?

Only case:
  1. List is HUGE (millions of elements)
  2. Removal VIA ITERATOR during traversal
  3. Cannot replace with removeIf()

In all other cases → ArrayList!

Alternative: ArrayDeque

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

// ✅ ArrayDeque (faster and less memory)
Deque<String> stack = new ArrayDeque<>();

// ArrayDeque:
// → Circular array
// → No Node objects
// → O(1) insert/remove at both ends
// → Better cache locality

---

Senior Level

Memory Footprint Deep Dive

LinkedList Node:
┌─────────────────────────┐
│ Object Header (12 bytes) │
│ item reference (4 bytes) │
│ next reference (4 bytes) │
│ prev reference (4 bytes) │
│ Padding (8 bytes)        │
└─────────────────────────┘
Total: 32 bytes per element!

Figures shown for 64-bit JVM with Compressed Oops (default up to 32 GB heap). Without Compressed Oops, sizes double.

ArrayList:
┌─────────────────────────┐
│ Object[] array           │
│ reference (4 bytes)      │
└─────────────────────────┘
Total: 4 bytes per element!

→ LinkedList is 8x larger!
→ GC pressure: millions of Node objects

Big O Illusion

Theory: LinkedList.add(0, e) = O(1)
Reality: ArrayList.add(0, e) faster for small lists!

Why?
  ArrayList: System.arraycopy() → SIMD instructions
    → 1000 elements → ~1 µs

  LinkedList: new Node() + 3 references
    → Object allocation → GC overhead
    → 1000 elements → ~5 µs

ArrayList wins up to ~10-20k elements!

GC Pressure

LinkedList on removal:
  → Each Node → garbage
  → 1M removals = 1M objects in Young Gen
  → Frequent Minor GC → STW pauses

ArrayList on removal:
  → Nullify reference in array
  → 0 new objects
  → GC works instantly

Vector and Stack — deprecated

// ❌ Vector (synchronized ArrayList)
Vector<String> v = new Vector<>();  // Slow!

// ❌ Stack (inherits from Vector)
Stack<String> s = new Stack<>();  // Double overhead!

// ✅ ArrayList (no synchronization)
List<String> list = new ArrayList<>();

// ✅ ArrayDeque (instead of Stack)
Deque<String> stack = new ArrayDeque<>();

// ✅ CopyOnWriteArrayList (if thread-safety needed)
List<String> threadSafe = new CopyOnWriteArrayList<>();

RandomAccess marker

// ArrayList implements RandomAccess
// LinkedList does NOT implement RandomAccess

// JDK checks this for optimization:
Collections.binarySearch(list, key);
// → If RandomAccess: binary search by index
// → If not: iteration (slower)

// Your code:
if (list instanceof RandomAccess) {
    for (int i = 0; i < list.size(); i++) { ... }  // for-i
} else {
    for (E e : list) { ... }  // foreach/iterator
}

Java 21: SequencedCollection

// List now inherits SequencedCollection
list.getFirst();   // New method!
list.getLast();    // New method!
list.reversed();   // Reverse order (view)

// ArrayList.reversed() → Efficient (array backwards)
// LinkedList.reversed() → Efficient (doubly-linked list)

Production Experience

Real scenario #1: LinkedList killed performance

• Application: 1M elements, frequent iteration
• LinkedList: 10 seconds, 500 MB memory
• ArrayList: 50 ms, 50 MB
• Speedup: 200x!

Real scenario #2: GC Pressure

• LinkedList: 10M removals → 320 MB garbage
• Minor GC every 2 seconds → lag
• ArrayList: 0 garbage → stable

Best Practices

1. ArrayList — default choice (99% of cases)
2. ArrayDeque — instead of LinkedList for queues/stacks
3. Avoid LinkedList due to GC pressure
4. RandomAccess check for loops
5. removeIf() instead of iteration with removal
6. ensureCapacity() if size is known
7. Java 21 → getFirst(), getLast(), reversed()

Senior Summary

• ArrayList = dynamic array, cache-friendly
• LinkedList = doubly-linked list, anti-pattern for CPU
• Memory: ArrayList 8x more compact
• GC: LinkedList creates millions of Node objects
• Big O illusion: O(1) LinkedList often slower than O(n) ArrayList
• ArrayDeque > LinkedList for stacks/queues
• RandomAccess = marker for optimization
• Valhalla (future): Inline Types will widen the gap. Project Valhalla is planned no earlier than Java 23+. Don’t use it in architecture planning yet.

---

Interview Cheat Sheet

Must know:

• ArrayList = dynamic array (Object[]), O(1) index access, cache-friendly
• LinkedList = doubly-linked list (Node with item/next/prev), O(n) access, 32 bytes per element
• Memory: ArrayList ~4 bytes/el vs LinkedList ~32 bytes/el — 8x more
• Cache locality — main reason: ArrayList loads 8 references per cache line, LinkedList — cache miss on every element
• Big O Illusion: LinkedList.add(0,e) = O(1) theoretically, but ArrayList faster up to 10-20k elements thanks to SIMD
• GC Pressure: LinkedList creates millions of Node objects, ArrayList — only nullifying references
• ArrayDeque > LinkedList for stacks and queues — 3-10x faster during iteration
• RandomAccess marker: JDK checks it to choose algorithm (binary search by index vs iteration)

Common follow-up questions:

• When is LinkedList actually justified? — Removal via iterator in 100k+ element lists where removeIf() cannot be used
• Why is ArrayList faster than LinkedList for front insertion? — System.arraycopy() = SIMD instructions, Node allocation is more expensive
• What is GC Pressure? — Frequent Minor GC from millions of Node objects → STW pauses → lag
• Why does ArrayList implement RandomAccess? — So JDK uses optimized algorithms for fast index access

Red flags (DO NOT say):

• “LinkedList is faster for insertion at start” — ArrayList is faster up to 10-20k elements thanks to SIMD
• “LinkedList is more memory efficient” — opposite, 8x more (32 bytes vs 4 bytes per element)
• “Use LinkedList as a queue” — ArrayDeque is faster and uses less memory
• “Big O = real performance” — O(1) LinkedList often slower than O(n) ArrayList due to constants

Related topics:

• [[1. What are the main Collection Framework interfaces]]
• [[4. When to use ArrayList vs LinkedList]]
• [[5. What is the time complexity of operations in ArrayList]]
• [[6. What is the time complexity of operations in LinkedList]]
• [[10. What is Deque]]