What is the difference between ArrayList and LinkedList in Java?
ArrayList is backed by a resizable array, so reading by index is O(1) but inserting or removing in the middle shifts elements. LinkedList is a doubly linked list, so adding or removing at the ends is O(1) but reaching an index means walking the nodes. In practice ArrayList is the better default almost every time.
Explain it simply
An ArrayList is like a row of numbered seats in a cinema hall. If you want seat 57, you walk straight to it. But if a new person must sit in seat 3, everyone from seat 3 onwards has to shift one seat to the right.
A LinkedList is like a queue of people at a railway counter where each person only knows who is in front and who is behind them. Someone can join at either end instantly. But to find the 57th person, you must start at one end and count heads one by one.
Example
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Lists {
public static void main(String[] args) {
List<String> stations = new ArrayList<>(List.of("Howrah", "Asansol", "Dhanbad"));
System.out.println(stations.get(2)); // prints: Dhanbad (direct index lookup)
stations.add(1, "Bandel"); // shifts Asansol and Dhanbad right
System.out.println(stations); // prints: [Howrah, Bandel, Asansol, Dhanbad]
LinkedList<String> queue = new LinkedList<>();
queue.addLast("Ravi");
queue.addLast("Meena");
queue.addFirst("Priority pass"); // O(1) at either end
System.out.println(queue.removeFirst()); // prints: Priority pass
}
}How it works
| Operation | ArrayList | LinkedList |
|---|---|---|
get(i) / set(i) | O(1) | O(n) |
| Add at end | O(1) amortised | O(1) |
| Add or remove at start | O(n) (shift) | O(1) |
| Add or remove in middle | O(n) (shift) | O(n) to find the spot, then O(1) to relink |
| Memory per element | Just a reference in the array | A node with item, next and prev references |
ArrayList keeps an Object[]. When it is full, it grows to about 1.5 times its size and copies the old elements across. Copying is occasional, so adding at the end is O(1) on average.
LinkedList keeps a pointer to the first and last node. Each node points to its neighbours. get(i) walks from whichever end is closer, but that is still O(n). LinkedList also implements Deque, so it can act as a queue or stack.
Real-world use
- ArrayList: lists shown in a UI, search results, rows from a database, anything you mostly read or append to.
- LinkedList: rarely the best choice today. For a queue or stack,
ArrayDequeis usually faster than LinkedList because it uses an array internally.
Common mistakes
- Saying "LinkedList is faster for insertion in the middle". The relinking is O(1), but finding the position is O(n), and in real benchmarks ArrayList's fast memory copy often wins.
- Calling
get(i)inside a loop on a LinkedList, which turns a simple loop into O(n²). Use an iterator or for-each. - Forgetting the memory cost. Every LinkedList node is a separate object, which is slower for the CPU cache and adds pressure on the garbage collector.
What to say in the interview
"ArrayList uses a dynamic array, so random access is O(1) and appending is amortised O(1), but inserting or deleting in the middle shifts elements, which is O(n). LinkedList is a doubly linked list, so adding or removing at the head or tail is O(1), but accessing by index is O(n) because it has to walk the nodes. LinkedList also uses more memory per element. So I default to ArrayList, and if I need a queue or stack I use ArrayDeque rather than LinkedList."
Follow-up questions
- How does ArrayList grow when it is full?
- Why is ArrayDeque usually preferred over LinkedList for a queue?
- What is the difference between
ArrayListandVector? - What happens if you remove elements from an ArrayList inside a for-each loop?
Go deeper
Read these once the basics above feel easy.
Big-O does not tell the whole story. An ArrayList stores its references in one block of memory, so the CPU can load many of them at once from cache. LinkedList nodes are scattered across the heap, and following each next pointer can miss the cache. That is why even operations that look equal on paper, such as iterating over all elements, are noticeably faster on ArrayList. If you remove items while looping, use iterator.remove() or list.removeIf(...); removing directly from the list inside a for-each loop throws ConcurrentModificationException.