Java LinkedList

A LinkedList is a doubly linked list implementation of Java’s List and Deque interfaces, found in the java.util package. Unlike ArrayList, which stores elements in one contiguous array, LinkedList stores each element inside its own small object called a node, and each node keeps references to its neighbors. This makes LinkedList excellent at inserting and removing elements at the beginning, end, or middle of the list once you already have a position, but slower at random access by index. Understanding when to reach for it, and when not to, is a core Java Collections skill.

Overview / How It Works

LinkedList implements both the List interface (ordered, indexable, duplicates allowed) and the Deque interface (double-ended queue, so it can act as a stack, a queue, or a deque). Internally, the JVM represents the list as a chain of private Node objects. Each node stores three things: the actual element (item), a reference to the next node, and a reference to the prev node. The list itself only keeps two references at all times: first (the head) and last (the tail).

Because every node is a separate heap-allocated object connected purely by references, inserting or removing an element only requires re-pointing a handful of next/prev references — no shifting of other elements is needed, unlike an array-backed list. That is why addFirst, addLast, removeFirst, and removeLast all run in constant time, O(1), regardless of how many elements the list holds.

The tradeoff is random access. There is no array to jump into with an offset calculation, so get(index) and set(index, value) must walk the chain of nodes one link at a time starting from whichever end is closer (the JVM checks if index is in the first half or second half of the list and starts traversal from first or last accordingly). That makes indexed access O(n) in the worst case, compared to O(1) for ArrayList. Each node is also its own object on the heap, which means more memory overhead (three references per element versus a flat array slot) and worse CPU cache locality than a contiguous array.

Syntax

Declaring and creating a LinkedList looks like this:

LinkedList<Type> name = new LinkedList<>();          // empty list
LinkedList<Type> name = new LinkedList<>(existingCollection); // copy of another collection

Part	Meaning
Type	The element type, e.g. String, Integer. Must be a reference type, not a primitive.
new LinkedList<>()	Creates an empty list. The diamond <> lets the compiler infer the type from the left side.
existingCollection	Optional: any Collection whose elements are copied into the new list, in iteration order.

Because it implements both List and Deque, a LinkedList exposes a large method set. The most commonly used methods are:

Method	Effect
add(e) / addLast(e)	Appends e to the end.
addFirst(e)	Inserts e at the front.
add(index, e)	Inserts e at position index, shifting the traversal (still O(n) to reach the spot).
get(index), getFirst(), getLast()	Reads an element without removing it.
remove(index), remove(Object)	Removes by position or by matching value (first match).
removeFirst(), removeLast()	Removes and returns the head or tail element.
peek(), peekFirst(), peekLast()	Returns the head/tail without removing it; returns null if empty.
poll(), pollFirst(), pollLast()	Removes and returns the head/tail; returns null if empty (no exception).
push(e), pop()	Stack operations: push adds to the front, pop removes from the front.
offer(e)	Queue-style add to the end; returns true/false instead of throwing.
size(), isEmpty(), contains(e), indexOf(e)	Standard list queries, all inherited from List.

Examples

Example 1: LinkedList as a List

The most common use is as a general-purpose ordered list, mixing indexed operations with head/tail helpers:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> playlist = new LinkedList<>();
        playlist.add("Song A");
        playlist.add("Song B");
        playlist.addFirst("Intro");
        playlist.addLast("Outro");
        System.out.println(playlist);
        System.out.println("First: " + playlist.getFirst());
        System.out.println("Last: " + playlist.getLast());
        playlist.remove("Song B");
        System.out.println(playlist);
    }
}

Output:

[Intro, Song A, Song B, Outro]
First: Intro
Last: Outro
[Intro, Song A, Outro]

addFirst and addLast place elements at the ends in O(1) time, and remove(Object) scans the list to find and unlink the first node whose element equals "Song B".

Example 2: LinkedList as a Deque (stack and queue)

Because LinkedList implements Deque, the same object can behave like a stack (LIFO) or a queue (FIFO) depending on which methods you call:

import java.util.LinkedList;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> stack = new LinkedList<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("Stack: " + stack);
        System.out.println("Pop: " + stack.pop());
        System.out.println("Stack after pop: " + stack);

        Deque<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println("Queue: " + queue);
        System.out.println("Poll: " + queue.poll());
        System.out.println("Queue after poll: " + queue);
    }
}

Output:

Stack: [3, 2, 1]
Pop: 3
Stack after pop: [2, 1]
Queue: [1, 2, 3]
Poll: 1
Queue after poll: [2, 3]

push inserts at the front (so the most recently pushed value comes out first), while offer/poll add to the end and remove from the front, giving first-in-first-out order. Declaring the variables as Deque rather than LinkedList is good practice: it documents intent and lets you swap in ArrayDeque later without changing calling code.

Example 3: Safe traversal and insertion with ListIterator

A realistic task-list example that removes completed items and inserts a new one, using a ListIterator so the modifications are safe while iterating:

import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> tasks = new LinkedList<>();
        tasks.add("Write report");
        tasks.add("DONE:Buy groceries");
        tasks.add("Clean house");
        tasks.add("DONE:Pay bills");
        tasks.add("Read book");

        ListIterator<String> it = tasks.listIterator();
        while (it.hasNext()) {
            String task = it.next();
            if (task.startsWith("DONE:")) {
                it.remove();
            }
        }
        System.out.println("Remaining tasks: " + tasks);

        ListIterator<String> front = tasks.listIterator();
        front.add("URGENT: Call client");
        System.out.println("After urgent insert: " + tasks);
    }
}

Output:

Remaining tasks: [Write report, Clean house, Read book]
After urgent insert: [URGENT: Call client, Write report, Clean house, Read book]

ListIterator.remove() unlinks the node the iterator just visited without invalidating the iterator’s position, and ListIterator.add() inserts a new node immediately before the cursor. Since front starts before index 0, the new task lands at the very beginning — both operations run in constant time because the iterator already holds a reference to the neighboring nodes.

Under the Hood

When you call add(e), the JVM allocates a new Node object on the heap holding e, sets its prev reference to the current last node, sets the old last node’s next reference to the new node, and updates the list’s last field to point to the new node. No other node moves. Removing a node works in reverse: the neighbors’ next/prev references are pointed at each other, skipping over the removed node, and the JVM’s garbage collector reclaims it once nothing references it.

Indexed access via get(index) calls an internal node(index) helper that compares index to size >> 1: if the index is in the first half, it walks forward from first; if it’s in the second half, it walks backward from last. This halves the average number of hops but does not change the fact that access is linear time overall, which is the key architectural difference from ArrayList‘s constant-time array indexing.

Common Mistakes

Mistake 1: Looping with get(i) instead of an iterator

Calling get(i) inside a for-loop forces a full traversal from an end on every single call. Over the whole loop that becomes O(n²) instead of O(n):

LinkedList<Integer> numbers = new LinkedList<>();
for (int i = 1; i <= 5000; i++) {
    numbers.add(i);
}
long sum = 0;
for (int i = 0; i < numbers.size(); i++) {
    sum += numbers.get(i);
}
System.out.println(sum);

Output:

12502500

The result is correct, but for large lists this pattern becomes noticeably slow because each get(i) re-walks part of the chain. Use the enhanced for-loop or an explicit Iterator, which advances one node at a time without restarting from an end:

LinkedList<Integer> numbers = new LinkedList<>();
for (int i = 1; i <= 5000; i++) {
    numbers.add(i);
}
long sum = 0;
for (int num : numbers) {
    sum += num;
}
System.out.println(sum);

Output:

12502500

Mistake 2: Modifying a list with a for-each loop

Removing an element directly from the collection while a for-each loop (or its hidden Iterator) is in progress throws a ConcurrentModificationException, because the iterator detects that the list changed underneath it:

LinkedList<String> items = new LinkedList<>();
items.add("apple");
items.add("banana");
items.add("cherry");
for (String item : items) {
    if (item.equals("banana")) {
        items.remove(item);
    }
}
System.out.println(items);

Output:

Exception in thread "main" java.util.ConcurrentModificationException

Fix it by removing through the iterator itself (as shown in Example 3) or with removeIf, which handles the traversal safely internally:

LinkedList<String> items = new LinkedList<>();
items.add("apple");
items.add("banana");
items.add("cherry");
items.removeIf(item -> item.equals("banana"));
System.out.println(items);

Output:

[apple, cherry]

Best Practices

• Default to ArrayList unless you specifically need frequent insertions/removals at both ends or genuine Deque behavior — in practice ArrayList outperforms LinkedList for most workloads due to cache locality, even for some middle insertions.
• If you only need stack or queue behavior, prefer ArrayDeque over LinkedList; it is generally faster and has lower memory overhead, and it disallows null elements, catching bugs earlier.
• Declare variables using the interface type (List, Deque, or Queue) rather than LinkedList, so the implementation can be swapped later without touching calling code.
• Never iterate a LinkedList with an indexed for-loop; use the enhanced for-loop, an Iterator, or a ListIterator.
• Use poll()/peek() variants over remove()/element() when the collection might be empty, since the former return null instead of throwing.
• When removing while iterating, use Iterator.remove() or Collection.removeIf(), never mutate the list directly inside a for-each loop.

Practice Exercises

• Build a simple browser history using a LinkedList as a Deque<String>: implement visit(url) (push a new page), back() (pop the current page and show the previous one), and print the deque after a sequence of visits and back navigations.
• Write a method that takes a LinkedList<Integer> and reverses it in place using a ListIterator, without creating a new list. Print the list before and after.
• Write two versions of a method that inserts 20,000 elements at index 0: one using ArrayList and one using LinkedList. Time each with System.nanoTime() and print which one is faster, to see the O(1) front-insertion advantage in practice.

Summary

• LinkedList is a doubly linked list implementing both List and Deque, made of Node objects each holding an item plus next/prev references.
• addFirst/addLast/removeFirst/removeLast run in O(1) because only neighboring references change.
• Indexed access (get/set) is O(n) because the JVM must walk node-by-node from whichever end is closer.
• It doubles as a stack (push/pop) or queue (offer/poll) via the Deque interface.
• Avoid indexed loops on a LinkedList; use iterators, and prefer ArrayList or ArrayDeque unless you specifically need cheap end operations.
• Never mutate a list directly inside a for-each loop — use Iterator.remove() or removeIf to avoid ConcurrentModificationException.