When would you use ArrayList versus LinkedList?

ArrayList stores elements in a contiguous array. Appending is amortized O(1) because the array grows geometrically. Inserting or removing in the middle shifts elements and costs O(n). Random access is O(1).

LinkedList stores a node per element with prev and next references. Inserting or removing at a node you already hold is O(1), but finding that node is O(n). Memory overhead is higher per element, and pointer chasing hurts CPU cache behaviour.

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add(0, "first");

Deque<String> queue = new ArrayDeque<>();
queue.addLast("job");
String next = queue.pollFirst();

Practical guidance

• Default to ArrayList for lists
• Use ArrayDeque for stack and queue behaviour
• Use LinkedList only when you repeatedly insert and remove at both ends through a List interface and have measured a benefit
• Preallocate capacity when the size is known to avoid repeated copying

Big-O alone can mislead. ArrayList often beats LinkedList even for middle inserts at realistic sizes because shifting contiguous memory is fast and cache-friendly, while following pointers is not. Measure with representative data before choosing the exotic option.