ArrayList vs LinkedList

📋 Quick Reference

* Amortized (occasional resize) ** Better cache locality

---

🎮 Interactive Visualizer

Compare how ArrayList and LinkedList handle the same operations:

Loading visualizer...

1. Random access (get) - see ArrayList's O(1) vs LinkedList's traversal
2. Add at front - LinkedList just updates pointers
3. Add at end - both are fast
4. Add in middle - ArrayList shifts, LinkedList traverses then inserts

---

🔧 Internal Structure

ArrayList (Dynamic Array)

Contiguous memory block:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘
  0   1   2   3   4   5   6   7
                      ↑
                    size=5, capacity=8

get(2): Direct calculation → array[2] → O(1)
add("F"): array[5] = "F", size++ → O(1)
add(0, "Z"): Shift all right, then insert → O(n)

LinkedList (Doubly-Linked)

Scattered nodes with pointers:
┌─────────┐    ┌─────────┐    ┌─────────┐
│ prev: ∅ │←──→│ prev    │←──→│ prev    │
│ data: A │    │ data: B │    │ data: C │
│ next    │←──→│ next    │←──→│ next: ∅ │
└─────────┘    └─────────┘    └─────────┘
    ↑                              ↑
   head                           tail

get(2): head→next→next → O(n)
addFirst("Z"): Create node, update head pointer → O(1)
addLast("D"): Create node, update tail pointer → O(1)

---

📊 Detailed Complexity Analysis

Time Complexity

* Amortized O(1), worst case O(n) during resize

Space Complexity

---

✅ When to Use Which

Choose ArrayList When

JAVA(19 lines)
Code
Loading syntax highlighter...

Choose LinkedList When

JAVA(22 lines)
Code
Loading syntax highlighter...

---

🔄 Common Operations Comparison

Adding Elements

JAVA(11 lines)
Code
Loading syntax highlighter...

Removing Elements

JAVA(11 lines)
Code
Loading syntax highlighter...

Iteration Performance

JAVA(20 lines)
Code
Loading syntax highlighter...

---

🧩 Real-World Patterns

Pattern 1: Stack

JAVA(5 lines)
Code
Loading syntax highlighter...

Pattern 2: Queue

JAVA(7 lines)
Code
Loading syntax highlighter...

Pattern 3: Frequent Middle Insertions

JAVA(5 lines)
Code
Loading syntax highlighter...

Pattern 4: LRU Cache

JAVA(16 lines)
Code
Loading syntax highlighter...

---

⚠️ Common Pitfalls

1. Indexed Loop on LinkedList

JAVA(9 lines)
Code
Loading syntax highlighter...

2. Using LinkedList as General-Purpose List

JAVA(7 lines)
Code
Loading syntax highlighter...

3. Not Pre-sizing ArrayList

JAVA(8 lines)
Code
Loading syntax highlighter...

4. Assuming add() is Always Fast

JAVA(6 lines)
Code
Loading syntax highlighter...

---

🎯 Interview Practice

Test your ArrayList vs LinkedList knowledge with 10 curated interview questions:

🎤 List Comparison Interview Mode - Coming Soon

---

🎤 Interview Tips

"

LinkedList when you need O(1) insertions/removals at the front (queue operations), or when using Iterator.remove() frequently. In practice, ArrayList is better 95% of the time due to cache locality and lower memory overhead.

"

ArrayList stores elements contiguously in memory, benefiting from CPU cache prefetching. LinkedList nodes are scattered in memory, causing cache misses on every access.

"

ArrayList: ~4-8 bytes per reference (just the array slot). LinkedList: ~24 bytes per node (object header, prev pointer, next pointer, data reference). For large lists, ArrayList uses 3-6x less memory.

"

ArrayDeque is usually better for queues - it's faster and uses less memory. LinkedList is only useful if you need null elements (ArrayDeque doesn't allow null) or need to remove elements from the middle during iteration.

---

📚 Series Navigation

---