What is the precise cost model of CopyOnWriteArrayList writes, and what is CopyOnWriteArraySet?
answer
- One write = O(n) time + a full new array allocation
- Incremental adds = O(n squared) + n allocations
- Prefer addAll / constructor to copy once
- CopyOnWriteArraySet is backed by a CopyOnWriteArrayList
- Set add and contains are O(n) linear scans
basics
~20 sEvery write copies the whole array, so one write is O(n) in time and allocates a new array of size n. Adding n elements one by one is O(n squared). CopyOnWriteArraySet is the Set version with no duplicates, backed by a CopyOnWriteArrayList, so adds also scan for existing elements.
solid answer
~50 sEach mutating operation on a CopyOnWriteArrayList allocates a fresh array and copies all existing elements, so a single add/remove/set is O(n) time and O(n) extra memory. Building the list element-by-element is therefore O(n squared) overall and generates a lot of short-lived garbage — if you know the contents up front, construct it once from a collection or use addAll, which still copies but only once. CopyOnWriteArraySet is the Set analogue: a set has no duplicate elements, and this one is backed internally by a CopyOnWriteArrayList. That backing means add() must first scan the array for an equal element (O(n)) and then, if absent, do the O(n) copy — so it's even less suited to large or write-heavy sets. Both share the same virtues: lock-free, snapshot iteration that never throws. Reach for them only for small, read-mostly collections.
go deeper
Knows writes are expensive because they copy the array and that a Set version exists.
States the O(n) per write and O(n squared) incremental-build cost, the addAll mitigation, and that CopyOnWriteArraySet is list-backed with linear-scan add/contains.
Reasons about resulting GC/allocation pressure and chooses ConcurrentHashMap.newKeySet over CopyOnWriteArraySet for larger or write-heavier sets.
Weighs allocation/latency-tail impact at scale and sets guidance on size thresholds and alternatives for concurrent collections.
## Reading the cost model We describe cost with **Big-O notation**, which states how work grows with the number of elements *n*. O(1) means constant (independent of n); O(n) means proportional to n; O(n²) means proportional to n times n. ### Per-write cost The copy-on-write rule is: every `add`, `set`, or `remove` **creates a brand-new array of (roughly) size n, copies every existing element into it**, applies the change, and swaps the reference. So: - **Time:** one write = **O(n)** (you touch all n elements to copy them). - **Memory:** one write **allocates** a whole new array (~n references) and abandons the old one, producing **garbage** for the collector to reclaim. ### Building it incrementally is quadratic If you start empty and `add` one element at a time, the i-th add copies i elements, so the total is 1 + 2 + … + n ≈ **n²/2 = O(n²)**, plus n separate array allocations. For a list of any real size this is dramatically slower and more GC-intensive than an `ArrayList`'s amortized O(1) appends. **Mitigation:** if you already know the contents, build the COW list in **one shot** — pass a collection to the constructor, or call `addAll(collection)` once. `addAll` still copies, but **once** for the whole batch (O(n)), not once per element. ## `CopyOnWriteArraySet` A **`Set`** is a collection that holds **no duplicate elements** (membership is decided by `equals`). `CopyOnWriteArraySet` is the copy-on-write `Set`. Crucially, **it is backed internally by a `CopyOnWriteArrayList`** — not by a hash table. Consequences: - Membership and dedup are done by **linear scan**: `add(x)` walks the array checking `equals` to see if `x` is already present — **O(n)** — and only then, if absent, performs the **O(n)** array copy. So `add` is O(n) regardless, and building a set of n elements is again **O(n²)**. - `contains(x)` is **O(n)** (scan), versus O(1) average for a `HashSet`. - It inherits COW's good parts: lock-free reads and a **snapshot iterator** that never throws `ConcurrentModificationException`. That linear behavior is why `CopyOnWriteArraySet` is only appropriate for **small** sets that are read far more than written — for a large or write-heavy concurrent set you'd prefer something like a set view over a `ConcurrentHashMap` (`ConcurrentHashMap.newKeySet()`), which gives O(1) average operations. ## Mental model Each write is like **republishing an entire book** to change one word: cheap to read the book, expensive to publish, and republishing once per word while writing the book (incremental adds) is absurdly wasteful — write the manuscript first, publish once (`addAll`). ## Quick reference | Operation | `CopyOnWriteArrayList` | `CopyOnWriteArraySet` | |---|---|---| | `get(i)` / read | O(1), lock-free | n/a (no index), `contains` is O(n) | | single `add` | O(n) | O(n) (scan + copy) | | build n elements one-by-one | O(n²) | O(n²) | | build via constructor/`addAll` | O(n) once | O(n²) worst case (still dedups by scan) | | iteration | snapshot, never throws | snapshot, never throws |
- How do you cheaply build a CopyOnWriteArrayList of known contents?Construct it from an existing collection (or call addAll once) so the backing array is copied a single time, O(n) total, instead of one O(n) copy per element which is O(n squared).
- Why is CopyOnWriteArraySet.contains O(n) rather than O(1)?It is backed by a CopyOnWriteArrayList, not a hash table, so membership is determined by a linear scan comparing elements with equals.
saying these in an interview costs you the question
- Saying a single write is O(1)
- Thinking CopyOnWriteArraySet is hash-based like HashSet (it's a linear scan)
- Building a large COW list element-by-element in a loop
- Assuming addAll avoids copying — it copies once, not zero times