Java: What is the difference between ArrayList and LinkedList?

ArrayList — array-based, fast access. LinkedList — node-based, fast insert/delete.

Analogy: ArrayList = numbered parking lot. LinkedList = treasure hunt chain.

ArrayList:

• Resizable array.
• O(1) access by index.
• O(n) insert/delete in middle.
• Better cache locality.

1ArrayList<String> list = new ArrayList<>();
2list.add("Alice");       // O(1)
3list.add(1, "Bob");     // O(n)
4String s = list.get(2); // O(1)
5list.remove(0);         // O(n)
6
7// Pre-size:
8new ArrayList<>(10000);
9
10// Search:
11list.contains("Alice");
12list.indexOf("Bob");

LinkedList:

• Doubly-linked list.
• O(1) head/tail operations.
• O(n) index access.
• Deque support.

1LinkedList<String> linked = new LinkedList<>();
2linked.add("Alice");        // O(1)
3linked.addFirst("Bob");     // O(1)
4String s = linked.get(2);   // O(n)
5linked.removeFirst();       // O(1)
6
7// Deque:
8linked.push("item");
9linked.pop();
10linked.offer("item");
11linked.poll();

Complexity:

• get(i): ArrayList O(1), LinkedList O(n)
• add(end): Both O(1)
• add(middle): ArrayList O(n), LinkedList O(1) if node known
• remove(middle): ArrayList O(n), LinkedList O(1) if node known

Use ArrayList for random access (99% of cases). Use LinkedList for queue/deque.