Java LinkedList: operations, internals and failure cases

What the nodes buy you

There is no backing array to shift when an endpoint changes. The list keeps a head and a tail. Adding a node at either end changes a small set of references; reading an arbitrary position requires a walk from one of those ends.

Indexing costs time. The structure has no equivalent of an array address computed from an index. For a list with n elements, get(i) can traverse roughly half the list even though its return type looks identical to ArrayList.get(i).

Build a task queue

import java.util.LinkedList;

public class TaskQueueDemo {
    public static void main(String[] args) {
        LinkedList<String> pendingTasks = new LinkedList<>();
        pendingTasks.addLast("Validate invoice");
        pendingTasks.addLast("Send receipt");
        pendingTasks.addFirst("Check account");
        System.out.println(pendingTasks);
        System.out.println(pendingTasks.pollFirst());
        System.out.println(pendingTasks.peekFirst());
        System.out.println(pendingTasks.size());
    }
}

Save as TaskQueueDemo.java. Compile with javac TaskQueueDemo.java and run java TaskQueueDemo. The program prints the following values.

[Check account, Validate invoice, Send receipt]
Check account
Validate invoice
2

addFirst inserts urgent work before the existing head. pollFirst removes that head; peekFirst reads the replacement without removing it. The sample is single-threaded and in-memory. It does not guarantee job durability or exactly-once processing.

List, Queue, or Deque?

The reference type decides which methods the compiler exposes. A List<String> reference supports positional operations. Queue<String> exposes offer, poll, and peek. Deque<String> adds operations on both ends. Choose the contract the caller needs rather than exposing every method of the implementation.

Use Queue<String> pendingTasks = new LinkedList<>(); when the caller should treat the structure as FIFO. Use Deque when both ends matter. A List reference does not expose addFirst in Java 8; later Java releases added sequenced collection methods, so check the target release before relying on them.

Methods worth knowing

addFirst(value) / addLast(value): insert an element at the selected end.
offer(value): append an element using the Queue contract. LinkedList is not a capacity-bounded queue.
peekFirst() / peekLast(): read an endpoint, returning null for an empty list.
pollFirst() / pollLast(): remove an endpoint, returning null for an empty list.
getFirst() / getLast(): read an endpoint but throw NoSuchElementException when empty.
removeFirst() / removeLast(): remove an endpoint but throw when empty.
get(index) / set(index, value): walk to a valid position; set replaces its value.
add(index, value): insert at a position from zero through size(). Locating that position can dominate the operation.
remove(index): remove by position and return the removed element.
remove(Object): search for and remove the first equal value, returning a boolean.
contains(value): search by equality. It does not provide constant-time lookup.
listIterator(): obtain a cursor that can move in either direction and edit through its own methods.
size(): read the stored element count without traversing the nodes.

Performance is about locating the node

Endpoint insertion and removal perform O(1) link work. Searching by value and accessing an arbitrary index take O(n) in the worst case. Traversing every element once with an iterator takes O(n). The list uses O(n) storage, including one node object per element and its links; exact byte counts depend on JVM settings and object layout.

Insertion through a ListIterator already positioned at the target has O(1) link work. Getting that cursor to an arbitrary index can take O(n). These are separate costs. “LinkedList inserts in constant time” is incomplete when the caller first searches for a position.

Avoid a loop that calls get(index) for every index. It repeats traversal and can do O(n²) work. An enhanced for loop or iterator visits the chain once. Allocation and cache behavior still matter; Big O alone does not identify the faster collection for a real workload.

Insert with a positioned cursor

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

public class ListEditDemo {
    public static void main(String[] args) {
        LinkedList<String> stages = new LinkedList<>(
            Arrays.asList("Received", "Packed", "Dispatched"));
        ListIterator<String> cursor = stages.listIterator();
        while (cursor.hasNext()) {
            if ("Packed".equals(cursor.next())) {
                cursor.add("Quality checked");
                break;
            }
        }
        System.out.println(stages);
    }
}

[Received, Packed, Quality checked, Dispatched]

The cursor is after Packed when add runs. It inserts at that cursor position and leaves Dispatched after the new element. Finding Packed takes O(n); adding after it takes O(1) link work. Iterator navigation remains valid because the edit goes through that iterator.

Removal overloads can surprise you

import java.util.Arrays;
import java.util.LinkedList;

public class RemovalTrapDemo {
    public static void main(String[] args) {
        LinkedList<Integer> retryCodes = new LinkedList<>(
            Arrays.asList(7, 11, 7));
        retryCodes.remove(1);
        System.out.println(retryCodes);
        retryCodes.remove(Integer.valueOf(7));
        System.out.println(retryCodes);
    }
}

[7, 7]
[7]

The literal 1 selects remove(int), which removes the value at index one: 11. Integer.valueOf(7) selects remove(Object), which removes the first matching 7. Autoboxing does not make those two calls mean the same thing.

Edit during iteration through the iterator

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;

public class IteratorCleanupDemo {
    public static void main(String[] args) {
        LinkedList<String> jobs = new LinkedList<>(
            Arrays.asList("done:1", "pending:2", "done:3"));
        Iterator<String> cursor = jobs.iterator();
        while (cursor.hasNext()) {
            if (cursor.next().startsWith("done:")) {
                cursor.remove();
            }
        }
        System.out.println(jobs);
    }
}

[pending:2]

Iterator.remove removes the element returned by the last next call. Calling it before next, or twice for the same element, is invalid. Calling jobs.remove from inside an enhanced for loop structurally edits the list outside its iterator and can trigger ConcurrentModificationException. Fail-fast behavior is a bug signal, not a concurrency guarantee.

Choose against ArrayList and ArrayDeque

Use ArrayList as a starting point for an ordered sequence that needs indexed reads. It uses a backing array of references and avoids allocating a linked node per element. Appending is amortized O(1), while inserting into the middle shifts later references.

For a queue or stack that does not need null values, evaluate ArrayDeque. It stores elements in a resizable array and typically avoids LinkedList’s node allocation costs. Its endpoint operations are generally amortized O(1). Do not choose LinkedList merely because the requirement says queue.

Choose LinkedList when its combined List/Deque behavior or cursor-based edits match a measured need. Benchmark realistic element counts, access patterns, allocation rates, and GC behavior. An isolated timing of one insertion does not represent a service workload.

Edge Cases

LinkedList permits null. That makes a null result from poll or peek ambiguous: it can mean an empty list or a stored null element. A queue of application jobs should usually reject null at its boundary.

Duplicates are permitted. remove(Object) removes only the first match. An empty list has no index zero, and get(size()) is out of bounds. add(size(), value) is valid because it inserts after the last current element.

The implementation is not synchronized. Protect an entire multi-step operation when several threads share it; individually coordinated calls do not automatically make check-then-remove atomic. A concurrent queue may fit the requirement better.

Connected lessons

Continue with Java ArrayList and indexed access, Java ArrayDeque for queues and stacks, Java LinkedList exercises with checked solutions.

Common Mistakes

Do not combine “not empty” and removeFirst as separate unprotected actions across threads. Do not expect a shallow list copy to copy mutable task objects. Keep indexed loops out of long linked lists, and decide whether removal means a position or a value before choosing the overload.