Q2 of 40 · Core Java
Explain the difference between ArrayList and LinkedList.
Short answer
Short answer: ArrayList is backed by a resizable array: O(1) random access by index, O(n) insert/delete in the middle. LinkedList is a doubly-linked list: O(1) insert/delete at a known node, O(n) index access. ArrayList outperforms LinkedList for almost all QA automation use cases due to cache-friendly memory layout.
Detail
Both implement List<E> and expose the same API, but the underlying data structures produce very different performance profiles.
ArrayList stores elements in a contiguous array that grows by ~50% when full. Getting an element at index i is O(1) — the JVM jumps directly to the address. Adding to the end is amortised O(1). Inserting or removing from the middle requires shifting everything after the insertion point — O(n). Iteration is cache-friendly because elements are laid out contiguously in memory.
LinkedList stores each element in a node that holds the value plus pointers to the previous and next nodes. Adding or removing at a known node (the head or tail) is O(1). But finding the node at index i requires traversal from whichever end is closer — O(n). It also carries higher memory overhead per element (two pointers per node) and is cache-unfriendly.
The practical result: unless you're doing a large number of insertions/deletions in the middle of a list and you already hold references to the nodes, ArrayList almost always wins on real workloads. JVM caching effects make ArrayList iteration measurably faster than LinkedList even when Big-O predicts parity.
For QA test code specifically — test data stores, scenario step lists, assertion result collections — use ArrayList. LinkedList as a Deque (via its Deque interface) is a legitimate use case when you need addFirst/removeLast semantics without caring about random access.
// EXAMPLE
ListComparison.java
// ArrayList: fast random access, good for most test data
List<String> steps = new ArrayList<>();
steps.add("navigate");
steps.add("login");
steps.add("assert");
String second = steps.get(1); // O(1)
// LinkedList as Deque: fast add/remove at both ends
Deque<String> queue = new LinkedList<>();
queue.addLast("task1");
queue.addLast("task2");
String next = queue.pollFirst(); // O(1)
// Pre-size ArrayList when count is known — avoids resize allocations
List<User> users = new ArrayList<>(1000);
for (int i = 0; i < 1000; i++) {
users.add(User.of("user" + i));
}