When LinkedList Outperforms ArrayList in Java

Direct Answer

LinkedList can be preferable when an algorithm already has a ListIterator at the required position and performs many insertions or removals there, or when one type must provide both List and Deque behavior. End operations are O(1), but ArrayDeque is normally a better pure queue or stack, and finding a middle position by index is still O(n). Measure real workloads before choosing it for performance.

Code Example

import java.util.*;

public class QueueWorkload {
    public static void main(String[] args) {
        // FIFO queue: O(1) at both ends on LinkedList
        Queue<String> q = new LinkedList<>();
        q.offer("job-1");        // add at tail - O(1)
        q.offer("job-2");
        String next = q.poll();  // remove from head - O(1)

        // ArrayList as a queue would be O(n) per front removal:
        List<String> bad = new ArrayList<>(List.of("a", "b", "c"));
        bad.remove(0);           // shifts everything left - O(n)

        // Best in practice for queues/stacks: ArrayDeque
        Deque<String> dq = new ArrayDeque<>();
        dq.addLast("x");
        dq.pollFirst();          // O(1), cache-friendly, less memory
    }
}

Common Mistakes & Pitfalls

• Over-claiming. 'LinkedList is better for insertion' is wrong without the head/tail-only qualifier — middle insert is still O(n).
• Using LinkedList as a queue by default. ArrayDeque is the recommended queue/stack — faster and leaner.
• Forgetting iterator.remove(). This is LinkedList's real O(1) edge versus ArrayList's O(n) removal.
• Indexing a LinkedList queue. If you ever need get(i), you've picked the wrong structure.