ArrayList

Classical data structure that is often fast, until it isn't.

Context

An ArrayList is a resizable array backed by a contiguous block of memory.

This layout gives it two major strengths:

• O(1) random access
• excellent cache locality

Appending elements is O(1) amortized:

• O(1) while capacity remains
• O(n) when resizing is required (the entire array is copied)

Its main weakness is structural:

• prepending or removing from the front requires shifting elements
• insertion/removal in the middle is O(n)

ArrayList is fast when writes are append-heavy and indices are stable. It degrades quickly when used like a queue or list of frequent inserts.

Core idea

• Maintain a backing array and a logical size
• Grow the array when capacity is exhausted
• Preserve contiguity by shifting elements on insert/remove
• Trade cheap reads for expensive structural mutations

This is a deliberate design, not a flaw.

Implementation

import java.util.*;

public class ArrayList<T> implements Iterable<T> {
    private int size;
    private T[] elements;
    private int modCount;
    
    @SuppressWarnings("unchecked")
    public ArrayList(int initialCapacity) {
        elements = (T[]) new Object[initialCapacity];
    }
    
    public void append(T element) {
        resizeIfNeeded();
        writeAtIndex(element, size);
    }
    
    public void prepend(T element) {
        resizeIfNeeded();
        System.arraycopy(elements, 0, elements, 1, size);
        writeAtIndex(element, 0);
    }
    
    public void insertAt(T element, int index) {
        assertIndexForInsert(index);
        resizeIfNeeded();
        System.arraycopy(elements, index, elements, index + 1, size - index);
        writeAtIndex(element, index);
    }
    
    public T get(int index) {
        assertIndexForAccess(index);
        return elements[index];
    }
    
    public T removeAt(int index) {
        assertIndexForAccess(index);
        var value = elements[index];
        System.arraycopy(elements, index + 1, elements, index, size - index - 1);
        elements[--size] = null;
        modCount++;
        return value;
    }
    
    public T remove(T element) {
        for (var i = 0; i < size; i++) {
            if (elements[i].equals(element)) {
                return removeAt(i);
            }
        }
        
        return null;
    }
    
    public boolean isEmpty() { return size == 0; }
    
    public int size() { return size; }
    
    @Override
    public ListIterator<T> iterator() { return new ArrayListIterator(); }
    
    private void assertIndexForAccess(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
    }
    
    private void assertIndexForInsert(int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException();
    }
    
    private void resizeIfNeeded() {
        if (elements.length == size) {
            var capacity = elements.length * 3 / 2 + 1;
            elements = Arrays.copyOf(elements, capacity);
        }
    }
    
    public void writeAtIndex(T element, int index) {
        elements[index] = element;
        size++;
        modCount++;
    }
    
    private final class ArrayListIterator implements ListIterator<T> {
        private final int expectedModCount = modCount;
        private int currentIndex = 0;
        
        @Override
        public boolean hasNext() {
            assertNoConcurrentModification();
            return currentIndex < size;
        }    
    
        @Override
        public boolean hasPrevious() {
            assertNoConcurrentModification();
            return currentIndex > 0;
        }       
        
        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            return elements[currentIndex++];
        }
        
        @Override
        public T previous() {
            if (!hasPrevious()) throw new NoSuchElementException();
            return elements[--currentIndex];
        }
        
        @Override
        public int nextIndex() { return currentIndex; }
        
        @Override
        public int previousIndex() { return currentIndex - 1; }
            
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    
        @Override
        public void set(T t) {
            throw new UnsupportedOperationException();
        }
    
        @Override
        public void add(T t) {
            throw new UnsupportedOperationException();
        }    
            
        private void assertNoConcurrentModification() {
            if (expectedModCount != modCount) throw new ConcurrentModificationException();
        }
    }
}