ArrayList
A dynamic array implementation that automatically resizes when needed. Elements are stored in contiguous memory, providing O(1) access by index.
Backing Array
ArrayList uses a regular array internally. When you create an ArrayList, it allocates an array with some initial capacity (typically 10 in Java). Elements are stored starting from index 0.
Size vs Capacity
Size is the number of elements actually stored. Capacity is the length of the backing array. Capacity ≥ Size always. Empty slots exist when Capacity > Size.
Dynamic Resizing
When you add an element and the array is full (size = capacity), ArrayList creates a new array with double the capacity, copies all elements over, then adds the new element.
Element Shifting
To insert at index i, all elements from i to end must shift right. To remove at index i, all elements from i+1 to end must shift left. This is why insert/remove in middle is O(n).
| Operation | Time | Why |
|---|---|---|
| get(index) | O(1) | Direct array access: data[index] |
| set(index, value) | O(1) | Direct array access: data[index] = value |
| addLast(value) | O(1) amortized | Usually O(1), occasionally O(n) when resizing |
| addFirst(value) | O(n) | Must shift all n elements right |
| add(index, value) | O(n) | Must shift n-index elements right |
| removeLast() | O(1) | Just decrement size, no shifting |
| removeFirst() | O(n) | Must shift all n-1 elements left |
| remove(index) | O(n) | Must shift n-index-1 elements left |
Try different operations and watch how ArrayList handles them internally. Toggle between diagram and memory views to see different perspectives.
Java Implementation
public void add(int index, E element) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException();
ensureCapacity(size + 1);
// Shift elements to the right
for (int i = size; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = element;
size++;
}Pseudocode
Empty List Operations
- •
get(0)on empty list → IndexOutOfBoundsException - •
removeFirst()on empty → NoSuchElementException - •
add(0, value)on empty → Works (adds first element)
Boundary Operations
- •
add(size, value)→ Same as addLast - •
add(-1, value)→ IndexOutOfBoundsException - •
add(size+1, value)→ IndexOutOfBoundsException
Resizing Behavior
- • Adding to full array triggers resize
- • New capacity = old capacity × 2
- • All elements copied to new array
Single Element
- •
remove(0)on single element → Empty list - • No shifting needed for single element operations
- • Size becomes 0, but capacity unchanged
Good For
- ✓ Random access by index (get/set)
- ✓ Adding/removing at the end
- ✓ Iterating through all elements
- ✓ When you know the approximate size
Not Good For
- ✗ Frequent insertions at beginning/middle
- ✗ Frequent deletions at beginning/middle
- ✗ When size changes dramatically
- ✗ When memory is very constrained