ArrayList is a resizing array: add(E) is amortised O(1), get(i) is O(1), and iteration is cache-friendly because elements are contiguous in memory. add(i, E) and remove(i) are O(n) because the tail must shift, but you rarely insert in the middle, so this is not a real bottleneck. Use ArrayList for almost everything: returning collections from methods, building up results in a loop, accumulating filtered values. The default capacity is 10 but it doubles on demand, so pre-sizing with new ArrayList<>(expected) saves reallocations only on hot paths.

LinkedList shines when you mutate at both ends. As a Deque, addFirst, addLast, pollFirst, and pollLast are all O(1) genuine constant time, no shifting required. The doubly-linked layout makes random access (get(i)) O(n) though, because the JVM has to walk from the nearest end. Reach for it when you implement a queue or stack and want to express that intent through the Deque interface. For pure stack semantics, ArrayDeque is usually faster than LinkedList because it avoids the per-node allocation overhead.

This loop indexes 50k elements by position. ArrayList.get(i) is a direct array offset, while LinkedList.get(i) walks the chain from the nearest end every call, turning the loop into O(n^2). On a typical JVM the linked list is hundreds of times slower for this access pattern. The lesson: never use LinkedList if you plan to call get(i) in a loop. If you must iterate, use the iterator (for (var x : ll)) which IS O(n) total because it advances one link per step rather than restarting the walk.