Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Java ArrayList vs LinkedList: Choosing the Right List

Compare Java's ArrayList and LinkedList: internal storage, access cost, memory overhead, and concrete criteria for choosing the right List implementation.

~6 min readJava
#ArrayList#LinkedList#Java Collections#Data Structures
Diagram comparing an ArrayList's contiguous array storage with a LinkedList's node-based chain, illustrating direct access versus sequential traversal.

Choosing between ArrayList and LinkedList in Java comes down to how each structure stores elements and what that means for the operations your code performs. Both implement the List interface, so in many places they are interchangeable. The difference shows up in runtime behavior: ArrayList keeps elements in a resizable array, while LinkedList stores each element in a node that references its neighbors.

Internal Storage and What It Means

ArrayList wraps an Object[] array. When the array fills up, the list allocates a new, larger array and copies the existing elements over. In the usual OpenJDK implementation, the growth factor is 1.5x, which keeps appends amortized O(1).

LinkedList uses a doubly-linked list. Each element is wrapped in a Node object that holds the element value plus references to the previous and next nodes. The list keeps references to the first and last nodes. There is no contiguous block of memory, and there is no resize operation.

This structural difference is the root cause of every other difference between the two classes.

Random Access: The get(int) Operation

ArrayList.get(int index) is a direct array read. Given an index, the JVM can compute the memory address immediately, so the operation is O(1).

LinkedList.get(int index) has to walk the chain of nodes. The implementation optimizes slightly by starting from whichever end is closer, but the operation is still O(n) in the worst case. For a list with a million elements, reading an element near the middle means following half a million node references.

java
List<String> arrayList = new ArrayList<>(); List<String> linkedList = new LinkedList<>(); // Populate both lists with the same data for (int i = 0; i < 100_000; i++) { arrayList.add("item-" + i); linkedList.add("item-" + i); } // Direct index access String fromArrayList = arrayList.get(50_000); // O(1) String fromLinkedList = linkedList.get(50_000); // O(n)

The get call on the linked list has to traverse from the nearest end to reach index 50,000. The array list reads the element directly from the backing array. If your algorithm indexes into the list repeatedly, ArrayList is the only reasonable choice.

Insertion and Removal: Where the Cost Comes From

For ArrayList, inserting or removing an element at an arbitrary index requires shifting every subsequent element. If you insert at index 0, all existing elements move one position to the right. This is O(n). Adding at the end is amortized O(1) because most appends do not trigger a resize.

For LinkedList, inserting or removing at a known position is O(1) if you already hold the node reference. The list only needs to update the prev and next references of the surrounding nodes. However, finding that position by index is O(n), so an operation like remove(index) still costs O(n) because of the traversal.

The practical difference appears in code like this:

java
// Inserting at the front of a large list List<Integer> arrayList = new ArrayList<>(); List<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < 100_000; i++) { arrayList.add(i); linkedList.add(i); } arrayList.add(0, -1); // O(n): shifts all 100,000 elements linkedList.add(0, -1); // O(1): links the new node at the head

The same pattern applies to removal. Removing the first element of an ArrayList shifts everything left. Removing the first element of a LinkedList is O(1); it unlinks the current head and updates the first/last references as needed. But removing an element in the middle of a LinkedList still requires walking to that position first.

Memory Footprint and Cache Behavior

ArrayList stores elements in a single contiguous array. The overhead is the array object itself plus a small amount of bookkeeping. Each element occupies one reference slot in the array.

LinkedList stores each element in a Node object. On a 64-bit JVM with compressed object pointers, each node carries the element reference plus two references for the previous and next nodes, in addition to object header overhead. That is significant per-element overhead compared to a single reference in an array.

Cache behavior matters as well. The CPU loads data in cache lines. When iterating over an ArrayList, consecutive elements are adjacent in memory, so the CPU can prefetch them efficiently. When iterating over a LinkedList, nodes are scattered across the heap, so each step may miss the cache and load a new cache line. For large lists, this makes iteration slower on linked lists even though the algorithmic complexity is the same.

Iteration and Traversal

Both classes implement Iterable, and a for-each loop works identically at the source level. The difference is in what happens during iteration.

For ArrayList, the iterator walks the backing array by index. Each next() call is an array read.

For LinkedList, the iterator follows node references. Each next() call dereferences the current node and moves to the next.

The algorithmic complexity of a full iteration is O(n) for both. The constant factor is higher for LinkedList because of the cache behavior described above.

There is also a difference with remove() during iteration. Both iterators support remove(), but the LinkedList iterator can remove the current node in O(1) because it holds the node reference, while the ArrayList iterator must shift elements.

java
List<String> list = new LinkedList<>(); // Works for ArrayList too Iterator<String> it = list.iterator(); while (it.hasNext()) { if (it.next().startsWith("skip-")) { it.remove(); } }

For LinkedList, each remove() call is O(1) because the iterator already points at the node. For ArrayList, each remove() call is O(n) because the remaining elements shift. For a large list, filtering with iterator removal tends to be much slower on an ArrayList when many elements are removed.

LinkedList as a Deque

LinkedList implements both List and Deque. This means it can be used as a queue or stack without wrapping it in another class.

java
Deque<String> queue = new LinkedList<>(); queue.addLast("first"); queue.addLast("second"); String next = queue.removeFirst(); // "first"

ArrayList does not implement Deque. If you need queue behavior with occasional indexed access, LinkedList gives you both in one class. If you only need queue behavior, ArrayDeque is usually a better choice because it uses a resizable array and has better cache locality.

This is a real decision point: the choice is not always ArrayList versus LinkedList. Sometimes the correct answer is ArrayDeque or another collection entirely.

Choosing Between ArrayList and LinkedList

The decision criteria are concrete:

  • Use ArrayList when you need indexed access, iterate frequently, or append elements at the end. This covers most list use cases in real applications.
  • Use LinkedList when you need to insert or remove at the beginning or end frequently and also need List semantics, or when you need a Deque and a List in the same object.
  • Avoid LinkedList when your code calls get(int) in a loop, because each call is O(n) and the total becomes O(n²).
  • Avoid ArrayList when you constantly insert at the front of a very large list, because each insertion shifts the entire array.

There is a common misconception that LinkedList is faster for all insertion and removal operations. That is only true when the insertion point is already known. When the insertion point is found by index, the traversal cost dominates.

A Practical Example: Filtering a Large List

Consider a task that reads a list of records, removes entries that do not match a condition, and then processes the survivors in order.

java
List<Record> records = loadRecords(); // returns either ArrayList or LinkedList Iterator<Record> it = records.iterator(); while (it.hasNext()) { if (!it.next().isValid()) { it.remove(); } } for (Record r : records) { process(r); }

With an ArrayList, the removal loop shifts elements many times, which is expensive for a large list. With a LinkedList, each removal is O(1) but the final iteration is slower due to cache behavior. Which one wins depends on the ratio of removals to surviving elements and the size of the list. If most elements survive, ArrayList is usually better because the iteration cost dominates. If most elements are removed, LinkedList can win because the removal cost dominates.

There is no universal answer, but the mechanism is clear: count the cost of shifting versus the cost of node traversal and cache misses.

Try matching browser tools

All tools

Small utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Java guides

More in Java

All Java guides

The guides filed next to this one in Java, in library order.