ArrayList / Dynamic Array

📋 Quick Reference

Property	Value
Type	Sequential, indexed collection
Access	O(1) random access by index
Insert/Delete	O(n) - requires shifting elements
Append	O(1) amortized (O(n) when resizing)
Memory	Contiguous block, cache-friendly
Best For	Random access, iteration, append-heavy workloads

One-liner: Dynamic array that grows automatically when full, providing O(1) index access.

🎮 Interactive Visualizer

Watch how ArrayList handles operations including the automatic resize when capacity is exceeded:

ArrayList Operations
Get: O(1)Add: O(1)*
1 / 13
Initialize ArrayList with capacity 4. Auto-grows when full (amortized O(1) add).
Best for:Random access, iteration, appending elements
Avoid:Frequent inserts/removes at beginning (use LinkedList or ArrayDeque)
size: 0
capacity: 4
load: 0%
📦
Resize visualization will appear here when array becomes full
Internal Array (capacity: 4)
[0]
[1]
[2]
[3]
Pseudocode
1add(value):
2  if size == capacity:
3    resize(capacity * 2)
4  array[size] = value
5  size++
6 
7add(index, value):
8  shift elements right
9  array[index] = value
10  size++
11 
12get(index):
13  return array[index]  // O(1)
14 
15remove(index):
16  shift elements left
17  size--
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Used
Used
Empty
Empty
Active
Active
Shifted
Shifted
P · [ ] · R
Loading visualizer...

Try these operations:

Add elements until resize triggers (capacity doubles)
Insert at index 0 - see all elements shift right
Remove from middle - see elements shift left
Access by index - instant O(1) operation

🔧 Key Operations

Creating

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

Adding Elements

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

Accessing

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

Removing

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

Iteration

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

📊 Complexity Analysis

Operation	Time	Notes
`get(i)`	O(1)	Direct array access
`set(i, e)`	O(1)	Direct array access
`add(e)`	O(1)*	*Amortized - O(n) when resize needed
`add(i, e)`	O(n)	Shifts elements right
`remove(i)`	O(n)	Shifts elements left
`contains(e)`	O(n)	Linear search
`size()`	O(1)	Stored as field

Resize Strategy

Capacity doubles: 10 → 20 → 40 → 80 → 160 → ...

Growth factor = 1.5x (in some implementations)
New capacity = oldCapacity + (oldCapacity >> 1)

✅ When to Use ArrayList

Good Use Cases

Random access needed - get/set by index frequently
Mostly appending - add to end is O(1) amortized
Iteration-heavy - cache-friendly memory layout
Known size - pre-size to avoid resizing

Avoid When

Frequent insert/delete at front - use ArrayDeque or LinkedList
Frequent insert/delete in middle - consider LinkedList
Need thread safety - use CopyOnWriteArrayList or synchronize
Primitive types - boxing overhead; use primitive arrays or specialized libs

⚠️ Common Pitfalls

1. ConcurrentModificationException

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

2. Forgetting Initial Capacity

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

3. Sublist Gotcha

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

🎤 Interview Tips

Q: When would you choose ArrayList over LinkedList?

"

Almost always. ArrayList has O(1) random access, better cache locality, and lower memory overhead. LinkedList only wins for frequent insertions/deletions at known positions with an iterator, which is rare.

Q: What happens when ArrayList is full?

"

It creates a new array ~1.5x larger, copies all elements, then discards the old array. This is O(n) but happens infrequently enough that add() is O(1) amortized.

Q: How would you make ArrayList thread-safe?

"

Options: Collections.synchronizedList(list), CopyOnWriteArrayList (for read-heavy), or external synchronization. ConcurrentHashMap has no direct List equivalent.

Previous: Part 0: Series Overview

Next: Part 2: LinkedList

Visualizer: ArrayList from @tomaszjarosz/react-visualizers