ArrayList stores elements in a resizable array, while LinkedList is a doubly linked list of nodes that point to their neighbours. That layout decides which operations are cheap.
ArrayList reads any index in O(1), because it jumps straight to the slot. Adding at the end is amortized O(1), meaning an occasional resize copies the array but the average cost per add stays constant. Inserting or removing in the middle is O(n), because the later elements have to shift.
LinkedList adds and removes at either end in O(1), and in the middle only when an iterator already points there. Reaching an index is O(n), because it walks node by node from the nearer end. So add(index, x) in the middle is O(n) as well.
ArrayList is the usual default, since its per-element overhead is lower. For queue work at the ends, ArrayDeque is often faster than LinkedList.
List<String> arrayList = new ArrayList<>(Collections.nCopies(101, "item"));
List<String> linkedList = new LinkedList<>();
// ArrayList better for
String element = arrayList.get(100); // O(1)
// LinkedList better for
linkedList.add(0, "first"); // O(1)
linkedList.remove(0); // O(1)
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Why there's no diagram: “”
The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓
The diagram below the answer is the concept . Jump to it ↓