🟢 Junior Level

Time complexity — how long an operation takes depending on the list size.

Operation	Complexity	Explanation
get(index)	O(1)	Instant, access by index
add(e)	O(1)*	Constant time on average. When array is full, resize occurs (copying all elements), but this happens rarely.
add(index, e)	O(n)	Need to shift elements
remove(index)	O(n)	Need to shift elements
contains(e)	O(n)	Linear search
size()	O(1)	Size is stored

Example:

ArrayList<String> list = new ArrayList<>();

list.add("A");        // O(1) — fast
list.get(0);          // O(1) — instant!
list.add(0, "B");     // O(n) — shift all elements
list.remove(0);       // O(n) — shift all elements
list.contains("A");   // O(n) — iteration

---

🟡 Middle Level

Amortized O(1) for add(e)

Amortized complexity = if you perform N operations, total time = O(N), so one operation on average = O(1). A single operation may take O(n) during resize, but this happens rarely (every ~1.5x fill).

// add(e) = O(1) on average, but sometimes O(n)

// Why?
// 1. Space available in array → O(1)
// 2. Array full → resize (O(n))

// Resize: new array × 1.5
// capacity: 10 → 15 → 22 → 33 → 49 → ...

// Amortized complexity:
// N additions = O(N) total
// One addition = O(1) on average

Operation details

// get(index): O(1)
// → array[index] → instant

// add(e): O(1)* amortized
// → If space: array[size++] = e
// → If no: resize + arraycopy

// add(index, e): O(n)
// → System.arraycopy(index, index+1, size-index)
// → array[index] = e
// → Native code → fast!

// remove(index): O(n)
// → System.arraycopy(index+1, index, size-index-1)
// → array[size-1] = null (for GC)

// contains(e): O(n)
// → for (int i = 0; i < size; i++)
//     if (element.equals(e)) return true;

Bulk operations (Java 8+)

// removeIf(predicate): O(n)
// → One pass to find elements
// → One shift to remove
// → Instead of O(n²) in loop!

// replaceAll(operator): O(n)
// → Direct array manipulation
// → No iterator creation

// removeAll(collection): O(n × m)
// → For each element checks collection

Optimizations

// 1. ensureCapacity(size)
// → Eliminate resizes if size is known
// → new ArrayList<>(1_000_000);

// 2. trimToSize()
// → Shrink array to actual size
// → After bulk removal

// 3. Sorted ArrayList
// → Collections.binarySearch() → O(log n)
// → Instead of O(n) contains!

---

🔴 Senior Level

System.arraycopy Deep Dive

ArrayList.remove(0):
  → System.arraycopy(src, 1, dest, 0, size-1)

Under the hood:
  → JVM intrinsic — method that JVM replaces with optimized machine instruction
  → memmove — standard C memory copy function
  → SIMD — parallel processing at CPU level
  → Moves 64 bytes per clock (cache line)

→ O(n) theoretically, but constant is VERY SMALL
→ For 1000 elements: ~1 μs
→ Faster than O(1) LinkedList with allocation!

Resize: why 1.5x?

// Some C++ std::vector implementations use 2x (libstdc++ GCC), others use 1.5x or 2x (libc++ Clang).
// Java ArrayList: 1.5x

// Why?
// 1.5x allows memory reuse:
//   10 → 15 (freed 0-9)
//   15 → 22 (freed 0-14)
//   22 → 33 (0-21 still busy, but 0-9 free!)
//   → Can reuse block 0-9

// 2x doesn't allow:
//   10 → 20 (0-9 free)
//   20 → 40 (0-19 busy)
//   → Block 0-9 too small for 40
//   → Heap fragmentation!

Memory Bandwidth Limit

For large lists (> 1M):
  add(e) limited by RAM write speed
  → ~25 GB/s for DDR4
  → 1M refs (8 MB) → ~0.3 ms

This is physical limit!

CPU Pipeline and Branch Prediction

Branch prediction — CPU predicts condition result (if) and preloads next instructions. If prediction is correct — code executes without delays. Pipeline — CPU processes multiple instructions simultaneously at different stages.

// contains(e): linear search
for (int i = 0; i < size; i++) {
    if (array[i].equals(e)) return true;
}

// CPU branch predictor:
// → While searching, predicts "not found"
// → Pipeline not interrupted
// → Almost O(n) without penalties

Production Experience

Real case: ensureCapacity saved 30 resizes

// ❌ Without ensureCapacity
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(data[i]);  // ~30 resizes!
}

// ✅ With ensureCapacity
ArrayList<String> list = new ArrayList<>(1_000_000);
for (int i = 0; i < 1_000_000; i++) {
    list.add(data[i]);  // 0 resizes!
}

// Result: -15% time

Best Practices

1. get(index) = O(1) — use for frequent reads
2. add(e) = O(1)* amortized — resizes are rare
3. add(0, e) = O(n) — but fast thanks to SIMD
4. removeIf() = O(n) — instead of removal loop
5. ensureCapacity() — if size is known
6. binarySearch() = O(log n) — for sorted lists
7. trimToSize() — after bulk removal

Summary for Senior

• get(index) = O(1) — perfect cache locality
• add(e) = O(1)* amortized — resize × 1.5
• add/remove(index) = O(n) — but SIMD speeds it up
• contains = O(n) → binarySearch = O(log n)
• System.arraycopy = native memmove
• 1.5x resize — less fragmentation than 2x
• removeIf = O(n) instead of O(n²)
• ensureCapacity = saves 30+ copies

---

🎯 Interview Cheat Sheet

Must know:

• get(index) = O(1), add(e) = O(1)* amortized, add/remove(index) = O(n)
• Amortized O(1): resize happens rarely (every ~1.5x fill), N additions = O(N) total
• Resize × 1.5 (not 2x) — allows reusing freed memory, less heap fragmentation
• System.arraycopy() = JVM intrinsic → memmove + SIMD — moves 64 bytes per clock, constant is VERY small
• removeIf() = O(n) instead of O(n²) in loop — one pass to find + one shift to remove
• ensureCapacity() saves 30+ resizes when loading 1M elements (-15% time)
• For sorted ArrayList: Collections.binarySearch() = O(log n) instead of O(n) contains
• CPU branch prediction makes linear search nearly penalty-free — pipeline not interrupted

Common follow-up questions:

• What does “amortized O(1)” mean? — Single operation may be O(n) during resize, but O(1) on average over N operations
• Why resize 1.5x not 2x? — 1.5x allows reusing old memory blocks, 2x causes heap fragmentation
• When can contains() be faster than O(n)? — If list is sorted — binarySearch = O(log n)
• Why is System.arraycopy() fast? — Native memmove + SIMD instructions + CPU prefetching

Red flags (NOT to say):

• ❌ “add(e) is always O(1)” — during resize it’s O(n), correct term is “amortized O(1)”
• ❌ “remove(index) = O(n) means it’s slow” — System.arraycopy() is very fast thanks to SIMD
• ❌ “ArrayList is always O(n) for search” — if sorted, binarySearch = O(log n)
• ❌ “2x resize is better because it’s rarer” — 2x causes heap fragmentation and wasted memory

Related topics:

• [[What are the main Collection Framework interfaces]]
• [[What is the time complexity of operations in LinkedList]]
• [[What is the difference between ArrayList and LinkedList]]
• [[When to use ArrayList vs LinkedList]]