Java LinkedList

An ArrayList keeps its elements side by side in one array. A Java LinkedList takes a completely different approach: every element lives in its own little box called a node, and each node holds links to its neighbors. In this lesson, you'll see how that chain works, use LinkedList as both a list and a double-ended queue, compare it with ArrayList, and meet ArrayDeque, the class most Java developers actually reach for when they need a stack or a queue.

What is a LinkedList in Java?

LinkedList is a class in java.util that stores elements in a doubly linked list. Each node holds three things: the element itself, a link to the previous node, and a link to the next node. The list remembers its first node (the head) and its last node (the tail).

Because nodes can live anywhere in memory, there's no fast way to jump to index 500. Java has to start at the head (or the tail, whichever is closer) and follow links one at a time. That's the key trade-off you'll see throughout this lesson.

Using LinkedList as a List

LinkedList implements the List interface, so every method you learned in Java ArrayList works: add, get, set, remove, size, contains. It also adds methods for working at the two ends: addFirst, addLast, getFirst, getLast, removeFirst and removeLast.

import java.util.LinkedList;

public class TrainCars {
    public static void main(String[] args) {
        LinkedList<String> train = new LinkedList<>();
        train.add("Coach A");
        train.add("Coach B");
        train.add("Dining car");
        System.out.println(train);

        train.addFirst("Engine");       // attach at the front
        train.addLast("Caboose");       // attach at the back
        train.add(3, "Coach C");        // List method: insert at index 3
        System.out.println(train);

        System.out.println("Front: " + train.getFirst());
        System.out.println("Back:  " + train.getLast());
        System.out.println("Index 2: " + train.get(2));

        train.removeLast();
        train.remove("Coach B");
        System.out.println(train + " (" + train.size() + " cars)");
    }
}

[Coach A, Coach B, Dining car]
[Engine, Coach A, Coach B, Coach C, Dining car, Caboose]
Front: Engine
Back:  Caboose
Index 2: Coach B
[Engine, Coach A, Coach C, Dining car] (4 cars)

Notice the variable is declared as LinkedList<String> here, not List<String>. That's because addFirst and friends belong to the Deque interface, which LinkedList also implements.

What is a Deque?

A Deque (pronounced "deck", short for double-ended queue) is a collection you can add to and remove from at both ends. LinkedList is one implementation. The Deque methods come in pairs: one version throws an exception when something goes wrong, and a gentler version returns a special value instead.

Here's a supermarket checkout line, where a priority customer jumps to the front and someone at the back gives up and leaves:

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

public class CheckoutLine {
    public static void main(String[] args) {
        Deque<String> line = new LinkedList<>();
        line.offerLast("Maya");
        line.offerLast("Jonas");
        line.offerLast("Priya");
        line.offerFirst("Mr. Ortiz");   // a customer with a priority pass
        System.out.println("Line: " + line);

        System.out.println("Next up: " + line.peekFirst());
        System.out.println("Served:  " + line.pollFirst());
        System.out.println("Served:  " + line.pollFirst());
        System.out.println("Gave up waiting: " + line.pollLast());
        System.out.println("Line: " + line);

        line.pollFirst();
        System.out.println("Empty line, pollFirst gives: " + line.pollFirst());
    }
}

Line: [Mr. Ortiz, Maya, Jonas, Priya]
Next up: Mr. Ortiz
Served:  Mr. Ortiz
Served:  Maya
Gave up waiting: Priya
Line: [Jonas]
Empty line, pollFirst gives: null

The final pollFirst() on an empty line returned null instead of crashing. removeFirst() would have thrown a NoSuchElementException. Use the poll/peek versions when "empty" is a normal situation you want to check for.

ArrayList vs LinkedList: which is faster?

Here's how the two compare. "Fast" means the time stays the same no matter how big the list is; "slow" means it grows with the size of the list.

In practice, ArrayList wins for almost every list. Modern computers love data packed side by side in memory, and most programs read far more than they insert at the front. LinkedList only shines when you constantly add or remove at the ends, and even there, ArrayDeque is usually faster.

ArrayDeque: the usual choice for stacks and queues

ArrayDeque is another Deque implementation. It uses a resizable array that wraps around in a circle, so adding and removing at both ends is fast and it uses less memory than LinkedList. Use it whenever you need a stack or a queue. (One rule: it doesn't accept null elements.)

A stack: last in, first out

A stack works like a pile of plates: the last thing you put on top is the first thing you take off (LIFO). Deque gives you the classic stack methods push (add to top), pop (remove from top) and peek (look at the top). A browser's Back button is a stack:

import java.util.ArrayDeque;
import java.util.Deque;

public class BrowserHistory {
    public static void main(String[] args) {
        Deque<String> history = new ArrayDeque<>();

        history.push("home.html");
        history.push("news.html");
        history.push("sports.html");
        history.push("scores.html");
        System.out.println("History (top first): " + history);
        System.out.println("Current page: " + history.peek());

        System.out.println("Back from " + history.pop());
        System.out.println("Back from " + history.pop());
        System.out.println("Current page: " + history.peek());
    }
}

History (top first): [scores.html, sports.html, news.html, home.html]
Current page: scores.html
Back from scores.html
Back from sports.html
Current page: news.html

A queue: first in, first out

A queue serves items in the order they arrived (FIFO), like people waiting for a bus. Declare it with the Queue interface and use offer to join the back and poll to leave from the front. An office printer handles jobs this way:

import java.util.ArrayDeque;
import java.util.Queue;

public class PrintQueue {
    public static void main(String[] args) {
        Queue<String> jobs = new ArrayDeque<>();
        jobs.offer("report.pdf");
        jobs.offer("photo.png");
        jobs.offer("invoice.docx");
        System.out.println("Waiting: " + jobs);

        while (!jobs.isEmpty()) {
            String job = jobs.poll();
            System.out.println("Printing " + job + "... " + jobs.size() + " left");
        }
    }
}

Waiting: [report.pdf, photo.png, invoice.docx]
Printing report.pdf... 2 left
Printing photo.png... 1 left
Printing invoice.docx... 0 left

The while (!jobs.isEmpty()) loop is the standard way to process a queue until nothing is left.

When should you use LinkedList?

• Need a normal list? Use ArrayList.
• Need a stack or queue? Use ArrayDeque.
• Need a queue that allows null, or a single object that's both a List and a Deque? That's where LinkedList fits.

It's still worth understanding LinkedList: linked nodes are a classic computer-science idea, they come up in interviews, and the same "node with links" pattern powers trees and graphs.

Common mistakes with LinkedList

1. Choosing LinkedList "because inserting is fast"

Inserting is fast only once you're at the right node. Reaching index i takes a walk, so add(i, x) in the middle is usually no faster than on an ArrayList.

2. Looping with get(i)

Every get(i) walks the chain again. Use a for-each loop or an Iterator.

3. Calling addFirst on a List variable

List<String> list = new LinkedList<>(); list.addFirst("x"); doesn't compile on Java 17 to 20 because List has no addFirst there (Java 21 added it). Declare the variable as Deque or LinkedList.

4. Using pop or remove on an empty deque

pop(), removeFirst() and getFirst() throw NoSuchElementException when empty. Check isEmpty() first, or use poll/peek, which return null.

5. Mixing up stack and queue ends

For a stack, stick to push/pop/peek. For a queue, stick to offer/poll/peek. Mixing push with poll works, but makes the code hard to follow.

Practice exercise

import java.util.ArrayDeque;
import java.util.Deque;

public class RadioRotation {
    public static void main(String[] args) {
        Deque<String> songs = new ArrayDeque<>();
        songs.offerLast("Song A");
        songs.offerLast("Song B");
        songs.offerLast("Song C");

        for (int round = 1; round <= 5; round++) {
            String playing = songs.pollFirst();
            System.out.println(round + ": now playing " + playing);
            songs.offerLast(playing);
        }
        System.out.println("Up next: " + songs.peekFirst());
    }
}

1: now playing Song A
2: now playing Song B
3: now playing Song C
4: now playing Song A
5: now playing Song B
Up next: Song C

What's next?

Lists find things by position. But what if you want to find a phone number by a person's name, or a price by a product code? Next, learn the collection built for lookups: Java HashMap.