Java LinkedList

LinkedList<E> is a doubly-linked list: every element lives in its own heap node with a pointer to the next node and a pointer to the previous one. That gives it the opposite performance profile to ArrayList: insert and remove at the ends is O(1), but get(i) has to walk from one end to the index — O(n). The class is also Java's only built-in List that also implements Deque<E>, so it doubles as a queue. This chapter explains when that combination is the right tool, and the (slightly larger) list of cases where it isn't.

The data structure

Each element is a node:

node:  prev ←—— element ——→ next

The list keeps two field references — first and last — and a size counter. To add at either end, you allocate a node, splice it in by adjusting two pointers, and bump size. No array, no resize, no slack memory. That's the appeal.

The cost is everywhere else:

• Each element pays for a node object — three references and an object header. Memory overhead per element is much higher than ArrayList's flat array.
• get(i), set(i, x), add(i, x), remove(i) all walk from the closer end. So list.get(size/2) is O(n/2). For long lists, that compounds badly.
• Cache locality is poor — nodes are scattered across the heap, so traversal misses the CPU cache and slows down even when the algorithm looks linear.

When LinkedList is the right choice

The honest answer in 2026: rarely as a List, sometimes as a Deque, almost never to "speed up insertions." The folklore "use LinkedList because you'll be inserting" has not aged well — for most workloads, the cache-friendliness of ArrayList plus its O(1) amortised append beats the extra pointer-chasing of a linked list, even when the algorithm calls add(0, x) sometimes. The cases where LinkedList actually wins:

• You need a Deque (add/remove at both ends) and don't already have an ArrayDeque in scope. ArrayDeque is faster; LinkedList is more familiar.
• You hold persistent references to specific nodes (via ListIterator) and want O(1) insert/remove at those exact positions. This is the textbook linked-list use case — and it almost never comes up in everyday Java.
• You want a Queue implementation that also exposes List methods for inspection. Real example: a job queue that occasionally gets dumped to a log.

For "list I append to and read by index," reach for ArrayList. For "queue or deque," reach for ArrayDeque. LinkedList sits between them and is rarely the best fit for either job.

Creating one and using it as a List

The List half of the API is identical to ArrayList:

List<String> tasks = new LinkedList<>();
tasks.add(\"compile\");
tasks.add(\"test\");
tasks.add(0, \"lint\");           // O(1) — at the head
String first = tasks.get(0);   // O(1) — head
String last  = tasks.get(tasks.size() - 1);   // O(1) — tail
String mid   = tasks.get(tasks.size() / 2);   // O(n/2) — has to walk

The constructor has no capacity parameter — there's nothing to pre-size, because nodes are allocated one at a time.

Using it as a Queue and Deque

Because LinkedList implements both Queue<E> and Deque<E>, you get the queue methods on top of the List ones:

Deque<String> stack = new LinkedList<>();
stack.push(\"a\");          // adds to head
stack.push(\"b\");
String top = stack.pop(); // removes from head → \"b\"

Queue<String> jobs = new LinkedList<>();
jobs.offer(\"j1\");         // adds to tail
jobs.offer(\"j2\");
String next = jobs.poll();// removes from head → \"j1\"

If your need is purely "FIFO queue" or "LIFO stack," declare the variable as Queue<E> or Deque<E> — and prefer new ArrayDeque<>() as the implementation. The interface is the same; the array-backed implementation is measurably faster.

Iteration and ConcurrentModificationException

Same fail-fast model as ArrayList. Mutating during a for-each loop throws:

LinkedList<Integer> xs = new LinkedList<>(List.of(1, 2, 3, 4));
for (int x : xs) if (x % 2 == 0) xs.remove(Integer.valueOf(x));  // throws

removeIf and the explicit Iterator.remove() are the two safe forms — identical to the ArrayList chapter. The interesting twist for LinkedList is the ListIterator: because the iterator holds a direct reference to the current node, its add and remove are genuinely O(1). If you really do need fast insert-at-position iteration, LinkedList.listIterator() is the API that delivers what the textbook promises.

Thread safety

Same story as ArrayList: none. Use Collections.synchronizedList(new LinkedList<>()) for blanket locking, or — much better — a ConcurrentLinkedDeque if your use case is really a concurrent queue.

The ArrayDeque comparison in one paragraph

When you reach for LinkedList to use as a queue or stack, look at ArrayDeque first. ArrayDeque is a circular array — no per-element node, no pointer chasing, no null rejection rules to remember. In micro-benchmarks it's typically 2–10× faster than LinkedList for stack/queue workloads. It doesn't implement List, which is its only real disadvantage.

A worked example: same job, two data structures

The program below builds the same queue with ArrayList, LinkedList, and ArrayDeque — push to one end, pop from the other 200 000 times — and prints the wall clock for each. Read the numbers in context: ArrayList is slow here because remove(0) is O(n). LinkedList wins by a lot. ArrayDeque wins by even more.

Two takeaways:

• The first two timings show why never index a LinkedList in a loop. The for-each form walks the list once in O(n); the index-form walks it once per index, giving you O(n²). For 10 000 elements that's already painful; for 100 000 it's seconds.
• The three queue timings show why LinkedList rarely wins on its own merits: ArrayDeque is the better queue. The remaining genuine reason to use LinkedList is "I want a Deque and a List," and even that's rare.

What's next

LinkedList and ArrayList are the two interesting general-purpose List implementations. The third one — older, synchronised, mostly historical — is Vector. Knowing why it's not the right choice in new code is part of being fluent in the framework.

Practice