Home/Learn/Java A–Z/LinkedList

LinkedList

Intermediate
Collections Framework

Java's doubly-linked list that implements both List and Deque — ideal for frequent insertions at both ends, but rarely better than ArrayList for random access.

Overview

Java's LinkedList is a doubly-linked list — each node holds a reference to both the previous and next node. It implements both List and Deque, making it usable as a list, stack, queue, and double-ended queue. The key advantage over ArrayList is O(1) insertion and removal at the head and tail without shifting. The disadvantage is O(n) random access (must walk from head or tail) and higher memory overhead (two references per node). For most use cases, ArrayDeque outperforms LinkedList as a queue/stack.

LinkedList as List & Deque

As a List, LinkedList supports all index-based operations but they are O(n) internally. It traverses from the closer end (head if index < size/2, tail otherwise) to reach the target node.

As a Deque (double-ended queue), LinkedList provides O(1) addFirst/addLast, removeFirst/removeLast, peekFirst/peekLast. These are the operations where LinkedList shines — building a queue or stack where all work happens at the ends.

LinkedListDemo.java
import java.util.LinkedList;
import java.util.Deque;
import java.util.Queue;

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

        // ── As a List ─────────────────────────────────────────────────
        list.add("banana");       // O(1) — adds at tail
        list.add("cherry");
        list.add(0, "apple");    // O(n) — must traverse to index 0
        System.out.println(list); // [apple, banana, cherry]

        System.out.println(list.get(1));    // banana — O(n) traversal
        System.out.println(list.size());    // 3

        // ── As a Deque (double-ended queue) ──────────────────────────
        LinkedList<Integer> deque = new LinkedList<>();
        deque.addFirst(2);   // [2]
        deque.addFirst(1);   // [1, 2]
        deque.addLast(3);    // [1, 2, 3]
        deque.addLast(4);    // [1, 2, 3, 4]

        System.out.println(deque.peekFirst()); // 1 — does not remove
        System.out.println(deque.peekLast());  // 4 — does not remove
        System.out.println(deque.removeFirst()); // 1
        System.out.println(deque.removeLast());  // 4
        System.out.println(deque); // [2, 3]

        // ── As a Queue (FIFO) ─────────────────────────────────────────
        Queue<String> queue = new LinkedList<>();
        queue.offer("first");
        queue.offer("second");
        queue.offer("third");
        System.out.println(queue.poll());  // first  (removes head)
        System.out.println(queue.peek());  // second (views head, no remove)

        // ── As a Stack (LIFO) ─────────────────────────────────────────
        Deque<String> stack = new LinkedList<>();
        stack.push("a"); stack.push("b"); stack.push("c");
        System.out.println(stack.pop());  // c (LIFO)
    }
}

LinkedList vs ArrayList vs ArrayDeque

When to pick which:

ArrayList — best default for lists; O(1) random access; cache-friendly; use unless you have specific reason not to LinkedList — only preferable when you need O(1) insertions/deletions at arbitrary positions AND you already have a reference to the node (not common in Java since you work with indices/iterators) ArrayDeque — best Stack and Queue; faster than LinkedList for head/tail ops because no node allocation; more cache-friendly

In practice: 95% of the time use ArrayList. For queues and stacks, use ArrayDeque.

CollectionComparison.java
import java.util.*;

public class CollectionComparison {

    // Benchmark-style comparison (conceptual)
    public static void main(String[] args) {
        int N = 100_000;

        // ArrayList — fast end-appending and random access
        List<Integer> arrayList = new ArrayList<>(N);
        for (int i = 0; i < N; i++) arrayList.add(i);     // O(1) amortised

        System.out.println(arrayList.get(N / 2));          // O(1) random access

        // LinkedList — slower random access but O(1) ends
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < N; i++) linkedList.addLast(i); // O(1) each
        System.out.println(linkedList.get(N / 2));          // O(n) — traverses

        // ArrayDeque — fastest queue/stack, no null allowed
        Deque<Integer> arrayDeque = new ArrayDeque<>(N);
        for (int i = 0; i < N; i++) arrayDeque.offerLast(i); // O(1) amortised
        System.out.println(arrayDeque.peekFirst());           // O(1)

        // Memory: LinkedList uses ~40 bytes per node (object header + 2 refs + data ref)
        // ArrayList uses ~4 bytes per reference + object overhead
        // ArrayDeque uses ~4 bytes per reference in a circular array

        // Summary printout
        System.out.println("ArrayList random access: O(1)");
        System.out.println("LinkedList random access: O(n)");
        System.out.println("ArrayDeque head/tail: O(1)");
        System.out.println("LinkedList head/tail: O(1) — but higher GC pressure");
    }
}

Iterator & ListIterator

LinkedList's ListIterator is the only way to traverse and mutate the list in O(n) total rather than O(n²). Each next()/previous() moves by one node. Calling listIterator.add() or listIterator.remove() during traversal is safe (no ConcurrentModificationException from the iterator itself) and O(1) per operation because the iterator holds a reference to the current node.

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

public class LinkedListIterator {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>(
            java.util.List.of(1, 2, 3, 4, 5));

        // ListIterator — bidirectional, supports add/remove/set during iteration
        ListIterator<Integer> it = list.listIterator();

        while (it.hasNext()) {
            int val = it.next();
            if (val % 2 == 0) {
                it.remove();          // O(1) — unlinks the node
            } else {
                it.set(val * 10);     // O(1) — updates in place
            }
        }
        System.out.println(list); // [10, 30, 50]

        // Reverse traversal
        while (it.hasPrevious()) {
            System.out.print(it.previous() + " "); // 50 30 10
        }
        System.out.println();

        // ListIterator.add() — inserts before the next element
        ListIterator<Integer> it2 = list.listIterator();
        it2.next();          // move past 10
        it2.add(15);         // insert 15 after 10
        System.out.println(list); // [10, 15, 30, 50]
    }
}

Interactive Visualization

«I»Collection
«I»List
«I»Set
«I»Queue
Collection is the root interface. It branches into List, Set, and Queue.
1 / 5

Key Points to Remember

  • LinkedList implements both List and Deque — it is a doubly-linked list
  • O(1) addFirst/addLast/removeFirst/removeLast; O(n) get(index) — must traverse from nearest end
  • Higher memory overhead than ArrayList: ~40 bytes per node vs ~4 bytes per reference slot
  • Prefer ArrayDeque over LinkedList for stacks and queues — faster and more cache-friendly
  • ListIterator allows O(1) add/remove/set during traversal without ConcurrentModificationException
  • LinkedList is fail-fast just like ArrayList — do not structurally modify from outside while iterating

Practice LinkedList in the Playground

Run and modify code directly in your browser - no setup needed.

Interview Questions

Sign in to ask Aria
1

What interfaces does LinkedList implement?

EasyTCS
2

When would you choose LinkedList over ArrayList?

MediumAmazon
3

What is the time complexity of LinkedList.get(index)?

EasyGoogle
4

What is the difference between ArrayDeque and LinkedList as a Queue?

MediumMicrosoft
5

How does LinkedList achieve O(1) insertion at both ends?

MediumOracle

Ask Aria about LinkedList

Your personal AI tutor — ask anything about this concept

Previous
ArrayList
Next
HashMap