ArrayList vs LinkedList

TL;DR

• ArrayList: Backed by a resizable dynamic array. Extremely fast (O(1)) for retrieving elements by index. Slow (O(N)) for inserting/deleting in the middle.
• LinkedList: Backed by a doubly-linked list of nodes. Fast (O(1)) for inserting/deleting at the absolute ends, but very slow (O(N)) for retrieving elements by index.
• Use ArrayList in 99% of professional Java applications due to superior CPU Cache Locality.

Concept

An ArrayList stores items in contiguous (side-by-side) memory blocks. When you ask for list.get(50), the CPU instantly jumps exactly 50 memory addresses forward and returns the item. However, if you list.add(0, "A"), Java has to move every single existing item in the array one slot to the right, which is very slow.

A LinkedList stores items as standalone Node objects scattered randomly across the heap. Each node just has a pointer to the “next” and “previous” node. To get(50), Java must start at the beginning and follow the pointers 50 times (O(N) time). However, if you are at the beginning and want to insert something, you just create one new Node and update two pointers (O(1) time).

Examples

import java.util.*;

public class ListComparison {

    public static void main(String[] args) {
        // ARRAYLIST (Contiguous Memory)
        List<String> arrayList = new ArrayList<>();
        arrayList.add("Apple");
        arrayList.add("Banana");
        
        // Instant O(1) lookup. The JVM knows exactly where memory index 1 is.
        System.out.println(arrayList.get(1)); 

        // LINKEDLIST (Scattered Nodes)
        List<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        
        // O(N) lookup. The JVM must start at node 0 and follow the pointer to node 1.
        System.out.println(linkedList.get(1)); 
        
        // Only fast if you are operating on the absolute ends!
        ((LinkedList<String>) linkedList).addFirst("Mango");
    }
}

Interview Questions

Q: Why does ArrayList outperform LinkedList even for insertions in real-world benchmarks?
A: Because of CPU Cache Locality. Modern CPUs load memory into their blazing-fast L1/L2 caches in blocks. Because ArrayList uses contiguous memory, the CPU loads the entire array into cache at once. Iterating or shifting an array in the L1 cache takes nanoseconds.
Because a LinkedList’s nodes are scattered randomly across the Heap, following a pointer almost always results in a “Cache Miss,” forcing the CPU to fetch data from main RAM (which is 100x slower).

Q: How does an ArrayList grow when it gets full?
A: An ArrayList starts with a default backing array size of 10. When you try to add the 11th element, it realizes it’s full.
It allocates a brand new array that is 1.5x the size (size 15). It then uses a native C++ memory copy command (System.arraycopy()) to instantly blast the data from the old array into the new array. The old array is then thrown away for the Garbage Collector.

Q: What is ArrayList vs LinkedList?
A: Answer…