PHASE 9Intermediate ~29 min· topic 3 of 13

Topic 9.3

LinkedList

In one line

LinkedList is a doubly linked list: a chain of node objects, each pointing to the one before and after. Adding or removing at either end is O(1), but reaching index i means walking node by node, so get(i) is O(n), and in practice ArrayList or ArrayDeque is almost always the better choice.

Think of it like this

A treasure hunt. Each clue tells you where the next clue is, and (in this version) also where the previous one was. Starting a new hunt from the first or last clue is instant, and slipping a new clue between two others only means changing two notes. But to find the 50th clue there's no shortcut: you follow the chain one clue at a time. That's a linked list.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Node: A small object holding one element plus links to its neighbours.
Doubly linked: Each node points both to the next node and to the previous one, so you can walk forwards and backwards.
Head and tail: The first and last nodes of the chain (first and last in the JDK code).
Traversal: Walking through the chain from node to node.
ListIterator: An iterator for lists that can move both ways and add, set or remove at its current position.
Cache miss: When the CPU needs data that isn't in its fast nearby memory and must wait for slower main memory. Scattered nodes cause many.
Deque: A "double-ended queue": a sequence you can add to and remove from at both ends.

Step by step

01The shape in memory

After adding "a", "b" and "c", the LinkedList object holds first (the node for a), last (the node for c) and size = 3. Each node is its own heap object; they can be anywhere in memory.

Compare with Topic 9.2: an ArrayList keeps one array whose slots sit side by side. The linked list trades that contiguity for cheap relinking.

The shape in memorydiagram

Rendering diagram…

02Adding at the end: link a new node

addLast(e) (and plain add(e)) creates new Node<>(last, e, null), sets the old last node's next to it, and moves last. If the list was empty, first points at it too. No copying, no growing: O(1) every time, not just on average.

addFirst is the mirror image. Removing an end unlinks the node and clears its fields so it doesn't keep its neighbours reachable.

LinkedList.java (simplified from the JDK)whole filejava

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) { ... }
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null) first = newNode;   // the list was empty
    else l.next = newNode;
    size++;
    modCount++;
}

03get(i): walking from the nearer end

get(i) calls node(i): if i < (size >> 1) it starts at first and follows next i times; otherwise it starts at last and follows prev size - 1 - i times. For a 1,000-element list, get(500) makes about 500 hops.

Each hop is a memory load that depends on the previous one, so the CPU can't fetch ahead. That's why walking a linked list is much slower per element than scanning an array, even when both are O(n).

LinkedList.java (simplified from the JDK)whole filejava

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) x = x.prev;
        return x;
    }
}

04The O(n²) loop hiding in plain sight

for (int i = 0; i < list.size(); i++) total += list.get(i); looks linear, but on a LinkedList each get(i) walks from an end. The hops add up to about n²/4. For 100,000 elements that's 2.5 billion hops.

Loop with for-each (which uses the iterator and moves one node per step) and the same work is O(n). Code that must work on any List should iterate, not index, unless it checks list instanceof RandomAccess.

05Insert in the middle with a ListIterator

A ListIterator remembers where it is. it.add(e) links a new node right there by changing four references, and it.remove() unlinks the last returned node. Each is O(1).

This is the one pattern where LinkedList really beats ArrayList: one pass that inserts or removes many elements as it goes. An ArrayList doing the same with it.add shifts the tail on every insert.

Main.javawhole filejava

ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    if (it.next().equals("b")) {
        it.add("x");          // O(1): link a node after "b"
    }
}

06As a queue and a stack

Because it implements Deque, a LinkedList offers offer/poll/peek (queue), push/pop (stack, working at the front) and all the First/Last methods. It's the only standard deque that allows null elements, which is a mixed blessing: poll() returns null both for "empty" and for a stored null.

ArrayDeque does all of this faster, with less memory and no garbage per element, so prefer it unless you need nulls or the List methods too.

terminal

$ java Main

── expected output ──

Exception in thread "main" java.util.NoSuchElementException

at java.base/java.util.LinkedList.removeFirst(LinkedList.java:281)

at Main.main(Main.java:6)

Try it yourself

1
Predict the hop counts
In the hops example, add list.get(4) and list.get(6) for the 10-element list. Predict the hops for each (4 and 3), then run.
2
Swap LinkedList for ArrayList
In the ListIterator example, change new LinkedList<> to new ArrayList<>. Predict whether the output changes. (It doesn't: the behaviour is the same, only the cost of each it.add differs, because the array must shift its tail.)
3
Measure your own data
Extend the indexed-vs-iterator example with n = 1,000,000 (use long). Predict roughly how many hops the indexed loop needs (about 2.5 × 10¹¹) before you run it.

Code & diagrams

Both ends are cheap: LinkedList as list, queue and stack New tab

Expected output

list: [a, b, c], first a, last c
poll: job1, left [job2]
pop: plate2, left [plate1]
pollFirst on empty: null
removeFirst on empty: NoSuchElementException

Build a doubly linked list and count the hops New tab

Index 5 of 10 isn't below size/2, so the walk starts at the tail.

Expected output

get(0) walked 0 hops
a
get(3) walked 3 hops
d
get(5) walked 4 hops
f
get(9) walked 0 hops
j

Indexed loop vs iterator: counting the hidden work New tab

Ten times more elements means a hundred times more hops for the indexed loop: that's O(n²).

Expected output

n=1000: indexed loop 249500 hops, iterator 999 hops
n=10000: indexed loop 24995000 hops, iterator 9999 hops
n=100000: indexed loop 2499950000 hops, iterator 99999 hops

ListIterator: O(1) insert and replace where you stand New tab

Expected output

[wake, brush, rinse, eat breakfast, brush, rinse, sleep]
first letters backwards: srberbw

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Remove from an empty LinkedList

Write LinkedList<String> jobs = new LinkedList<>(); String next = jobs.removeFirst();.

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.util.NoSuchElementException

at java.base/java.util.LinkedList.removeFirst(LinkedList.java:281)

at Main.main(Main.java:6)

Break #2

Call addFirst through a List variable on Java 17

Declare List<String> jobs = new LinkedList<>(); and call jobs.addFirst("urgent");, compiling with --release 17.

terminal

$ javac --release 17 Main.java

── what you'll see ──

Main.java:6: error: cannot find symbol

jobs.addFirst("urgent");

symbol: method addFirst(String)

location: variable jobs of type List<String>

1 error

Myth vs fact

Myth

LinkedList inserts in the middle in O(1).

Fact

Only once you're at the node. Reaching index i is an O(n) walk, so list.add(i, e) is O(n), the same Big-O as ArrayList and usually slower in practice.

Myth

LinkedList is the right class for a queue.

Fact

It works, but ArrayDeque is faster and uses far less memory. Use LinkedList as a queue only if you need null elements.

Myth

LinkedList uses less memory because it doesn't over-allocate.

Fact

Each element costs a whole node object (about 24 bytes) versus a 4-byte array slot plus up to a third spare capacity in an ArrayList. The linked list is several times bigger.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
With compressed object pointers (the default for heaps under 32 GB), a LinkedList.Node has a 12-byte header and three 4-byte references: 24 bytes. A million-element LinkedList spends about 24 MB on nodes alone; an ArrayList spends about 4 MB on its array.
▸
LinkedList doesn't implement RandomAccess, so Collections.binarySearch falls back to an iterator-based search that still does O(log n) comparisons but O(n) node hops. Sorting is done by copying into an array (toArray), sorting that, and writing back through a ListIterator.
▸
Every add allocates a node, which is garbage later. In allocation-heavy services, swapping a LinkedList queue for ArrayDeque can measurably cut GC pressure.
▸
LinkedList is not thread-safe. The JDK's concurrent linked structures (ConcurrentLinkedQueue, ConcurrentLinkedDeque, LinkedBlockingQueue) are separate, lock-free or lock-based designs (Topic 13.8).

Remember this

1
LinkedList stores each element in a separate node object with three fields: item (the element), next and prev (references to the neighbouring nodes). The list itself keeps first, last and size. Because each node knows both neighbours, it's a doubly linked list and can be walked in either direction.
2
Ends are cheap. addFirst, addLast, removeFirst, removeLast, getFirst and getLast only touch the first or last node and change a couple of references: O(1), with no array to grow and no elements to shift.
3
The middle is slow. get(i), set(i, e), add(i, e) and remove(i) must first walk to node i. The JDK starts from whichever end is closer (i < size / 2 walks from first), so it's at most n/2 hops, but that's still O(n). A loop like for (int i = 0; i < list.size(); i++) list.get(i) is therefore O(n²).
4
The O(1) middle insert people quote is only true when you're already standing at the node: through a ListIterator, it.add(e) and it.remove() relink in O(1). Finding the position is still the O(n) walk.
5
LinkedList implements both List and Deque, so it can be a list, a queue or a stack, and it accepts null elements. Memory is its weak point: each node is an object of about 24 bytes (with compressed references) on top of the element, versus 4 bytes per slot in an ArrayList. Nodes are scattered across the heap, so walking them causes CPU cache misses.
6
The modern advice is blunt: for a list, use ArrayList; for a queue, stack or deque, use ArrayDeque (Topic 9.7). LinkedList wins only in narrow cases, such as many inserts and removals at positions you reach with an iterator you already hold. For linked-list algorithms themselves (reversing, cycle detection, merging), see the DSA course's Linked Lists module (/dsa/linked-lists), where you build the nodes yourself.

Explain it without notes

Describe how LinkedList stores elements and what get(i) does.

When is LinkedList genuinely better than ArrayList?

Why is for (int i = 0; i < list.size(); i++) list.get(i) dangerous on a LinkedList?

Compare LinkedList and ArrayDeque as a queue.

Practice

Use a LinkedList as a stack to check whether the brackets in "{[()()]}" and "([)]" are balanced. Print true/false for each.

With a ListIterator, remove every element equal to "ad" from [news, ad, sport, ad, weather] in one pass and print the list.

Write a method that reverses a LinkedList<Integer> in place by repeatedly moving the last element to a growing position from the front, using removeLast and add(index, e). Print the result for [1, 2, 3, 4]. Then explain in a comment why Collections.reverse is better.

Trade-offs

↔
LinkedList gives true O(1) at both ends without ever copying, so no single operation is slow. ArrayDeque is O(1) amortised with an occasional grow, but faster on average and far smaller.
↔
Iterator-based splicing in the middle is O(1) per change in a LinkedList and O(n) in an ArrayList. Unless the list is large and the edits many, the array's cache-friendliness still wins; measure before switching.
↔
Allowing null elements is convenient but makes poll() and peek() ambiguous. ArrayDeque's refusal of null is a deliberate design choice.

Done when you can

Done when you can draw the nodes of a doubly linked list and the first/last fields.
Done when you can give the Big-O of get(i), addFirst, removeLast and add(i, e) on a LinkedList.
Done when you can spot the O(n²) indexed loop and fix it with an iterator.
Done when you can use a ListIterator to add, set and remove while walking.
Done when you can explain why ArrayList and ArrayDeque are usually better choices.

Command Palette

Words you'll meet

Step by step

01The shape in memory

02Adding at the end: link a new node

03get(i): walking from the nearer end

04The O(n²) loop hiding in plain sight

05Insert in the middle with a ListIterator

06As a queue and a stack

Try it yourself

Predict the hop counts

Swap LinkedList for ArrayList

Measure your own data

Code & diagrams

Break it on purpose

Remove from an empty LinkedList

Call addFirst through a List variable on Java 17

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can