Lists: interview questions & scenarios

Model answer

A no-argument new ArrayList<>() does not immediately allocate a 10-element array. It points at a shared empty array. On the first add, it allocates the default capacity, which is 10 in OpenJDK. When that backing array fills, JDK 21 grows to roughly old + (old >> 1), about 1.5x, and copies references with Arrays.copyOf.

size is the number of actual elements. Capacity is the length of the internal array and is not normally visible. add(e) is amortised O(1): most calls write one slot, while occasional growth calls copy the current contents.

List<String> tags = new ArrayList<>(); // shared empty backing array
tags.add("new");                      // first real array, capacity 10
tags.add("sale");                     // size 2

If you know the count, use new ArrayList<>(expectedSize) or ensureCapacity before a large batch. Do not cargo-cult trimToSize; it can save memory after a spike, but it also removes spare capacity and makes the next append more likely to grow.

Model answer

The nuanced answer is: LinkedList only wins if you already hold the current position, usually through a ListIterator, and perform several edits at that cursor. Then insertion and removal are pointer rewires after the node is known.

If each operation starts with an index, a song ID or a search, LinkedList first walks to the position. That is O(n), plus node allocation and pointer chasing. ArrayList shifts a contiguous suffix with System.arraycopy, which is often faster in practice even though the Big-O table says O(n).

LinkedList<String> playlist = new LinkedList<>(List.of("intro", "ad", "song"));
ListIterator<String> it = playlist.listIterator();
while (it.hasNext()) {
    if (it.next().equals("ad")) {
        it.remove();       // O(1) at cursor
        it.add("station"); // O(1) at cursor
    }
}

So I default to ArrayList for lists. I choose LinkedList for a cursor-edit workflow I can describe clearly, not for the vague phrase "middle inserts".