skip to content

List Implementations

The ordered, indexed collections — ArrayList, LinkedList and the view types — and the backing structures that give them their very different cost profiles. The ArrayList-versus-LinkedList question is nearly guaranteed to appear.

part ofJavaread it →
on this pageshow

explore

questions

20

What is the fundamental difference between ArrayList and LinkedList in Java, and how does it affect their performance characteristics?

level: juniorimportance: must knowfreq 85%

answer

  1. Array (contiguous, indexable) vs nodes (separate, linked)
  2. get(i): O(1) vs O(n)
  3. ArrayList middle insert = shift; LinkedList middle insert = traverse then relink
  4. LinkedList = 2 extra pointers/node + weaker cache locality
  5. Default to ArrayList

basics

~20 s

ArrayList stores elements in a resizable array, so reading any element by index is instant. LinkedList stores elements as separate nodes connected by links, so reading by index means walking the chain. ArrayList is faster for most uses.

solid answer

~50 s

Both implement the List interface but use opposite internal structures. ArrayList is backed by a contiguous array, giving O(1) random access by index (get/set) and good cache locality, but inserting or removing in the middle requires shifting all later elements (O(n)). LinkedList is a doubly linked list of nodes, each holding the value plus references to the previous and next node; it has O(1) insert/remove at the ends or once you hold a node, but get(index) is O(n) because it must traverse. LinkedList also uses more memory per element (two extra pointers per node, plus an object header) and usually has worse cache locality, since each node is a separate heap object that can land anywhere. In practice ArrayList is the default choice; LinkedList rarely wins because traversal cost and pointer overhead usually outweigh its theoretical insertion advantage.

go deeper

for a junior

Knows ArrayList uses an array and LinkedList uses linked nodes, and that ArrayList's get by index is fast while LinkedList's is slow; defaults to ArrayList.

for a middle

States the Big-O table correctly, explains the shift-vs-relink tradeoff, and notes memory overhead and that append is amortized O(1).

for a senior

Explains why ArrayList wins even at middle insertion (traversal cost + cache locality + constant factors), and when LinkedList genuinely helps (iterator removal, deque ends), suggesting ArrayDeque as a better deque.

for a principal

Frames the choice around real workload profiles and hardware (cache lines, prefetch, allocation pressure/GC), can reason about amortized analysis, and sets team conventions defaulting to ArrayList while justifying rare exceptions with measurement.

## What a List is In Java, `List` is an interface — a contract that says "an ordered collection you can access by integer position (index)." `ArrayList` and `LinkedList` are two **implementations** of that same contract. They behave identically from the outside (`add`, `get`, `remove`, `size`) but store the data completely differently inside, which is why their speed differs. ## ArrayList: backed by an array An **array** is a single block of memory holding elements one after another, like numbered boxes in a row. `ArrayList` wraps a resizable array. - **Random access — `get(i)` / `set(i)`** is **O(1)** (constant time): the computer computes the memory address directly as `base + i * elementSize` and jumps straight there. No matter how large the list, fetching element 5 or element 5,000,000 costs the same. - **Insert/remove in the middle** is **O(n)** (linear time): to insert at position `i`, every element from `i` onward must be **shifted** one slot to make room (or to close the gap on removal). With a million elements, inserting near the front moves ~a million elements. - **Append at the end** is **amortized O(1)**: usually instant, but when the array fills up, `ArrayList` allocates a bigger array (typically ~1.5x) and copies everything over. That occasional copy is spread ("amortized") over many cheap appends, so the average stays constant. - **Memory**: just the array plus some slack capacity. No per-element overhead beyond the references themselves. - **Cache locality**: excellent for the array itself. The element references sit contiguously in memory, so the CPU's cache loads neighbors together and iterating is very fast in practice. ## LinkedList: a chain of nodes A **node** is a small object holding one value plus references (pointers) to other nodes. Java's `LinkedList` is **doubly linked**: each node points to both the **next** and the **previous** node. The list keeps references to the first and last nodes. - **Random access — `get(i)`** is **O(n)**: there is no formula for "where is element i." You must start at the head or the tail, whichever is closer, and **walk** the chain step by step. In a 10-million-element list, element 5,000,000 takes about five million hops. - **Insert/remove once you already hold the node** is **O(1)**: you just rewire a few pointers (relink the neighbors). This is its one structural strength — e.g. removing via an `Iterator` during traversal. - **Insert/remove at the ends** is **O(1)**: it has direct references to first and last, which is why it's a natural `Deque`/queue. - **Memory**: high overhead. Every element needs a separate node object, and each node carries **two extra references** (prev + next) plus an object header: 24 bytes per node against a 4-byte `ArrayList` slot when references are compressed. - **Cache locality**: weaker, and it degrades. Each node is a separate heap object with no layout guarantee, so as nodes scatter the CPU cache helps less; even plain iteration is slower than `ArrayList` despite both being O(n). ## The crucial subtlety: insertion in the middle People often say "LinkedList is better for inserting in the middle." The pointer **relink** itself is O(1) — but **finding** the middle position is O(n) for LinkedList (you must traverse to it). For ArrayList, finding is O(1) but the **shift** is O(n). So both are O(n) for an arbitrary-position insert; ArrayList's O(n) is a fast contiguous `System.arraycopy` (memory block move), while LinkedList pays an O(n) traversal, often with cache misses. That's why ArrayList usually still wins even at the task LinkedList supposedly excels at — unless you already hold the position (e.g. an iterator) or the index is near the front, where LinkedList's walk is short and ArrayList's shift is longest. ## Big-O summary | Operation | ArrayList | LinkedList | |---|---|---| | `get(i)` / `set(i)` | O(1) | O(n) | | `add` at end | amortized O(1) | O(1) | | `add`/`remove` at front | O(n) | O(1) | | `add`/`remove` middle (by index) | O(n) (shift) | O(n) (traverse) + O(1) relink | | remove via iterator at cursor | O(n) (shift) | O(1) | | memory per element | low | high (2 pointers/node) | | cache locality | good | weaker, worse once nodes scatter | ## Why ArrayList is the default For the overwhelming majority of real workloads — build a list, iterate it, look things up by index — ArrayList is faster and leaner. Modern CPUs reward contiguous memory heavily (cache), so even LinkedList's theoretical edges rarely materialize. The standard advice: **default to ArrayList; reach for LinkedList only when you genuinely need a queue/deque with heavy add/remove at both ends, or O(1) removal while iterating.** Even then, `ArrayDeque` is usually a better deque than `LinkedList`.

  • If an arbitrary-index insert is O(n) on both, why does ArrayList usually still beat LinkedList at it?
    ArrayList's O(n) is a single contiguous System.arraycopy (cache-friendly block move), while LinkedList must traverse node-by-node to reach the index, often with cache misses, before its O(1) relink. The constant factors and cache behavior favor ArrayList, except near the front, where the walk is short and the shift is longest.
  • When does LinkedList's O(1) insertion actually pay off?
    When you already hold the position — e.g. removing/inserting via an Iterator during traversal, or pushing/popping at the ends as a queue/deque — so you skip the O(n) search entirely.

  • Claiming LinkedList is faster for middle insertion overall — finding the spot is still O(n) traversal
  • Saying ArrayList add() is O(n) — it's amortized O(1) at the end
  • Forgetting LinkedList get(i) is O(n), not O(1)
  • Ignoring cache locality and pretending only Big-O matters
  • Recommending LinkedList as a general default

context

open as a page

What is an ArrayList in Java, and how does it store its elements?

level: juniorimportance: must knowfreq 85%

basics

~10 s

An ArrayList is a resizable list backed by an array. You can add items without picking a size up front, and you read any item by its position (index) quickly.

open as a page

What is the internal data structure of java.util.LinkedList, and how does it differ from ArrayList?

level: juniorimportance: must knowfreq 78%

basics

~20 s

LinkedList stores each element in a separate node that points to the next and previous nodes (a doubly-linked list). ArrayList stores elements in a single backing array. So LinkedList chases pointers; ArrayList uses index math.

open as a page

What does List.subList(from, to) return, and how does it relate to the original list?

level: juniorimportance: must knowfreq 55%

basics

~20 s

subList(from, to) returns a view of part of the original list, not a copy, from inclusive to to exclusive. Changes to the view reach the original, and element updates in the original reach the view.

open as a page

What happens if you modify an ArrayList while iterating over it, and how do you handle it correctly?

level: middleimportance: must knowfreq 78%

basics

~10 s

Changing an ArrayList's size while looping over it with its iterator usually throws ConcurrentModificationException. To remove during iteration, use the iterator's own remove() method, or skip the loop and use removeIf.

open as a page

How does an ArrayList grow when it runs out of space, and what is the cost?

level: middleimportance: must knowfreq 80%

basics

~20 s

When the internal array is full and you add an item, ArrayList makes a bigger array (about 1.5x), copies everything over, then adds the new item. That copy is occasional, so adding is fast on average.

open as a page

Given a real-world scenario, how do you decide between ArrayList and LinkedList — and why is ArrayList almost always the right default?

level: middleimportance: must knowfreq 70%

basics

~20 s

Use ArrayList by default — it's faster for reading by index and uses less memory. Only consider LinkedList for constant adds or removes at or near the start, at the end, or through an iterator. At the ends, ArrayDeque is usually better.

open as a page

For LinkedList, what is the time complexity of get, add-at-end and remove-from-middle, and why is middle insertion not really O(1) in practice?

level: middleimportance: must knowfreq 72%

basics

~20 s

get(i) is O(n) because you walk the chain. Adding/removing at the ends is O(1). Removing a known node is O(1), but finding that middle position first costs O(n), so a middle insert is really O(n) overall.

open as a page

How do List.indexOf and List.contains decide whether an element matches, and why does overriding equals matter?

level: middleimportance: must knowfreq 62%

basics

~20 s

indexOf and contains find an element by comparing with equals, not by reference (==). For a custom class to be found, it must override equals correctly; otherwise the default equals compares object identity and lookups fail unless it is the exact same object.

open as a page

Why can a subList view throw ConcurrentModificationException, and how do you avoid it?

level: middleimportance: must knowfreq 48%

basics

~20 s

A subList view becomes invalid if you structurally change the original list (add or remove elements) through some other reference. The next time you use the view, it usually throws ConcurrentModificationException. Avoid it by using the view only within a short scope.

open as a page

Why are insertion and removal in the middle of an ArrayList O(n), and when does that matter?

level: middleimportance: should knowfreq 70%

basics

~20 s

To insert or remove in the middle, ArrayList has to shift every element after that spot by one position so there are no gaps. The more elements after the spot, the more shifting, so it costs O(n).

open as a page

How does Vector differ from ArrayList in Java, and why is Vector treated as a legacy class?

level: middleimportance: should knowfreq 62%

basics

~20 s

Vector is ArrayList's older, synchronized sibling: nearly every call takes its own lock, and it doubles when full or adds a fixed capacityIncrement. It predates the Collections Framework, ArrayList suits unshared lists, and per-call locks leave compound actions unsafe, hence legacy.

open as a page

Why is ArrayList's add() at the end 'amortized O(1)' when a full backing array must be copied?

level: middleimportance: should knowfreq 50%

basics

~20 s

ArrayList keeps a fixed-size array inside. Adding is instant until it's full; then it makes a bigger array (about 1.5x) and copies everything over. That copy is occasional and spread across many cheap adds, so on average each add is constant time.

open as a page

When is an ArrayList the wrong choice in Java, and what should you use instead?

level: seniorimportance: should knowfreq 75%

basics

~20 s

ArrayList is wrong when the main work is at the front (use ArrayDeque), lookup by value (HashSet or HashMap), priority or sorted order (PriorityQueue, TreeMap), sharing with writer threads (concurrent collections), or large primitive data (int[]).

open as a page

Why is iterating a LinkedList with a for-i index loop a performance trap, and what's the correct way to traverse it?

level: seniorimportance: should knowfreq 45%

basics

~20 s

In a LinkedList, get(i) has to walk from the nearer end each time, so a loop calling get(0), get(1), get(2)... re-walks the chain repeatedly and becomes very slow (O(n^2)). Use an enhanced for-loop or iterator instead, which walks the chain just once.

open as a page

For ArrayList versus LinkedList, why do memory overhead and cache locality often matter more than Big-O?

level: seniorimportance: should knowfreq 55%

basics

~20 s

LinkedList uses much more memory because every element is a separate object with two extra links. Its nodes can scatter across the heap, so the CPU cache helps less, making it slower in real use even when Big-O looks equal.

open as a page

How does LinkedList implement the Deque and Queue interfaces, and why might you still prefer ArrayDeque?

level: seniorimportance: should knowfreq 58%

basics

~20 s

LinkedList implements Deque (a double-ended queue) and Queue, so it offers addFirst/addLast/peek/poll in O(1) and can act as a stack, queue, or deque. But ArrayDeque is usually faster and lighter, so it is the preferred choice.

open as a page

When is using List.contains/indexOf for membership testing the wrong choice, and what should you use instead?

level: seniorimportance: should knowfreq 40%

basics

~10 s

List.contains/indexOf scan the list until a match, so each check is O(n). If you do many membership checks, that becomes slow (O(n*m)). Use a HashSet instead, which checks membership in roughly O(1) on average.

open as a page

How do you delete a contiguous range from an ArrayList efficiently, and why is subList(...).clear() the idiomatic approach?

level: seniorimportance: should knowfreq 35%

basics

~10 s

Use list.subList(from, to).clear(). Because the sublist is a view of the original, clearing it removes that whole range from the original list in one operation, instead of removing elements one at a time.

open as a page

In real-world systems, when is LinkedList actually the right choice, and why is it so rarely used in practice?

level: principalimportance: should knowfreq 48%

basics

~20 s

LinkedList is rarely the best choice. ArrayList wins for most list work and ArrayDeque wins for queues/stacks because both are faster and use less memory. LinkedList only fits niche cases like heavy iterator-based middle edits or needing List and Deque in one object.

open as a page