Deep Dive (java.util.concurrent) - CopyOnWriteArrayList

"Write once, read everywhere — the list that clones itself on every mutation."

CopyOnWriteArrayList is a thread-safe List that achieves concurrency by creating a new copy of the entire underlying array on every write. This sounds insane, but it's perfect for specific workloads.

---

What is CopyOnWriteArrayList, Really?

The entire implementation can be summarized as:

• Reads: Return data from the current array reference (volatile read, no lock)

• Writes: Lock, copy the entire array, modify the copy, swap the reference

public class CopyOnWriteArrayList<E> implements List<E> {
    
    final transient Object lock = new Object();  // Lock for writes
    private transient volatile Object[] array;    // The data — volatile!
    
    final Object[] getArray() {
        return array;
    }
    
    final void setArray(Object[] a) {
        array = a;  // Volatile write — visible to all threads
    }
}

---

The Core Mechanism — Snapshot Isolation

Key insight: Existing readers continue using the old array (their snapshot). New readers see the new array. No locks, no ConcurrentModificationException, no coordination needed.

---

How add() Works — Clone the World

public boolean add(E e) {
    synchronized (lock) {          // 1. Acquire exclusive write lock
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);  // 2. Copy ENTIRE array (O(n)!)
        es[len] = e;                       // 3. Add new element to copy
        setArray(es);                      // 4. Volatile swap (publish new array)
        return true;
    }
}

set() and remove() — Same Pattern

public E set(int index, E element) {
    synchronized (lock) {
        Object[] es = getArray();
        E oldValue = elementAt(es, index);
        if (oldValue != element) {
            es = es.clone();          // Full copy!
            es[index] = element;
            setArray(es);
        }
        return oldValue;
    }
}

public E remove(int index) {
    synchronized (lock) {
        Object[] es = getArray();
        E oldValue = elementAt(es, index);
        int numMoved = es.length - index - 1;
        Object[] newElements;
        if (numMoved == 0)
            newElements = Arrays.copyOf(es, es.length - 1);
        else {
            newElements = new Object[es.length - 1];
            System.arraycopy(es, 0, newElements, 0, index);
            System.arraycopy(es, index + 1, newElements, index, numMoved);
        }
        setArray(newElements);
        return oldValue;
    }
}

Every mutation creates a new array. That's the "copy on write" in action.

---

How get() Works — Zero Locking

public E get(int index) {
    return elementAt(getArray(), index);  // That's it. No lock!
}

// getArray() is just:
final Object[] getArray() {
    return array;  // volatile read — sees the latest published version
}

Time complexity: O(1) — one volatile read + one array access. No synchronization, no CAS, no contention.

---

How Iterators Work — Snapshot Iterators

This is the most elegant part. Iterators capture a snapshot of the array at creation time and are completely unaffected by subsequent modifications:

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

static final class COWIterator<E> implements ListIterator<E> {
    private final Object[] snapshot;  // Captured at creation time
    private int cursor;
    
    COWIterator(Object[] es, int initialCursor) {
        cursor = initialCursor;
        snapshot = es;  // This reference NEVER changes
    }
    
    public E next() {
        // Reads from snapshot — immune to concurrent modifications!
        return (E) snapshot[cursor++];
    }
}

No ConcurrentModificationException. Ever. The iterator works on a frozen snapshot. This is the fundamental guarantee.

Trade-off: The iterator may not reflect the latest state. If you need to see real-time data, CopyOnWriteArrayList is the wrong choice.

---

Write Amplification — The Cost

Every write copies the entire array. Let's quantify the pain:

List Size	Time per add()	Memory per add()	Verdict
10	~50 ns	~40 bytes	✅ Fine
100	~200 ns	~400 bytes	✅ Fine
1,000	~2 μs	~4 KB	⚠️ Depends
10,000	~20 μs	~40 KB	❌ Careful
100,000	~200 μs	~400 KB	❌ Avoid

---

When to Use It

Ideal use cases:

• Event listener lists — add/remove listeners infrequently, iterate (notify) often

• Configuration lists — set once, read many times

• Caches of small reference data — updated rarely, queried constantly

• Observer pattern — for (listener : listeners) is the hot path

Real-world example — Listener/Observer:

class EventBus {
    // Listeners rarely change, but are iterated on every event
    private final CopyOnWriteArrayList<EventListener> listeners =
        new CopyOnWriteArrayList<>();
    
    void addListener(EventListener listener) {
        listeners.add(listener);  // Rare write — copy is OK
    }
    
    void fireEvent(Event event) {
        // Hot path — thousands of events per second
        for (EventListener listener : listeners) {  // Snapshot iterator — no lock!
            listener.onEvent(event);
        }
    }
}

---

CopyOnWriteArraySet

Just like Sets are Map-backed, CopyOnWriteArraySet is backed by CopyOnWriteArrayList:

public class CopyOnWriteArraySet<E> extends AbstractSet<E> {
    private final CopyOnWriteArrayList<E> al;
    
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }
    
    public boolean add(E e) {
        return al.addIfAbsent(e);  // O(n) — must scan for duplicates!
    }
    
    public boolean contains(Object o) {
        return al.contains(o);     // O(n) — linear scan!
    }
}

Warning: CopyOnWriteArraySet has O(n) contains() and add() because it uses a flat array, not a hash table. Only use it for very small sets.

---

Common Pitfalls

Pitfall 1: Using with Large Lists

// ❌ TERRIBLE: Large list + frequent writes
CopyOnWriteArrayList<LogEntry> logs = new CopyOnWriteArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    logs.add(new LogEntry(message));  // Copies 1M entries EACH time!
}
// Total copies: 1 + 2 + 3 + ... + 1M = ~500 billion element copies!

// ✅ Use a concurrent queue instead
ConcurrentLinkedQueue<LogEntry> logs = new ConcurrentLinkedQueue<>();

Pitfall 2: Expecting Iterator to See Updates

// The iterator sees a snapshot — NOT the live list
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(List.of("A", "B"));
Iterator<String> it = list.iterator();
list.add("C");
// it will NOT see "C" — it's reading from the old snapshot

Pitfall 3: Iterator Doesn't Support remove()

// ❌ UnsupportedOperationException!
Iterator<String> it = list.iterator();
it.next();
it.remove();  // Not supported — can't modify a snapshot!

---

Summary

The one-liner: CopyOnWriteArrayList copies the entire array on every write to achieve lock-free reads and snapshot iterators — perfect for small, rarely-modified, frequently-iterated lists like event listener registries.