ArrayList | Engineering Interview Kit

TL;DR

ArrayList is a resizable-array implementation of the List interface.
It provides $O(1)$ fast random access via index.
Inserting/deleting in the middle of the list is slow $O(n)$ because elements must be shifted.
Not thread-safe.

Concept

Under the hood, an ArrayList is backed by a standard Java array (Object[]). Standard arrays have a fixed size. ArrayList solves this by automatically creating a new, larger array and copying elements over when the current array gets full.

Resizing Mechanism

The default initial capacity is 10.
When the array is full and a new element is added, it typically grows by 50% (capacity = oldCapacity + (oldCapacity >> 1)).
The old array is garbage collected.

Examples

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) {
        // You can specify initial capacity to avoid resizing overhead
        List<String> cities = new ArrayList<>(20);
        
        // O(1) appending to the end
        cities.add("New York"); 
        cities.add("London");
        cities.add("Tokyo");
        
        // O(1) random access
        String myCity = cities.get(1); // "London"
        
        // O(n) insertion in the middle (Tokyo has to shift right)
        cities.add(1, "Paris"); 
        
        // O(n) removal from the middle (Tokyo has to shift left)
        cities.remove(1); 
        
        System.out.println(cities);
    }
}

Interview Questions

Q: When should you use ArrayList over LinkedList?
A: Use ArrayList when you need fast random access to elements (using get(index)), and when your modifications (adds/removes) happen mostly at the end of the list. ArrayList has excellent cache locality because arrays are stored in contiguous memory blocks.

Q: What is the time complexity of add() in an ArrayList?
A: Most of the time, appending to the end is $O(1)$ amortized. However, in the exact moment the backing array runs out of space, the array must be resized. During a resize operation, the complexity becomes $O(n)$ because all elements must be copied to the new, larger array.