ArrayList vs LinkedList - What Actually Matters

ArrayList is backed by a dynamic array: random access by index is O(1), tail add is amortized O(1), but insert/remove in the middle requires shifting elements O(n). LinkedList is a doubly linked list: head/tail insert/remove are O(1), but access by index requires traversal O(n). In most real-world scenarios (iteration, index access, conditional removal), ArrayList is the better choice. This article explains the trade-offs with examples and a comparison table.

Overview

• ArrayList: Internally an Object[] elementData that grows automatically (typically 1.5× when full). get(i) and set(i) are O(1). add(e) at the end is amortized O(1); add(i, e) or remove(i) are O(n) because elements must be shifted. Iteration is fast and cache-friendly because elements are stored contiguously.
• LinkedList: A doubly linked list; each node has prev, next, and the element. Head/tail add and remove are O(1). get(i) and set(i) require walking from head or tail to position i, so O(n). Insert/remove at an iterator position is O(1), but getting to that position is still O(n). Nodes are scattered in memory, so cache locality is poor.
• Practice: Use ArrayList in the vast majority of cases. For queues or double-ended queues, prefer ArrayDeque (backed by a circular array); do not use LinkedList as a general-purpose List or default queue implementation.

Example

Example 1: Index access — ArrayList wins

JavaCopy
List<String> list = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
    process(list.get(i));  // ArrayList: O(1) per access; LinkedList: O(n) per access
}

With frequent get(i), ArrayList is much faster. LinkedList must traverse from the head (or tail, whichever is closer) for each access.

Example 2: Tail append — both work, ArrayList uses less memory

JavaCopy
for (int i = 0; i < 100_000; i++) {
    list.add("item" + i);
}
// ArrayList: one backing array, contiguous memory
// LinkedList: 100k nodes, each with prev/next pointers and element — more overhead

Example 3: Iteration with removal — Iterator remove

JavaCopy
List<Integer> list = new ArrayList<>();  // or LinkedList
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (condition(it.next())) {
        it.remove();  // O(1) for LinkedList at iterator position; O(n) for ArrayList (shift)
    }
}

For ArrayList, it.remove() still requires shifting elements. For LinkedList, removal at the iterator position is O(1). If you are iterating and removing many elements, LinkedList can be faster, but in practice ArrayList often wins due to cache locality and lower allocation overhead.

Example 4: When LinkedList might help

JavaCopy
// Frequent insert/remove in the middle when you already have a ListIterator position
List<Integer> list = new LinkedList<>();
ListIterator<Integer> it = list.listIterator();
while (it.hasNext()) {
    if (condition(it.next())) it.remove();
    else it.add(someValue);  // O(1) at iterator position for LinkedList
}

Only when you already have an iterator and do not need random access does LinkedList's O(1) insert/remove at the current position help. Most algorithms do not have this pattern.

Comparison Table

Operation	ArrayList	LinkedList
get(i)	O(1)	O(n)
add(e) at end	O(1) amortized	O(1)
add(i, e)	O(n)	O(n) to locate + O(1) to insert
remove(i)	O(n)	O(n) to locate + O(1) to remove
Memory	Contiguous array, less overhead	Extra prev/next per element
Queue/Stack	Use ArrayDeque	Not recommended

Core Mechanism / Behavior

• ArrayList resize: When capacity is exceeded, a new array is allocated (typically 1.5× the old size) and elements are copied. Tail add is amortized O(1) because resize is rare.
• LinkedList: No capacity; each add allocates a new node. Deleted nodes become eligible for GC. Traversal and index access follow the chain of pointers.
• ArrayDeque: Circular array; head/tail operations are O(1). No get(i). Better than LinkedList for queue/stack in both speed and memory.

Key Rules

• Default to ArrayList: Iteration, index access, conditional filtering, and bulk operations all favor ArrayList. If you have many middle insertions/deletions, consider optimizing the algorithm (e.g. bulk moves, different data structure) before switching to LinkedList.
• For queue or deque, use ArrayDeque, not LinkedList.
• Consider LinkedList only when you have frequent insert/remove at an iterator position and do not need random access. Measure memory and latency; poor cache locality can outweigh the theoretical O(1) advantage.

What's Next

See Java Collections in Practice for collection overview. See HashMap Deep Dive for another common structure.