Skip to content
Tutorials Center
My learning

Topics

Lesson 81 of 201 Ā· Collections

LinkedList

Learn Java LinkedList - List and Deque methods, how its doubly linked nodes work, the get(i) trap, when it really helps, and an ArrayList vs LinkedList benchmark.

LinkedList stores its elements in a chain of small node objects, each pointing to the node before and after it. That makes it the textbook opposite of ArrayList: adding or removing at either end never shifts anything, but finding the element at index 5,000 means walking 5,000 links.

Textbooks often present it as the choice "when you insert and remove a lot". In real Java code it's almost never the best choice, and its own author has joked that he never uses it. This lesson shows you how LinkedList works, its complete API as both a List and a Deque, the trap that makes it painfully slow, and measurements that show when it does and doesn't pay off.

A List and a Deque in one

LinkedList implements two interfaces. As a List it has everything ArrayList has: add, get, set, remove, indexOf, subList. As a Deque (double-ended queue) it adds methods for both ends:

Java LinkedList as a list, a queue and a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The Deque methods come in pairs that differ only in how they handle failure:

Action Throws if it can't Returns a special value
Insert at front / back addFirst(e) / addLast(e) offerFirst(e) / offerLast(e) (return false)
Remove from front / back removeFirst() / removeLast() pollFirst() / pollLast() (return null)
Look at front / back getFirst() / getLast() peekFirst() / peekLast() (return null)

The queue and stack names are shortcuts: offer/poll/peek work at the back/front like a queue, and push/pop work at the front like a stack. There are also removeFirstOccurrence(o), removeLastOccurrence(o) and descendingIterator() for walking backward.

Since LinkedList and ArrayDeque both implement Deque, the same code works with either. Queues, Deques and PriorityQueue covers the Deque API in depth.

Each element lives in its own node with three fields: the element, a link to the previous node and a link to the next one. The list itself only remembers the first node, the last node and the size:

TEXT
 first                                         last
   │                                             │
   ā–¼                                             ā–¼
 ā”Œā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”      ā”Œā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”      ā”Œā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”
 │ prev: ─  │ ◄─── │ prev     │ ◄─── │ prev     │
 │ item: A  │      │ item: B  │      │ item: C  │
 │ next     │ ───► │ next     │ ───► │ next: ─  │
 ā””ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”˜      ā””ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”˜      ā””ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”€ā”˜

Inserting means creating one node and rewiring four links; nothing moves. But there's no way to jump to the middle: to reach index i, the list starts from whichever end is closer and follows links one by one. Here is a stripped-down version of the same idea, so you can see the link updates happen:

Java A tiny doubly linked list, built by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The real java.util.LinkedList works the same way, with generics and a size counter. You'll build complete versions of this structure in Data Structures in Java.

Those nodes have a cost. Each one is a separate object of roughly 24 bytes on a typical 64-bit JVM, plus the element itself, compared with about 4 bytes per reference slot in an ArrayList's array. Worse, nodes are scattered around the heap, so walking the list jumps between memory locations and defeats the CPU cache, while an array is read in one smooth sweep.

The get(i) trap

Because LinkedList implements List, code like this compiles and looks innocent:

Java
for (int i = 0; i < list.size(); i++) {
    process(list.get(i));
}

With an ArrayList that's fine. With a LinkedList, every get(i) walks from an end to position i, so the loop does about n²/4 steps. For 20,000 elements that's 100 million link hops:

Java Index loops on a LinkedList are quadratic

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The index loop over the LinkedList is dramatically slower than the other two; the exact numbers vary from run to run. The fix is simple: iterate lists with for-each, an Iterator or forEach, which follow the links in order. Library code checks for the RandomAccess marker interface (implemented by ArrayList, not by LinkedList) to decide whether index access is cheap.

The same trap hides in innocent-looking places. A method that takes a List parameter and loops by index is fine for every caller that passes an ArrayList, and quietly quadratic for the one caller that passes a LinkedList. Binary search by index, Collections.swap in a loop, or "get the middle element" all suffer in the same way. That's another reason to write loops with for-each by default.

Other operations with the same hidden walk: get(i), set(i, e), add(i, e) and remove(i) all cost O(n) on a LinkedList, because they first have to find position i.

Where LinkedList actually wins

The promise of cheap insertion only holds when you're already at the position. That's what a ListIterator gives you: it remembers its node, so add and remove through the iterator are O(1). Inserting after every element of a list is a fair test:

Java Editing through a ListIterator

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Here LinkedList wins clearly, since each ArrayList insert shifts the rest of the array. Note how specific the scenario is: one pass, with many insertions in the middle of a large list, all done through an iterator. And even then, building a new ArrayList while reading the old one (or calling removeIf for removals) is usually just as fast.

The benchmark that matters: queues

The most common reason people pick LinkedList is a queue: add at the back, remove from the front. ArrayList.remove(0) is O(n), so LinkedList beats it easily. But ArrayDeque, a circular array with no shifting and no per-element nodes, beats both:

Java Queue workload: ArrayList vs LinkedList vs ArrayDeque

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The times are in microseconds (µs, millionths of a second). Typical results: ArrayList with remove(0) is the slowest by far, tens of thousands of microseconds, because every removal shifts the whole array. ArrayDeque is at least as fast as LinkedList, usually faster, while using much less memory: it allocates no node objects, so the garbage collector has almost nothing to clean up afterward. Timings in a shared online sandbox jump around, so run it a few times and compare the order rather than the exact milliseconds. Serious benchmarks use a harness like JMH (Java Performance Tips).

ArrayList vs LinkedList vs ArrayDeque

Operation ArrayList LinkedList ArrayDeque
get(i) / set(i, e) O(1) O(n) not available
add/remove at the end O(1) amortized O(1) O(1) amortized
add/remove at the front O(n) O(1) O(1) amortized
add/remove via an iterator in the middle O(n) O(1) only removal, O(n)
contains O(n) O(n) O(n)
memory per element one reference (+ spare capacity) a 24-byte node + links one reference (+ spare capacity)
null elements allowed allowed rejected

The practical guidance:

  • Need a list? Use ArrayList.
  • Need a queue, stack or deque? Use ArrayDeque.
  • Use LinkedList only when you need one object that is both a List and a Deque, need null elements in a deque, or have measured a workload of many iterator-based insertions and removals in the middle of a large list.

Check your understanding

Quick check Ā· 5 questions

of 5 answered You scored / 5 Ā· perfect!

  1. 1. What does this print? Deque<Integer> d = new LinkedList<>(); d.push(1); d.push(2); d.addLast(3); System.out.println(d);

    push adds at the front, so after two pushes the deque is [2, 1]. addLast then appends 3 at the back.
  2. 2. Why is for (int i = 0; i < list.size(); i++) list.get(i); slow on a large LinkedList?

    LinkedList has no index-based access. Every get(i) walks up to n/2 nodes, so n calls do about n²/4 steps. A for-each loop is O(n).
  3. 3. What does pollFirst() return on an empty LinkedList?

    The poll and peek methods return null for an empty deque; removeFirst and getFirst throw NoSuchElementException instead.
  4. 4. You need a FIFO queue of tasks (no nulls) for a busy server. Which class is usually the best choice?

    ArrayDeque gives O(1) operations at both ends without allocating a node per element, so it is usually faster and smaller than LinkedList. ArrayList.remove(0) is O(n).
  5. 5. In which situation does LinkedList genuinely beat ArrayList?

    A ListIterator is already positioned at its node, so add and remove through it are O(1). In ArrayList each such insertion shifts the rest of the array.

Summary

  • LinkedList is a doubly linked list of nodes that implements both List and Deque.
  • Deque methods come in throwing (addFirst, removeFirst, getFirst) and special-value (offerFirst, pollFirst, peekFirst) forms; push/pop work at the front.
  • Adding and removing at the ends is O(1), but get(i), set(i, e), add(i, e) and remove(i) must walk the list: O(n).
  • Never loop over a LinkedList by index; use for-each or an iterator.
  • LinkedList wins mainly for iterator-based insertions and removals in the middle of large lists.
  • Each node costs extra memory and cache misses; use ArrayList for lists and ArrayDeque for queues and stacks.

Next: HashMap, the collection that finds a value by its key in constant time.