Java 17: ArrayList vs LinkedList
easy⏱ 5 mincoursejava
ArrayList internals
Backed by Object[] elementData (default initial capacity 10). On add at the end: O(1) amortized; on resize, grows by 1.5x and System.arraycopy copies the old elements. On add(i, elem) in the middle: O(n) — shifts all elements after i right by one.
LinkedList internals
Doubly-linked list of Node { item, prev, next }. Every insert allocates a new node (GC pressure). Random access get(i) walks from head or tail. Because nodes are scattered in memory, cache misses dominate — typically 5-10x slower than ArrayList even for sequential iteration.
When to use which
ArrayList: the default — random access, append, iterate. ArrayDeque: if you need a stack or queue (faster than LinkedList). LinkedList: essentially never. The only niche is middle-insertion with an existing iterator position — and even then profile first.
// Prefer ArrayDeque over LinkedList for queue/stack
Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> queue = new ArrayDeque<>();
stack.push(1); stack.pop();
queue.offer(1); queue.poll();
Build a capacity grower
Simulate ArrayList growth: start at capacity 10, grow by 1.5x each time add would overflow. Append 1000 items. Log each resize (new capacity + total copies so far). Compare to LinkedList: 1000 node allocations, zero resizes, but each access is O(n).
Pre-size when possible
If you know the size, pass it to the constructor: new ArrayList<>(1000). That skips all intermediate resizes. The default 10 → 15 → 22 → 33... chain wastes work for large collections.
Quiz: Iterator.remove vs list.remove
You're iterating a list and removing elements. Which is safe? iterator.remove() — list.remove() throws ConcurrentModificationException because the iterator sees the underlying size change behind its back. Or use removeIf(Predicate) — cleanest.