Lesson 33 / 38

ArrayList vs LinkedList

Compare the two common List implementations by how they store data and what that means for random access versus insertion/removal performance.

Backing storage

ArrayList is backed by a resizable array — get(i) is O(1), but inserting/removing in the middle shifts every element after it (O(n)). LinkedList is a doubly-linked list — adding/removing at a known node is O(1), but get(i) must walk from an end (O(n)).

Pick by usage pattern

Default to ArrayList — it's cache-friendly and covers most cases. Reach for LinkedList (or better, ArrayDeque) only when you need frequent insertions/removals at the ends, like a queue or stack.

List<Integer> fast = new ArrayList<>();   // random access, append
Deque<Integer> stack = new ArrayDeque<>(); // push/pop at ends

stack.push(1); stack.push(2);
System.out.println(stack.pop());   // 2