Skip to content
Java collections 6 min read

LinkedList

LinkedList is a versatile data structure that implements both the List and Deque interfaces. Unlike ArrayList, it stores elements in a chain of nodes rather than a contiguous block of memory — which makes it excellent for frequent insertions and deletions, especially at the ends of the list.

What is LinkedList?

LinkedList<E> lives in the java.util package. Each element is wrapped in a node that holds a reference to both the previous and the next node, forming a doubly linked list.

import java.util.LinkedList;

public class BasicLinkedList {
    public static void main(String[] args) {
        LinkedList<String> cities = new LinkedList<>();
        cities.add("London");
        cities.add("Paris");
        cities.add("Tokyo");
        System.out.println(cities);
    }
}

Output:

[London, Paris, Tokyo]

Creating a LinkedList

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

public class CreatingLinkedList {
    public static void main(String[] args) {
        // Empty list
        LinkedList<Integer> nums = new LinkedList<>();

        // From another Collection
        List<String> source = List.of("A", "B", "C");
        LinkedList<String> copy = new LinkedList<>(source);

        System.out.println(nums);   // []
        System.out.println(copy);   // [A, B, C]
    }
}

Output:

[]
[A, B, C]

Common Operations

Adding Elements

LinkedList gives you several ways to add elements — at the end, at the beginning, or at any index.

import java.util.LinkedList;

public class AddingElements {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        list.add("Middle");          // adds to tail
        list.addFirst("First");      // adds to head
        list.addLast("Last");        // adds to tail
        list.add(1, "After First");  // adds at index 1

        System.out.println(list);
    }
}

Output:

[First, After First, Middle, Last]

Accessing Elements

import java.util.LinkedList;

public class AccessingElements {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>(List.of("A", "B", "C", "D"));

        System.out.println(list.get(2));    // index-based — O(n)
        System.out.println(list.getFirst()); // O(1)
        System.out.println(list.getLast());  // O(1)
        System.out.println(list.peek());     // same as getFirst, null if empty
        System.out.println(list.peekLast()); // same as getLast, null if empty
    }
}

Output:

C
A
D
A
D

Note: get(index) traverses the list from the nearest end, so it is O(n). If you need frequent random access by index, prefer ArrayList.

Removing Elements

import java.util.LinkedList;

public class RemovingElements {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("One");
        list.add("Two");
        list.add("Three");
        list.add("Four");

        list.removeFirst();      // removes head
        list.removeLast();       // removes tail
        list.remove("Three");    // removes by value
        list.remove(0);          // removes by index (now just "Two" left)

        System.out.println(list);
    }
}

Output:

[]

Tip: poll() and pollFirst() are safe alternatives to removeFirst() — they return null instead of throwing NoSuchElementException when the list is empty.

Using LinkedList as a Queue

Because LinkedList implements java.util.Queue, you can use it as a FIFO queue with the standard queue methods.

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        queue.offer("First in");   // enqueue
        queue.offer("Second in");
        queue.offer("Third in");

        System.out.println("Peek: " + queue.peek());    // view head
        System.out.println("Poll: " + queue.poll());    // dequeue
        System.out.println("Remaining: " + queue);
    }
}

Output:

Peek: First in
Poll: First in
Remaining: [Second in, Third in]

Using LinkedList as a Stack / Deque

LinkedList also implements java.util.Deque, so you can use it as a double-ended queue or a stack.

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

public class DequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();

        // Stack behaviour (LIFO)
        deque.push("Bottom");
        deque.push("Middle");
        deque.push("Top");

        System.out.println("Pop: " + deque.pop());    // Top
        System.out.println("Pop: " + deque.pop());    // Middle
        System.out.println("Remaining: " + deque);
    }
}

Output:

Pop: Top
Pop: Middle
Remaining: [Bottom]

Tip: For a pure stack, Deque<T> stack = new ArrayDeque<>() is generally faster than LinkedList because there is no node allocation overhead.

Iterating a LinkedList

You can iterate using a for-each loop, an Iterator, or listIterator().

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

public class IteratingLinkedList {
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
        for (int i = 1; i <= 5; i++) numbers.add(i * 10);

        // for-each
        for (int n : numbers) {
            System.out.print(n + " ");
        }
        System.out.println();

        // Iterator (safe removal during iteration)
        Iterator<Integer> it = numbers.iterator();
        while (it.hasNext()) {
            if (it.next() == 30) it.remove();
        }
        System.out.println(numbers);
    }
}

Output:

10 20 30 40 50 
[10, 20, 40, 50]

Key Methods at a Glance

MethodDescriptionTime
add(e) / addLast(e)Append to tailO(1)
addFirst(e)Prepend to headO(1)
add(i, e)Insert at indexO(n)
get(i)Retrieve by indexO(n)
getFirst() / getLast()Head / tail elementO(1)
remove(i)Remove at indexO(n)
removeFirst() / removeLast()Remove head / tailO(1)
poll() / pollLast()Remove head / tail (null-safe)O(1)
peek() / peekLast()View head / tail (null-safe)O(1)
push(e) / pop()Stack operations (head)O(1)
size()Number of elementsO(1)
contains(o)Membership checkO(n)
clear()Remove all elementsO(n)

ArrayList vs LinkedList

Choosing the right list implementation matters for performance. Here is a quick comparison:

FeatureArrayListLinkedList
Internal structureDynamic arrayDoubly linked nodes
Random access get(i)O(1)O(n)
Insert / delete at head or tailO(n) (shifting)O(1)
Insert / delete in middleO(n)O(n) find + O(1) change
Memory per elementLow (just the value)Higher (value + 2 pointers)
Implements DequeNoYes
Cache friendlinessHigh (contiguous memory)Low (nodes scattered in heap)

Use LinkedList when you have many additions or removals at the head or tail of the list. Prefer ArrayList for general-purpose use where index-based access is common.

Warning: Despite O(1) middle insertion once you have an iterator position, LinkedList is often slower than ArrayList in practice for most workloads because of poor CPU cache utilisation. Always benchmark before assuming LinkedList is the better choice.

Under the Hood

Each element in a LinkedList is stored in an inner Node<E> class (in java.util.LinkedList’s source):

// Simplified version of the private static inner class
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

The LinkedList object itself holds references to only two nodes — first (head) and last (tail) — plus an integer size. Accessing get(i) checks whether i is in the first or second half of the list, then traverses from the closer end. This clever optimisation cuts the average traversal in half, but it is still O(n).

When you add or remove an element at either end, only those two pointer fields are updated — no data is shifted. This is why head/tail operations are truly O(1).

Because nodes are individual heap objects, each element carries the overhead of two object references (16 bytes on a 64-bit JVM with compressed OOPs) plus the object header for the node itself. For large lists of small primitives, this can use significantly more memory than an ArrayList.

Note: LinkedList is not thread-safe. For concurrent use, wrap it with Collections.synchronizedList() or use a ConcurrentLinkedDeque from java.util.concurrent for lock-free queue operations. See Concurrent Collections for details.

Last updated June 13, 2026
Was this helpful?