LinkedList

LinkedList is a list implementation in which each element is stored in its own node, and each node holds references to the previous and next nodes. This structure, a doubly linked list, makes adding and removing at either end very fast, and allows insertion or removal in the middle without shifting other elements. LinkedList implements both the List interface and the Deque (double-ended queue) interface, so it can act as a list, a queue, or a stack.

How a Linked List Is Structured

        first                                       last
          │                                           │
          ▼                                           ▼
null ◄─ [prev|"A"|next] ◄─► [prev|"B"|next] ◄─► [prev|"C"|next] ─► null

• Each element lives in a separate node object on the heap.
• The list keeps references to the first and last nodes.
• Nodes are linked in both directions, so the list can be walked forward or backward.

Compare this with ArrayList, which stores all element references in one contiguous array. That difference determines which operations are fast for each.

Creating a LinkedList

import java.util.LinkedList;
import java.util.List;

LinkedList<String> tasks = new LinkedList<>();
LinkedList<Integer> numbers = new LinkedList<>(List.of(3, 1, 4));

Declare the variable as LinkedList when you need its Deque methods (addFirst, pollLast, ...). If you use it only as a list, declare it as List<String>, or as Deque<String> when you use it as a queue.

List Operations

LinkedList supports every List method:

List<String> list = new LinkedList<>();
list.add("Ada");
list.add("Linus");
list.add(1, "Grace");             // insert at index 1
System.out.println(list);         // [Ada, Grace, Linus]
System.out.println(list.get(2));  // Linus
list.remove("Ada");
System.out.println(list.size());  // 2

These behave exactly as they do for ArrayList. Only their performance differs.

Operations at Both Ends

The methods that make LinkedList distinctive come from the Deque interface:

LinkedList<String> queue = new LinkedList<>();

queue.addFirst("B");         // [B]
queue.addFirst("A");         // [A, B]
queue.addLast("C");          // [A, B, C]

String first = queue.getFirst();     // "A" (throws if empty)
String last = queue.peekLast();      // "C" (returns null if empty)

queue.removeFirst();                 // removes and returns "A"
queue.pollLast();                    // removes and returns "C"
System.out.println(queue);           // [B]

Each end operation updates only one or two node links, so it runs in constant time, regardless of how many elements the list holds.

Two families of methods

Many Deque operations come in two versions that differ in how they handle an empty list:

Use the throwing versions when an empty list indicates a bug, and the null-returning versions when emptiness is a normal condition, such as draining a work queue. Because null signals "empty," avoid storing null elements in a LinkedList used as a queue.

As a queue (FIFO) and a stack (LIFO)

LinkedList<String> fifo = new LinkedList<>();
fifo.offer("job1");      // adds at the end
fifo.offer("job2");
fifo.poll();             // "job1": first in, first out

LinkedList<String> lifo = new LinkedList<>();
lifo.push("page1");      // adds at the front
lifo.push("page2");
lifo.pop();              // "page2": last in, first out

offer, poll, and peek are the Queue methods; push, pop, and peek are the stack-style methods. Queues and stacks have their own lessons.

Performance Compared with ArrayList

Why get(i) is slow

To reach index i, a linked list follows next links one at a time, starting from whichever end is closer. Calling get(i) inside a loop therefore makes the whole loop quadratic:

LinkedList<Integer> nums = new LinkedList<>();
for (int i = 0; i < 100_000; i++) nums.add(i);

long sum = 0;
for (int i = 0; i < nums.size(); i++) {
    sum += nums.get(i);              // each get walks the list: very slow
}

long fast = 0;
for (int n : nums) {                 // iterator follows links once: fast
    fast += n;
}

Always iterate a LinkedList with a for-each loop or an iterator, never with an index.

The real-world verdict

Although LinkedList wins on paper for insertions in the middle, it is usually slower than ArrayList in practice. Reaching the middle of a linked list takes O(n) pointer hops, and ArrayList's O(n) shift is a single fast memory copy. Node objects are scattered across memory, which defeats the CPU cache, and each node adds roughly 24 or more bytes of overhead.

For most needs:

• Use ArrayList for general lists.
• Use ArrayDeque for queues and stacks: it supports the same Deque operations with constant-time ends, using a compact array.

LinkedList remains appropriate when you insert or remove many elements while iterating with a ListIterator, when you need a List and a Deque in one object, or when you need to store null elements in a deque (which ArrayDeque forbids).

Inserting While Iterating: ListIterator

A ListIterator can move in both directions and insert, replace, or remove elements at its current position. With a LinkedList, these modifications take constant time because only neighboring links change:

LinkedList<String> steps = new LinkedList<>(List.of("plan", "code", "deploy"));

ListIterator<String> it = steps.listIterator();
while (it.hasNext()) {
    if (it.next().equals("code")) {
        it.add("test");              // inserts right after "code"
    }
}
System.out.println(steps);           // [plan, code, test, deploy]

it.add inserts the new element immediately after the one just returned by next(), and the iterator stays valid. Modifying the list directly (with steps.add(...)) during iteration would throw ConcurrentModificationException.

Other ListIterator methods:

Iterating Backward

LinkedList<String> recent = new LinkedList<>(List.of("a.txt", "b.txt", "c.txt"));

Iterator<String> desc = recent.descendingIterator();
while (desc.hasNext()) {
    System.out.print(desc.next() + " ");     // c.txt b.txt a.txt
}

Since Java 21, LinkedList also implements SequencedCollection, which provides reversed(), a reverse-ordered view: for (String f : recent.reversed()) { ... }.

Practical Example: Browser History

A browser keeps a back history and a forward history. Visiting a new page pushes the current page onto the back history and clears the forward history; going back and forward moves pages between the two. Both histories are used only at their front, and the back history drops its oldest page when it exceeds a limit, so all operations are at the ends of the lists.

import java.util.LinkedList;

public class BrowserHistory {
    private final LinkedList<String> back = new LinkedList<>();
    private final LinkedList<String> forward = new LinkedList<>();
    private String current;
    private static final int LIMIT = 3;

    BrowserHistory(String home) { current = home; }

    void visit(String url) {
        back.addFirst(current);
        if (back.size() > LIMIT) back.removeLast();    // drop the oldest page
        forward.clear();
        current = url;
    }

    void goBack() {
        if (back.isEmpty()) return;
        forward.addFirst(current);
        current = back.removeFirst();
    }

    void goForward() {
        if (forward.isEmpty()) return;
        back.addFirst(current);
        current = forward.removeFirst();
    }

    @Override
    public String toString() { return "back=" + back + " current=" + current + " forward=" + forward; }

    public static void main(String[] args) {
        BrowserHistory h = new BrowserHistory("home");
        h.visit("courses");
        h.visit("java");
        h.visit("java/arrays");
        h.visit("java/lists");
        System.out.println(h);
        h.goBack();
        h.goBack();
        System.out.println(h);
        h.goForward();
        System.out.println(h);
        h.visit("docker");
        System.out.println(h);
    }
}

Output:

back=[java/arrays, java, courses] current=java/lists forward=[]
back=[courses] current=java forward=[java/arrays, java/lists]
back=[java, courses] current=java/arrays forward=[java/lists]
back=[java/arrays, java, courses] current=docker forward=[]

The most recent page is always at the front of each list. After four visits, the back history holds only three pages: "home" was removed from the end by removeLast() when the limit was exceeded. Going back twice moves two pages to the forward history; going forward moves one back. Visiting docker clears the forward history, just as a real browser does. Every operation touches only the first or last node, so each one runs in constant time no matter how long the histories grow. (ArrayDeque would work equally well here; LinkedList is used to show its end operations.)