LinkedList

Picture a treasure hunt. You are handed the first clue. It does not hold the treasure. It says where the next clue is hidden. That clue points to the next, and so on, until the last one shows you the prize. There is no list of every clue. The only way to reach clue number 5 is to follow clues 1 to 4.

A LinkedList is that hunt. Its items live in separate little objects called nodes. Each node holds one item and a link, which is a reference saying where another node is. Java's LinkedList goes one step further than the hunt: every clue card also says where you came from. Each node has a link to the next node and a link to the one before, so it is doubly linked and can be walked in either direction.

The list itself only remembers where the chain begins and where it ends. Everything else is reached by following links.

Here is an honest note before we start. LinkedList gets a lot of attention in books and interviews, but in everyday Java it is rarely the right choice. An ArrayList is usually faster even for jobs where a linked list sounds better on paper. So why learn it? Because it shows the opposite trade-off to ArrayList, because it teaches you to think in nodes and links, and because interviewers love it.

Remember: in everyday Java, use an ArrayList. Learn the LinkedList to understand the trade-off, and to pass the interview.

The picture shows three nodes. Each has three parts: a link back (prev), the item, and a link forward (next). first points at the first node and last at the final one. The first node's prev and the last node's next are null, which means "no node there".

Adding to the front is quick. Make a node, point its next at the old first node, point the old first node's prev back at it, and move first. Nothing else moves, however long the list is. Adding at the end works the same way, using last. Taking an item off either end is just as quick.

Reading item number 5 is the problem. There is no table of addresses. You start at first and follow four links. The real LinkedList is a little clever: it starts from whichever end is nearer. But in the middle of a long list, it still has to walk a long way.

LinkedList is a List, so everything from the last lesson works on it. On top of that it has methods for working at the two ends. Every block below can be pasted into jshell.

LinkedList<String> hunt = new LinkedList<>();
hunt.addLast("clue 2");
hunt.addFirst("clue 1"); // cheap: only the front links change
hunt.addLast("clue 3");
System.out.println(hunt);
System.out.println(hunt.getFirst());
System.out.println(hunt.removeFirst());
System.out.println(hunt.getLast());
System.out.println(hunt.size());

[clue 1, clue 2, clue 3]
clue 1
clue 1
clue 3
2

addFirst and addLast add at either end. getFirst and getLast look at the ends without removing anything, and removeFirst takes the first item off and hands it to you. After that, two clues remain.

Because it also implements Queue, you can use it as a waiting line:

// A LinkedList is also a Queue, so it can serve a line of people.
Queue<String> line = new LinkedList<>();
line.offer("Asha");
line.offer("Ravi");
System.out.println(line.poll());
System.out.println(line.peek());

Asha
Ravi

offer joins the back and poll takes from the front, just as in lesson 1. It works, but for a plain queue Java has a better class, ArrayDeque, which lesson 9 covers. The only reason to pick LinkedList as a queue is if you need to allow null items, which ArrayDeque refuses.

To see how it works, build a smaller version. Java's real LinkedList has two links per node. We will use one, because the idea is the same and the code is half as long. This is also the shape of the linked lists in most interview questions.

First, the node.

static class Node<T> {
    T value;
    Node<T> next; // null marks the end of the chain

    Node(T value, Node<T> next) {
        this.value = value;
        this.next = next;
    }
}

A Node<T> holds a value and a next link. The T is the placeholder from lesson 2, so one node class can hold anything. next is null for the last node.

Now the list.

static class TinyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail; // remembering the tail makes addLast quick
    private int size = 0;

    int size() {
        return size;
    }

    void addFirst(T value) {
        head = new Node<>(value, head);
        if (tail == null) {
            tail = head; // the list was empty, so the new node is also the last
        }
        size++;
    }

    void addLast(T value) {
        Node<T> node = new Node<>(value, null);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    T removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("the list is empty");
        }
        T value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
        }
        // No shortcut to slot number index: follow the links, one by one.
        Node<T> current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.value;
    }
}

Go through it in order.

• head is the first node and tail is the last. Keeping tail is what lets addLast be quick, because we don't need to walk to the end to find it.
• addFirst makes a new node whose next is the old head, then makes it the head. If the list was empty, that new node is also the tail.
• addLast makes a node and hooks it after the tail. If the list was empty, it becomes the head too.
• removeFirst reads the head's value and moves head along to the next node. If that leaves the list empty, tail must be cleared as well. Forgetting that is a classic bug.
• get has no shortcut. It starts at head and follows next links, index times.

TinyLinkedList<String> clues = new TinyLinkedList<>();
clues.addLast("clue 2");
clues.addFirst("clue 1");
clues.addLast("clue 3");
System.out.println(clues.get(2)); // follows three links to get there
System.out.println(clues.removeFirst());
System.out.println(clues.size());

clue 3
clue 1
2

Asking for item 2 took two steps along the chain. The cost of get depends on how far in the item is, and that is the weakness of the whole idea.

Why is it often slower than an ArrayList in practice, even for the jobs it seems to suit? Each node is a separate object, so the nodes are scattered around memory, and each one carries extra links. A computer reads memory fastest when it is read in order and close together, which is exactly what an array gives it. Following scattered links is slower. You don't need to remember the details, only the conclusion: "inserts in the middle are O(1)" is true for the relinking, but finding the spot costs O(n) first.

Compare this with the ArrayList table from lesson 3. The two are almost mirror images: ArrayList is fast at get(i) and slow at the front, and LinkedList is the other way round. The catch is that the mirror is not even. Per item, a LinkedList uses more memory, and its get(i) weakness hits far more often than its front-and-back strength.

The first uses Java's own LinkedList. The other two use the Node class from above, as an interview would.

static void rotateLeft(LinkedList<Integer> list, int k) {
    throw new UnsupportedOperationException("move the first k items to the back, in order");
}

static void rotateLeft(LinkedList<Integer> list, int k) {
    if (list.isEmpty()) {
        return;
    }
    // Rotating by the length is a full lap and changes nothing, so
    // only the remainder counts.
    int moves = k % list.size();
    for (int i = 0; i < moves; i++) {
        list.addLast(list.removeFirst()); // both ends are cheap on a LinkedList
    }
}

static <T> Node<T> reverse(Node<T> head) {
    throw new UnsupportedOperationException("flip every next link; return the new head");
}

static <T> Node<T> reverse(Node<T> head) {
    Node<T> reversed = null;
    Node<T> current = head;
    while (current != null) {
        Node<T> next = current.next; // save it before the link is overwritten
        current.next = reversed;
        reversed = current;
        current = next;
    }
    return reversed;
}

static <T> boolean hasCycle(Node<T> head) {
    throw new UnsupportedOperationException("does following next ever loop back?");
}

static <T> boolean hasCycle(Node<T> head) {
    // Two walkers, one twice as fast. In a loop the fast one laps the
    // slow one and they meet; in a straight chain the fast one falls off the end.
    Node<T> slow = head;
    Node<T> fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

LinkedList is a favourite interview topic, in two different ways: choosing it, and writing code with nodes.

• "ArrayList or LinkedList?" ArrayList almost always. It has O(1) get(i), uses less memory, and is quick to read because its items sit together. LinkedList wins only when you work at both ends all the time, and then ArrayDeque is usually better still.
• "Isn't inserting in a LinkedList O(1)?" Only once you are at the spot. Finding position i takes O(n), so add(i, x) is O(n) overall. This is the most common half-right answer, so saying it clearly stands out.
• "Why is get(i) slow?" There is no index to jump to. The list follows links from the nearer end.
• "Can a LinkedList hold null?" Yes. ArrayDeque can't, which is one real reason to choose the former.
• Reverse a linked list. Problem 2 is the standard answer: three variables, one pass, O(1) space. Say out loud that you save next before overwriting the link.
• Detect a cycle. Problem 3's slow and fast pointers is the expected answer. A set of visited nodes works but costs O(n) space, so mention it and then offer the better one.
• Say the cost. "Both ends are O(1), anything by position is O(n), and each item costs a whole node" is a complete answer.

Made by VeraStack Labs