Brewlearn Get the app
🗃️ Collections Framework · Intermediate

LinkedList in Java

Doubly linked list; O(n) get, rarely the right choice.

🧩 The mysteryLinkedList can insert in O(1)... in theory. Yet swap it in for ArrayList and your code often gets SLOWER. Let's find out why.

A treasure hunt of nodes

A LinkedList is a chain of nodes. Each node holds an element plus links to the previous and next node. There's no array, so to reach index i it must walk node by node (from whichever end is nearer): get(i) is O(n).

null ← [a] ⇄ [b] ⇄ [c] → null
         head            tail

Cheap at both ends

Adding or removing at either end only rewires a couple of links: O(1). LinkedList implements **both List and Deque**, so it has get(i) as well as addFirst, addLast, removeFirst, removeLast.

LinkedList<String> l = new LinkedList<>();
l.addFirst("b");   // [b]
l.addFirst("a");   // [a, b]
l.addLast("c");    // [a, b, c]
🔮 Predict it

Your turn

What does this print?

LinkedList<String> l = new LinkedList<>();
l.addLast("b");
l.addFirst("a");
l.addLast("c");
System.out.println(l.removeFirst() + " " + l);
  1. a [b, c]
  2. c [a, b]
  3. b [a, c]
Show the answer

addLast("b") → [b], addFirst("a") → [a, b], addLast("c") → [a, b, c]. removeFirst() returns a and leaves [b, c].

🤔 Think first

The O(1) insert myth

Linking in a new node is O(1). So why is list.add(i, x) at random positions usually slower on a LinkedList than on an ArrayList?

Think about it, then reveal the answer

Before linking, it must walk O(n) nodes to reach position i. The nodes are scattered in memory, so the CPU cache keeps missing. ArrayList's shift is one fast block copy (System.arraycopy) over contiguous memory.

Looping over a LinkedList

✗ O(n²)
for (int i = 0; i < names.size(); i++) {
    String n = names.get(i); // walks!
}

Every get(i) walks the chain again from an end.

✓ O(n)
for (String n : names) {
    System.out.println(n);
}

for-each follows the links once, start to finish.

💼 In the real world

Rarely the right tool

In real code, ArrayList wins for lists and ArrayDeque wins for queues and stacks. Each LinkedList node is a separate object, so it also uses much more memory. If you see get(i) inside a loop over a LinkedList in code review, flag it.

Key takeaways

  1. Doubly linked: each node points to prev and next
  2. get(i) is O(n) — it walks from the nearer end
  3. addFirst/addLast/removeFirst/removeLast are O(1)
  4. Scattered nodes hurt CPU caching, so it's rarely the best choice

💡 A LinkedList is a treasure hunt: each clue tells you where the next one is, so finding clue 500 means following 499 clues first.

🤯 Did you know?

Joshua Bloch, who wrote Java's LinkedList, joked on Twitter in 2015: "Does anyone actually use LinkedList? I wrote it, and I never use it."

Practice questions

On a LinkedList of n elements, what is the cost of get(n / 2)?

  1. O(1)
  2. O(log n)
  3. O(n)
  4. O(n²)
Check your answer

O(n). There's no array to jump into, so LinkedList walks node by node (starting from whichever end is closer). Halfway through is still about n/2 steps: O(n).

What does this print?

LinkedList<Integer> q = new LinkedList<>();
q.addFirst(2);
q.addFirst(1);
q.addLast(3);
System.out.println(q.removeLast() + " " + q);
  1. 3 [1, 2]
  2. 1 [2, 3]
  3. 3 [2, 1]
  4. 2 [1, 3]
Check your answer

3 [1, 2]. addFirst(2) then addFirst(1) gives [1, 2]; addLast(3) gives [1, 2, 3]. removeLast() returns 3 and leaves [1, 2].

Next: list.remove(1) on a list of numbers. Does it remove the number 1, or the item at index 1? Java has a surprising answer.