ArrayList vs LinkedList: How to Choose

ArrayList vs LinkedList: How to Choose

Two of the most common List implementations are ArrayList and LinkedList. They look identical from the outside because both implement List<E>, but their internal structures make them perform very differently. Understanding that difference helps you write code that stays fast as data grows, and the lessons translate to every other collection choice you will make.

How ArrayList works

ArrayList is a growable array. Elements sit next to each other in memory, so random access by index is O(1). Adding to the end is amortized O(1), but inserting or removing in the middle forces every subsequent element to shift, which costs O(n). When the backing array fills up, it reallocates a larger one and copies the contents over.

How LinkedList works

LinkedList is a doubly linked list. Each node holds its element plus references to the previous and next nodes. Adding or removing a node only rewires a few references, so insertions and deletions are O(1) once you have the node. The cost is memory overhead per element and O(n) random access, because finding index 500 requires walking from the head.

The practical guidance

For almost all real workloads, ArrayList wins. Random access, iteration, and appending dominate typical code, and arrays are more cache-friendly. LinkedList shines only when you constantly insert or delete near the beginning of a large list. If you need a queue or deque, prefer ArrayDeque over LinkedList.

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 100_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}
System.out.println(arrayList.get(50_000));
System.out.println(linkedList.get(50_000));

Benchmark your own code

Measure before you optimize. Microbenchmarks on your target JVM and data sizes matter more than folklore. Java 9 and later also let you create unmodifiable lists with List.of(...), which is a great default when you never need to modify the collection.

Key Points

• ArrayList offers O(1) positional access; LinkedList offers O(1) node insertion.
• ArrayList uses a growable array; LinkedList uses connected nodes with extra memory overhead.
• Use ArrayList for defaults and for patterns dominated by access and appends.
• Prefer ArrayDeque over LinkedList for stack or queue behavior.
• Always benchmark before switching implementations based on theory.