When should you use LinkedList over ArrayList?

• ArrayList (default choice): fast random access O(1), excellent cache locality, compact memory (~4 bytes/element), amortized O(1) add at end
• LinkedList (niche choice): O(1) insert/remove during ListIterator traversal, O(1) operations at both ends, implements both List and Deque
• ArrayDeque (for queue/stack): faster than LinkedList for Deque operations, contiguous memory, no node object overhead
• The decision flow: need random access? ArrayList. Need queue/stack? ArrayDeque. Need ListIterator modification? LinkedList.

When should you use LinkedList over ArrayList?

This is one of the most common interview questions, and the short answer surprises many candidates: almost never. ArrayList wins in practice for the vast majority of use cases.

The three scenarios where LinkedList is a valid choice:

1. ListIterator-based insert/remove during traversal. When you walk through a list with a ListIterator and need to add or remove elements at the current position, LinkedList does this in O(1) while ArrayList does it in O(n).

2. You need both List and Deque on the same object. LinkedList implements both interfaces. If your code passes the same collection to methods expecting List and methods expecting Deque, LinkedList is the only standard choice.

3. Predictable operation time. ArrayList's add() is usually O(1) but occasionally O(n) during resize. LinkedList's addFirst()/addLast() is always O(1), never worse. If your system requires guaranteed latency (no spikes), LinkedList eliminates resize spikes – though in practice, pre-allocated ArrayList also eliminates them.

package com.bank.service;

import java.util.*;

public class DecisionGuideDemo {
    public static void main(String[] args) {
        // Scenario 1: Filter and annotate during traversal
        LinkedList<String> transactions = new LinkedList<>(List.of(
            "TXN-001: Deposit 50000",
            "TXN-002: Withdraw 10000 [SUSPICIOUS]",
            "TXN-003: Transfer 25000",
            "TXN-004: Withdraw 90000 [SUSPICIOUS]",
            "TXN-005: Deposit 15000"
        ));

        // Walk through and insert hold notes after suspicious transactions
        ListIterator<String> it = transactions.listIterator();
        while (it.hasNext()) {
            String txn = it.next();
            if (txn.contains("[SUSPICIOUS]")) {
                it.add("[HOLD] Investigation required for: " + txn);
                // O(1) on LinkedList, O(n) on ArrayList
            }
        }

        transactions.forEach(System.out::println);
    }
}

TXN-001: Deposit 50000
TXN-002: Withdraw 10000 [SUSPICIOUS]
[HOLD] Investigation required for: TXN-002: Withdraw 10000 [SUSPICIOUS]
TXN-003: Transfer 25000
TXN-004: Withdraw 90000 [SUSPICIOUS]
[HOLD] Investigation required for: TXN-004: Withdraw 90000 [SUSPICIOUS]
TXN-005: Deposit 15000

Why does ArrayList win even for add(0, elem)?

In theory, add(0, elem) on ArrayList is O(n) because it shifts all elements. On LinkedList, addFirst(elem) is O(1). But in benchmarks, ArrayList is often faster even for this operation when the list has fewer than about 10,000 elements.

The reason is that System.arraycopy() is a JVM intrinsic that translates to a single CPU instruction (memmove). It copies a contiguous block of memory extremely efficiently. LinkedList's addFirst() creates a new Node object (heap allocation), updates pointers (random memory access), and causes cache misses.

For lists with more than ~100,000 elements, LinkedList's O(1) starts to genuinely outperform ArrayList's O(n) shift. But at that size, you should probably use a different data structure entirely.

package com.bank.demo;

import java.util.*;

public class AddAtZeroBenchmark {
    public static void main(String[] args) {
        int size = 50_000;

        // ArrayList: add at position 0 (shifts all elements)
        List<String> arrayList = new ArrayList<>();
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            arrayList.add(0, "ACC" + i); // O(n) shift each time
        }
        long arrayTime = System.nanoTime() - start;

        // LinkedList: addFirst (pointer update)
        LinkedList<String> linkedList = new LinkedList<>();
        start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            linkedList.addFirst("ACC" + i); // O(1) each time
        }
        long linkedTime = System.nanoTime() - start;

        System.out.printf("ArrayList add(0): %d ms%n", arrayTime / 1_000_000);
        System.out.printf("LinkedList addFirst: %d ms%n", linkedTime / 1_000_000);
    }
}

ArrayList add(0): 312 ms
LinkedList addFirst: 8 ms

What is the decision flowchart?

Follow this decision tree when choosing a List implementation:

- **Do you need random access by index (get/set by position)?** → ArrayList. Stop here.
- **Do you need queue or stack behavior (FIFO/LIFO)?** → ArrayDeque. Stop here.
- **Do you need to insert/remove at the current position during iteration?** → LinkedList.
- **Do you need both List and Deque interfaces on the same object?** → LinkedList.
- **None of the above / unsure?** → ArrayList. It is the safe default.

| Use case | Best choice | Why |
|---|---|---|
| Transaction history (paginated) | ArrayList | Random access for pagination |
| Account search results | ArrayList | Iteration and index access |
| Transaction processing queue | ArrayDeque | FIFO, cache-friendly |
| Undo stack | ArrayDeque | LIFO, faster than Stack/LinkedList |
| Inline audit insertion during scan | LinkedList | O(1) ListIterator add |
| Priority processing | PriorityQueue | Sorted by priority |
| Thread-safe list (read-heavy) | CopyOnWriteArrayList | Lock-free reads |

package com.bank.service;

import java.util.*;

public class RightCollectionForJob {
    public static void main(String[] args) {
        // Transaction history – ArrayList (paginated access)
        List<String> history = new ArrayList<>();
        history.add("TXN-001");
        String page1 = history.get(0); // O(1)

        // Processing queue – ArrayDeque (not LinkedList!)
        Deque<String> queue = new ArrayDeque<>();
        queue.offerLast("TXN-001");
        String next = queue.pollFirst(); // O(1), cache-friendly

        // Inline annotation – LinkedList (ListIterator advantage)
        LinkedList<String> auditList = new LinkedList<>(List.of("A", "B", "C"));
        ListIterator<String> it = auditList.listIterator();
        while (it.hasNext()) {
            it.next();
            it.add("VERIFIED"); // O(1) insert
        }
    }
}

What are common mistakes in the ArrayList vs LinkedList decision?

Mistake 1: Choosing LinkedList because "it is faster for inserts"

// WRONG reasoning: "I insert frequently, so LinkedList is better"
// If inserts are at the END: ArrayList is just as fast (amortized O(1))
// If inserts are at RANDOM positions: both are O(n) – ArrayList may be faster
// LinkedList is faster ONLY for ListIterator-based inserts

Mistake 2: Using LinkedList as a queue

// SUBOPTIMAL
Queue<String> queue = new LinkedList<>();
// Each enqueue creates a Node object (GC pressure)
// Node objects scattered in heap (cache misses)

// BETTER
Queue<String> queue = new ArrayDeque<>();
// Circular array – no object creation per enqueue
// Contiguous memory – cache-friendly

Mistake 3: Using LinkedList and accessing by index in a loop

LinkedList<String> list = new LinkedList<>(/* 10000 elements */);
// WRONG – O(n^2) quadratic access
for (int i = 0; i < list.size(); i++) {
    String s = list.get(i); // O(i) each time
}
// CORRECT – O(n) using iterator
for (String s : list) { /* O(1) per step */ }

What should a senior engineer know?

- Benchmark, do not assume. CPU cache effects dominate for lists under ~100K elements. Always benchmark with realistic data sizes and access patterns before choosing LinkedList over ArrayList.

- JMH for reliable benchmarks. Microbenchmarks with System.nanoTime() can be misleading due to JIT warm-up and GC. Use JMH (Java Microbenchmark Harness) for reliable comparison.

- Lock-free alternatives. ConcurrentLinkedQueue is a lock-free queue based on linked nodes. It is the right choice for high-throughput producer-consumer scenarios, not LinkedList.

- Modern Java consideration. Java records, sealed classes, and pattern matching do not change the ArrayList vs LinkedList decision. The choice is purely about data structure performance, not language features.

- LinkedList in the JDK source. Even within the JDK itself, ArrayList is used far more than LinkedList. The JDK team recommends ArrayList as the default.

What are common interview follow-up questions?

• "Name a scenario where LinkedList is genuinely better." – ListIterator insert/remove during traversal.
• "What about ArrayDeque?" – Faster than LinkedList for queue/stack, uses less memory, but does not implement List.
• "If ArrayList shifts elements on insert, why is it still fast?" – System.arraycopy is a JVM intrinsic (native memcpy), cache-friendly.
• "What is the RandomAccess marker interface?" – Signals that get(index) is O(1). ArrayList implements it; LinkedList does not.