Java LinkedList

A LinkedList is another kind of list. From the outside it works like the ArrayList: both implement the List interface, so add, get, remove, size and the for-each loop all work the same. The difference is inside. An ArrayList keeps its items in one array; a LinkedList keeps each item in its own small object (a node) that points to the next and the previous node.

Same methods as ArrayList

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> songs = new LinkedList<>();
        songs.add("Song B");
        songs.add("Song C");
        songs.addFirst("Song A");
        songs.addLast("Song D");
        System.out.println(songs);
        System.out.println(songs.getFirst() + " ... " + songs.getLast());
        songs.removeFirst();
        System.out.println(songs);
        System.out.println(songs.size());
    }
}

[Song A, Song B, Song C, Song D]
Song A ... Song D
[Song B, Song C, Song D]
3

addFirst, addLast, getFirst, getLast, removeFirst and removeLast work at the two ends of the list. These are fast for a linked list, because only the nodes at the ends change.

A queue: first in, first out

A queue works like a line at a ticket counter: people join at the back and are served from the front. LinkedList implements the Queue interface with offer (join), peek (look at the front) and poll (take the front item):

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

public class Main {
    public static void main(String[] args) {
        Queue<String> line = new LinkedList<>();
        line.offer("Asha");
        line.offer("Bilal");
        line.offer("Chen");
        System.out.println("Next: " + line.peek());
        while (!line.isEmpty()) {
            System.out.println("Serving " + line.poll());
        }
        System.out.println(line.poll());
    }
}

Next: Asha
Serving Asha
Serving Bilal
Serving Chen
null

On an empty queue, poll returns null instead of throwing an exception.

A stack: last in, first out

A stack works like a pile of plates: you take the one you put on last. push puts an item on top and pop takes the top one:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> history = new LinkedList<>();
        history.push("home");
        history.push("products");
        history.push("cart");
        System.out.println("Now on: " + history.peek());
        history.pop();
        System.out.println("Back to: " + history.peek());
        System.out.println(history);
    }
}

Now on: cart
Back to: products
[products, home]

This is how the Back button of a browser can work. (For stacks and queues, Java also has ArrayDeque, which is often a little faster.)

Choosing between ArrayList and LinkedList

In practice, ArrayList is the right default for most lists. Choose LinkedList when you mostly work at the two ends, such as a queue. Because both are Lists, switching later only changes the new expression.

Practice exercises

1. Simulate a printer queue: add three documents, then print them in order with poll.
2. Use push and pop to reverse the words of the sentence "Java is fun".
3. Check whether a text has balanced brackets () using a stack.