When is an ArrayList the wrong choice in Java, and what should you use instead?
answer
- Which operation dominates the workload?
- What moves when the front changes?
- Lookup by value: what gets scanned?
- Who else writes to it?
- Boxed values: what does each one cost?
basics
~20 sArrayList is wrong when the main work is at the front (use ArrayDeque), lookup by value (HashSet or HashMap), priority or sorted order (PriorityQueue, TreeMap), sharing with writer threads (concurrent collections), or large primitive data (int[]).
solid answer
~50 s`ArrayList` gives constant-time `get`, `set` and `removeLast` and amortized appends, but linear time for most other operations, so it is the wrong choice when one of those dominates. For a FIFO queue, `remove(0)` shifts every remaining element: use `ArrayDeque`, giving up index access and nulls. For repeated lookup by value, `contains` scans: use `HashSet` or `HashMap`. For the next smallest element, use `PriorityQueue`; for sorted data that keeps changing, `TreeSet` or `TreeMap`. When threads share it and one writes, it needs external synchronization, so prefer `CopyOnWriteArrayList` for read-mostly lists or a `BlockingQueue` for hand-off. For large primitive data, boxing costs an object per value outside a small cache, so use `int[]`. `LinkedList` fits narrowly: many edits at a position a `ListIterator` holds, or one object that must be both a `List` and a `Deque`. On a short list the difference rarely shows up in a profile, so measure before switching.
code
java · 14 lines// Queue: ArrayList.remove(0) would shift every remaining element
Deque<String> queue = new ArrayDeque<>();
queue.addLast("a");
queue.addLast("b");
System.out.println(queue.pollFirst()); // a
// Lookup by value, keeping first-seen order
Set<String> seen = new LinkedHashSet<>(List.of("b", "a", "b"));
System.out.println(seen.contains("a")); // true
System.out.println(seen); // [b, a]
// The next smallest, with no re-sort
Queue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 3));
System.out.println(pq.poll()); // 1go deeper
Know that ArrayList is the usual default but is slow at removing from the front and at finding a value, and name ArrayDeque and HashSet as the fixes for those two jobs.
Be ready to match a job to its replacement: ArrayDeque for a queue, HashSet or HashMap for lookup, PriorityQueue for the next best element, TreeMap for sorted data, and say what each gives up against a list.
Expect to argue from the workload: name the dominant operation, give the replacement and its cost, and know the traps, such as removeFirst still shifting, and a stack or a sorted read-only list being fine on ArrayList.
Be ready to set team guidance: ArrayList as the default with profiled exceptions, unmodifiable lists at API boundaries, and when the memory cost of boxed data justifies a primitive array or a new library dependency.
## Where the contract stops helping `ArrayList` keeps its elements in one array, in index order. Its Javadoc promises constant time for `get`, `set`, `size`, `getLast`, `removeLast` and `iterator`, amortized constant time for `add` at the end, and linear time, "roughly speaking", for all of the other operations. So it is a sound default, and that list also says when it is the wrong one: the operation that dominates your workload is one of the linear ones, or the job needs something an array does not give. Each replacement below is a trade, so say what it costs as well. How the shift works, how the array grows and what happens when the list changes during iteration are separate questions. | The job | Why `ArrayList` is wrong | Use instead | What you give up | |---|---|---|---| | FIFO queue, work at the front | `remove(0)` and `add(0, x)` move every other element | `ArrayDeque` | `get(int)`, null elements | | Repeated lookup by value | `contains` and `indexOf` scan the array | `HashSet`, `HashMap` | index access, duplicates in a set | | Always the next smallest or largest | finding it means a scan or a re-sort | `PriorityQueue` | index access, sorted iteration | | Sorted data that keeps changing | each insert shifts the tail | `TreeSet`, `TreeMap` | index access, duplicates in a set | | Shared by threads, at least one writing | it is not synchronized | `CopyOnWriteArrayList`, a `BlockingQueue` | cheap writes, or the `List` API | | Large primitive data | every element is a boxed object | `int[]` | automatic growth, the `List` API | | A list callers must not change | anyone holding it can mutate it | `List.of`, `List.copyOf` | null elements, mutation | ## Work at the front A FIFO queue on an `ArrayList` pays a full shift on every `remove(0)`. `ArrayDeque` runs most operations in amortized constant time, and taking from its head moves an index, not the elements. Its Javadoc calls it likely to be faster than `LinkedList` when used as a queue. It is not a `List`, so it has no `get(int)`, and it prohibits null elements. Two details matter here: - **`addFirst` and `removeFirst` do not help.** `ArrayList` gained them in JDK 21. They read like deque methods, and they still shift the other elements. - **The tail is fine.** A LIFO stack built on `add` and `removeLast` stays cheap, so a stack alone does not make `ArrayList` wrong. ## Lookup and order - **Lookup by value:** `HashSet` and `HashMap` offer constant time for their basic operations, assuming the hash function disperses elements properly. `LinkedHashSet` adds insertion order on the same terms. In exchange, the elements need a correct `hashCode` and `equals`, and OpenJDK allocates a node per entry where the array had a slot. - **The next best element:** the implementation note on `PriorityQueue` gives O(log n) for `offer` and `poll` and constant time for `peek`. - **Sorted data that keeps changing:** `TreeSet` and `TreeMap` guarantee log(n) for their basic operations and add range views such as `headSet` and `subMap`. A `TreeSet` drops an element that compares equal to one it holds, so to keep duplicates, count them in a `TreeMap` or use Guava's `TreeMultiset`. - **Sorted data that stays put:** keep the `ArrayList`. `Collections.binarySearch` runs in log(n) time on it, and nothing shifts if nothing is inserted. ## Threads The Javadoc says an `ArrayList` "must be synchronized externally" when several threads access it and at least one modifies it structurally. The fix depends on the workload: 1. **Read-mostly, such as a listener list:** `CopyOnWriteArrayList`. Every mutation copies the array, which its Javadoc calls "ordinarily too costly", but possibly more efficient when traversals vastly outnumber mutations. 2. **Hand-off between threads:** a `BlockingQueue`, whose `put` and `take` wait for space or for an element. 3. **A `List` with frequent writes:** `Collections.synchronizedList`, with a manual `synchronized` block around every traversal. ## Primitives, and lists you hand out A `List<E>` holds references, so an `ArrayList<Integer>` boxes each value. On JDK 25 and 27 with compressed references, a value outside the always-cached range of -128 to 127 costs a 4-byte slot plus a 16-byte `Integer`, against 4 bytes per element in an `int[]`. Use an `int[]` when you can size it, or a primitive list such as Eclipse Collections' `IntArrayList` when it has to grow and a profile justifies the dependency. A list returned from a getter is a different problem: an `ArrayList` lets any holder change your state. `List.copyOf` returns an unmodifiable snapshot whose mutators throw `UnsupportedOperationException`, and `List.of` builds such a list directly. Both disallow null elements. ## Where LinkedList fits, and how to decide `LinkedList` is the fit in two narrow cases: a long list edited many times at a position a `ListIterator` already holds, since each `add` or `remove` there relinks neighbours and moves no elements; and one object that has to be both a `List` and a `Deque`. The head-to-head with `ArrayList` has its own questions. To decide: 1. Name the operation that dominates in production, not the one that is easiest to write. 2. Find its replacement above, and check what that gives up against the job. 3. On a short list a scan or a shift rarely shows up in a profile, so keep `ArrayList` until one says otherwise.
- What if the list must stay sorted and reads far outnumber inserts?Keep the ArrayList. Collections.binarySearch runs in log(n) time on a random-access list, and a negative result encodes the insertion point, though the add itself still shifts the tail. Move to TreeSet or TreeMap once inserts become frequent and index access no longer matters.
- What do you do if you need list order, duplicates and fast membership at once?LinkedHashSet does not fit, because it drops duplicates. Keep the ArrayList for order beside a HashMap of counts for membership, and wrap the pair in one class so every change updates both.
- How do you stop callers changing a list you return from an API?Return List.copyOf(list), an unmodifiable snapshot that later changes to your list do not reach; it throws NullPointerException if the list holds a null. Collections.unmodifiableList(list) is a read-only view instead, so callers still see your later changes.
- Believing a larger initial capacity fixes a slow remove(0)
- Assuming addFirst and removeFirst made ArrayList a cheap deque in JDK 21
- Reaching for LinkedList whenever an ArrayList is slow, without naming the operation
- Calling ArrayList wrong for a stack, when add and removeLast at the tail are cheap
- Using CopyOnWriteArrayList for a shared list that is written often
- Treating an ArrayList<Integer> as being as compact as an int[]
- ArrayDeque
- Java 1.6
- removeLast, getLast, addFirst and removeFirst on List
- Java 21
- List.of
- Java 9
- List.copyOf
- Java 10
Assumes JDK 27; JDK 25 reads the same here. ArrayList has getLast, removeLast, addFirst and removeFirst since JDK 21: the first two run in constant time, and the other two still shift elements. The slot and Integer sizes hold on both releases with compressed references.
context
- ArrayList (Java SE 27 & JDK 27)docs.oracle.com
- ArrayDeque (Java SE 27 & JDK 27)docs.oracle.com
- LinkedHashSet (Java SE 27 & JDK 27)docs.oracle.com