ArrayList vs LinkedList Cheat Sheet
`ArrayList` and `LinkedList` both implement `List`, but their performance profiles are nearly opposite. This snippet shows the basic operations on each, the cases where `LinkedList` actually wins (head/tail mutation via the `Deque` API), and a quick benchmark that demonstrates random access cost. The takeaway: default to `ArrayList`; only reach for `LinkedList` when you genuinely need queue or deque behaviour.
346 views
8
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add(1, "x"); // inserts shift the tail; O(n)
System.out.println(list); // [a, x, b, c]
System.out.println("size=" + list.size());
System.out.println("get(2)=" + list.get(2)); // O(1) random access
list.remove("x");
System.out.println("after remove: " + list);
}
}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.
import java.util.LinkedList;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
LinkedList<Integer> dq = new LinkedList<>();
dq.addFirst(1); // O(1)
dq.addLast(2); // O(1)
dq.addFirst(0); // O(1)
System.out.println(dq); // [0, 1, 2]
System.out.println("peekFirst=" + dq.peekFirst()); // 0
System.out.println("pollLast=" + dq.pollLast()); // removes 2
System.out.println("after polls: " + dq);
// Use it through the Deque interface for clarity:
Deque<String> stack = new LinkedList<>();
stack.push("top");
stack.push("middle");
stack.push("bottom");
System.out.println("pop=" + stack.pop()); // bottom (last pushed)
}
}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.
import java.util.ArrayList;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
int n = 50000;
ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < n; i++) { al.add(i); ll.add(i); }
long t1 = System.nanoTime();
long sum1 = 0;
for (int i = 0; i < n; i++) sum1 += al.get(i);
long arrMs = (System.nanoTime() - t1) / 1_000_000;
long t2 = System.nanoTime();
long sum2 = 0;
for (int i = 0; i < n; i++) sum2 += ll.get(i);
long linkMs = (System.nanoTime() - t2) / 1_000_000;
System.out.println("ArrayList get-by-index sum=" + sum1 + " ms=" + arrMs);
System.out.println("LinkedList get-by-index sum=" + sum2 + " ms=" + linkMs);
System.out.println("linked / array ratio ~ " + (linkMs / Math.max(arrMs, 1)));
}
}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.