LinkedList

Use LinkedList as both a List and a Deque for efficient insertions at both ends.

Overview

LinkedList is a doubly-linked list implementation that implements both the List and Deque interfaces. Each element (node) holds a reference to the previous and next node, so insertions and removals at the head or tail are O(1), while random access by index is O(n). LinkedList is a good choice when you frequently insert or remove at the front or both ends of a list, or when you need a stack or queue. For most other uses, ArrayList is faster due to better cache locality. Because LinkedList implements Deque, it has methods like addFirst, addLast, pollFirst, pollLast that make it easy to use as a queue or stack.

Key Points

•LinkedList implements both List and Deque
•O(1) insertion and removal at head and tail
•O(n) random access by index (no direct memory addressing)
•addFirst/addLast, peekFirst/peekLast, pollFirst/pollLast for queue or deque use
•push/pop for stack-style usage (front of the list)
•offer/poll for queue-style usage (add at tail, remove from head)
•Use ArrayList when most operations are random access or iteration
•Use LinkedList when most operations are at the head or tail

Examples

LinkedList as a List

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

public class Main {
    public static void main(String[] args) {
        List<String> tasks = new LinkedList<>();
        tasks.add("Write code");
        tasks.add("Write tests");
        tasks.add("Deploy");

        // All standard List operations work
        System.out.println(tasks.get(1)); // Write tests
        tasks.remove(0);
        System.out.println(tasks);        // [Write tests, Deploy]
    }
}

LinkedList supports all List operations. The difference is performance: get(n) traverses the chain, so avoid heavy random access.

LinkedList as a Queue (FIFO)

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

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

        // Enqueue (add to tail)
        queue.offer("Task A");
        queue.offer("Task B");
        queue.offer("Task C");

        System.out.println("Peek: " + queue.peek()); // Task A (no remove)

        // Dequeue (remove from head)
        while (!queue.isEmpty()) {
            System.out.println("Processing: " + queue.poll());
        }
    }
}

offer returns false if the queue is full (not applicable here). poll returns null on empty; remove throws NoSuchElementException. Use poll for safety.

LinkedList as a Stack (LIFO)

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

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

        // Push to front
        stack.push("First");
        stack.push("Second");
        stack.push("Third");

        System.out.println("Peek: " + stack.peek()); // Third

        // Pop from front (LIFO)
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
        // Prints: Third, Second, First
    }
}

push adds to the front; pop removes from the front. This gives LIFO (last-in, first-out) behaviour. Deque<E> is the preferred interface for stacks in modern Java.

Common Mistakes

Using LinkedList for random access (get(i) in a loop) which is O(n) per call and much slower than ArrayList
Mixing up poll (returns null when empty) and remove (throws exception when empty). Use poll for safe queue drain loops
Declaring as LinkedList<E> instead of List<E>, Queue<E>, or Deque<E>. The interface tells readers how you intend to use it

Note

In practice, ArrayDeque is faster than LinkedList for stack and queue operations because it avoids the overhead of allocating a node object per element. Use ArrayDeque unless you also need the List interface.

LinkedList

Overview

Key Points

Examples

Common Mistakes

Note

Exercises

Knowledge Check

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