JAVA-201 · Lesson 9 of 12 · 26 min

Implementing a linked list

▶ Video coming soon A video version of this lesson is on the way.

Using a collection well is one skill; knowing how it works inside is another, and the second makes the first much easier. Ingrid's plan for Friday, March 19, 2027 is that Hamza builds his own linked list from nothing but nodes and references. It will not replace java.util.LinkedList, and the course never asks him to use it in place of the library. The point is to see exactly why adding at the front is O(1), why get(i) is O(n) and what can go wrong when references are changed in the wrong order. His list will hold the day's repair tags, in the order the volunteers want to work on them.

Nodes and references

A linked list is built from nodes. Each node holds one element and a reference to the next node. The list itself holds a reference to the first node, called the head, and the last node's next reference is null, which marks the end. Nothing else is needed: the order of the elements is the order of the chain. A Node<T> class is usually written as a private static nested class, because no code outside the list should ever see it.

Java Example · Main.java
public class Main {
    static class Node<T> {
        T value;
        Node<T> next;

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

    public static void main(String[] args) {
        Node<String> third = new Node<>("SG-0012-TA", null);
        Node<String> second = new Node<>("SG-0007-AR", third);
        Node<String> head = new Node<>("SG-0003-CI", second);

        for (Node<String> n = head; n != null; n = n.next) {
            System.out.println(n.value + (n.next == null ? " (last)" : " ->"));
        }
    }
}
Output
SG-0003-CI ->
SG-0007-AR ->
SG-0012-TA (last)

What this code does

Three nodes are chained by hand: head refers to the node for SG-0003-CI, which refers to the next, and the last node's next is null. The loop starts at head and follows next until it reaches null, visiting each tag once. This walk is the basic move of every linked-list method.

The loop for (Node<T> n = head; n != null; n = n.next) is worth memorizing. Almost every method of a linked list is a variation of it: walk until you find something, walk while counting, or walk while keeping a reference to the previous node so you can change its next.

A list class: addFirst and size

Wrapping the nodes in a class gives the list an interface and protects its invariants: head is null exactly when the list is empty, and size always equals the number of nodes. The simplest operation is addFirst: make a new node whose next is the old head, then make it the new head. Two reference changes, whatever the length of the list, so it is O(1).

Two panels. Before: head points to a chain of two nodes, SG-0007-AR then SG-0012-TA, ending in null. After addFirst(SG-0003-CI): a new node SG-0003-CI is drawn on the left; step 1, a dashed arrow from its next to the old first node; step 2, head is moved to point at the new node. A note says the order of the two steps matters: setting head first would lose the rest of the list.
addFirst: link the new node to the old head, then move head
Java Example · Main.java
public class Main {
    public static void main(String[] args) {
        TagList tags = new TagList();
        tags.addFirst("SG-0012-TA");
        tags.addFirst("SG-0007-AR");
        tags.addFirst("SG-0003-CI");
        System.out.println(tags + " size " + tags.size());
    }
}

class TagList {
    private static class Node {
        final String value;
        Node next;
        Node(String value, Node next) { this.value = value; this.next = next; }
    }

    private Node head;
    private int size;

    void addFirst(String value) {
        head = new Node(value, head);
        size++;
    }

    int size() { return size; }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (Node n = head; n != null; n = n.next) {
            sb.append(n.value);
            if (n.next != null) sb.append(", ");
        }
        return sb.append("]").toString();
    }
}
Output
[SG-0003-CI, SG-0007-AR, SG-0012-TA] size 3

What this code does

new Node(value, head) links the new node to the old head before head is reassigned, so the rest of the list is never lost. Each addFirst puts its tag in front, which is why the tags print in the reverse of the order they were added. size is kept up to date on every change, so asking for it is O(1).

A tail reference makes addLast O(1)

Volunteers usually want new tags at the end. Without help, addLast must walk the whole chain to find the last node, which is O(n). Keeping a second reference, tail, to the last node makes addLast O(1): link the new node after tail, then move tail. The price is one more invariant to keep right, since every method that changes the ends must now update tail as well as head.

Java Example · Main.java
public class Main {
    public static void main(String[] args) {
        TagList tags = new TagList();
        for (String t : new String[] {"SG-0003-CI", "SG-0007-AR", "SG-0012-TA"}) tags.addLast(t);
        tags.addFirst("SG-0001-CI");
        System.out.println(tags + " first " + tags.getFirst() + " last " + tags.getLast());
    }
}

class TagList {
    private static class Node {
        final String value;
        Node next;
        Node(String value) { this.value = value; }
    }

    private Node head, tail;
    private int size;

    void addFirst(String value) {
        Node n = new Node(value);
        n.next = head;
        head = n;
        if (tail == null) tail = n;
        size++;
    }

    void addLast(String value) {
        Node n = new Node(value);
        if (tail == null) {
            head = tail = n;
        } else {
            tail.next = n;
            tail = n;
        }
        size++;
    }

    String getFirst() { return head.value; }
    String getLast() { return tail.value; }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (Node n = head; n != null; n = n.next) sb.append(n.value).append(n.next != null ? ", " : "");
        return sb.append("]").toString();
    }
}
Output
[SG-0001-CI, SG-0003-CI, SG-0007-AR, SG-0012-TA] first SG-0001-CI last SG-0012-TA

What this code does

addLast links the new node after the current tail and then moves tail to it, so it never walks the list. The first node added to an empty list must become both head and tail, which is the special case in each method. getFirst and getLast read the two ends directly.

get(i): walking to a position

A linked list has no way to jump to position i; it must start at head and follow next i times. That makes get(i) O(n). It must also check the index, because walking past the end would reach null and then throw NullPointerException with an unhelpful message. Throwing IndexOutOfBoundsException with the index and size, as the library does, is far kinder to the caller.

Java Example · Main.java
public class Main {
    public static void main(String[] args) {
        TagList tags = new TagList();
        for (String t : new String[] {"SG-0003-CI", "SG-0007-AR", "SG-0012-TA", "SG-0015-CA"}) tags.addLast(t);
        System.out.println("tag 2: " + tags.get(2) + " after " + tags.lastSteps + " steps");
        System.out.println("tag 0: " + tags.get(0) + " after " + tags.lastSteps + " steps");
        try {
            tags.get(4);
        } catch (IndexOutOfBoundsException e) {
            System.out.println("refused: " + e.getMessage());
        }
    }
}

class TagList {
    private static class Node {
        final String value;
        Node next;
        Node(String value) { this.value = value; }
    }

    private Node head, tail;
    private int size;
    int lastSteps;

    void addLast(String value) {
        Node n = new Node(value);
        if (tail == null) head = tail = n; else { tail.next = n; tail = n; }
        size++;
    }

    String get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node n = head;
        lastSteps = 0;
        for (int i = 0; i < index; i++) {
            n = n.next;
            lastSteps++;
        }
        return n.value;
    }
}
Output
tag 2: SG-0012-TA after 2 steps
tag 0: SG-0003-CI after 0 steps
refused: Index: 4, Size: 4

What this code does

get(2) follows next twice from the head before it reaches the third tag, while get(0) needs no steps at all. The number of steps grows with the index, which is what O(n) means here. An index past the end is refused with a clear message instead of a NullPointerException.

Removing: the previous node problem

Removing the first node is O(1): move head to head.next. Removing any other node is harder in a singly linked list, because to unlink a node you must change the next reference of the node before it, and the nodes do not point backwards. The usual technique is to walk with two references, prev and current, so that when current is the node to remove, prev is right behind it. Then prev.next = current.next skips it, and the removed node, with nothing pointing to it, is collected by the garbage collector.

Java Example · Main.java
public class Main {
    public static void main(String[] args) {
        TagList tags = new TagList();
        for (String t : new String[] {"SG-0003-CI", "SG-0007-AR", "SG-0012-TA", "SG-0015-CA"}) tags.addLast(t);
        System.out.println(tags.remove("SG-0012-TA") + " " + tags);
        System.out.println(tags.remove("SG-0003-CI") + " " + tags);
        System.out.println(tags.remove("SG-0015-CA") + " " + tags + ", last is now " + tags.getLast());
        System.out.println(tags.remove("SG-9999-XX") + " " + tags);
    }
}

class TagList {
    private static class Node {
        final String value;
        Node next;
        Node(String value) { this.value = value; }
    }

    private Node head, tail;
    private int size;

    void addLast(String value) {
        Node n = new Node(value);
        if (tail == null) head = tail = n; else { tail.next = n; tail = n; }
        size++;
    }

    boolean remove(String value) {
        Node prev = null;
        for (Node cur = head; cur != null; prev = cur, cur = cur.next) {
            if (cur.value.equals(value)) {
                if (prev == null) head = cur.next; else prev.next = cur.next;
                if (cur == tail) tail = prev;
                size--;
                return true;
            }
        }
        return false;
    }

    String getLast() { return tail.value; }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (Node n = head; n != null; n = n.next) sb.append(n.value).append(n.next != null ? ", " : "");
        return sb.append("]").toString();
    }
}
Output
true [SG-0003-CI, SG-0007-AR, SG-0015-CA]
true [SG-0007-AR, SG-0015-CA]
true [SG-0007-AR], last is now SG-0007-AR
false [SG-0007-AR]

What this code does

remove walks with prev one node behind cur, so when it finds the tag it can link prev straight to the node after cur. Removing the head and removing the tail are special cases: the first moves head, and the second moves tail back to prev. A tag that is not in the list leaves it unchanged and returns false.

A neat way to remove the special case at the front is a sentinel, also called a dummy node: a node that always sits before the first real element and holds no value. Every real node then has a node before it, so the same code removes the first element and any other. java.util.LinkedList takes another route; it is doubly linked, with a prev reference in every node, so it can remove a node it is holding in O(1) without a walk.

Making the list iterable and generic

So far the list holds Strings. Making it generic is a matter of adding a type parameter, exactly as in lesson 1, and making it Iterable lets callers use the enhanced for loop, as in lesson 8. The iterator only needs to remember the node it will return next.

Java Example · Main.java
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        MyList<Integer> counts = new MyList<>();
        counts.addLast(14);
        counts.addLast(6);
        counts.addLast(9);
        int total = 0;
        for (int c : counts) total += c;
        System.out.println("total " + total + " over " + counts.size() + " parts");

        MyList<String> tags = new MyList<>();
        tags.addLast("SG-0003-CI");
        tags.addLast("SG-0007-AR");
        for (String t : tags) System.out.println(t);
    }
}

class MyList<T> implements Iterable<T> {
    private static class Node<T> {
        final T value;
        Node<T> next;
        Node(T value) { this.value = value; }
    }

    private Node<T> head, tail;
    private int size;

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

    int size() { return size; }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<>() {
            private Node<T> cur = head;

            @Override
            public boolean hasNext() { return cur != null; }

            @Override
            public T next() {
                if (cur == null) throw new NoSuchElementException();
                T v = cur.value;
                cur = cur.next;
                return v;
            }
        };
    }
}
Output
total 29 over 3 parts
SG-0003-CI
SG-0007-AR

What this code does

MyList<T> is the same chain of nodes with a type parameter, so one class holds Integers in one list and Strings in another. Its iterator remembers the node to return next and steps along the chain, so the enhanced for loop walks the list once in O(n). The total of the three counts is 29.

Reversing a list in place

A classic exercise, and a classic interview question, is to reverse a linked list without making new nodes. Walk the list once, and at each node point its next back at the previous node. Three references are needed, prev, cur and the saved next, because once cur.next is changed the rest of the list would be lost if it had not been saved first. At the end, head and tail swap.

Three rows showing a list of three nodes A, B, C being reversed. Row 1: prev is null, cur is A, next saved as B; A.next is turned to point at null. Row 2: prev is A, cur is B, next saved as C; B.next is turned to point at A. Row 3: prev is B, cur is C, next saved as null; C.next is turned to point at B. Final: head points to C, and the chain reads C, B, A, null.
Reversing in place: save next, turn the arrow, move on
Java Example · Main.java
public class Main {
    public static void main(String[] args) {
        TagList tags = new TagList();
        for (String t : new String[] {"SG-0003-CI", "SG-0007-AR", "SG-0012-TA", "SG-0015-CA"}) tags.addLast(t);
        System.out.println("before:  " + tags);
        tags.reverse();
        System.out.println("after:   " + tags);
        tags.addLast("SG-0001-CI");
        System.out.println("addLast: " + tags);
    }
}

class TagList {
    private static class Node {
        final String value;
        Node next;
        Node(String value) { this.value = value; }
    }

    private Node head, tail;

    void addLast(String value) {
        Node n = new Node(value);
        if (tail == null) head = tail = n; else { tail.next = n; tail = n; }
    }

    void reverse() {
        Node prev = null, cur = head;
        tail = head;
        while (cur != null) {
            Node next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        head = prev;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (Node n = head; n != null; n = n.next) sb.append(n.value).append(n.next != null ? ", " : "");
        return sb.append("]").toString();
    }
}
Output
before:  [SG-0003-CI, SG-0007-AR, SG-0012-TA, SG-0015-CA]
after:   [SG-0015-CA, SG-0012-TA, SG-0007-AR, SG-0003-CI]
addLast: [SG-0015-CA, SG-0012-TA, SG-0007-AR, SG-0003-CI, SG-0001-CI]

What this code does

Each pass saves cur.next before turning cur's arrow back to prev, then moves both references one node on. After the loop prev is the old last node, which becomes the new head, and the old head was recorded as the new tail before the loop began. addLast still works afterwards, which shows the tail invariant was kept.

Your list and the library's

Costs of three list implementations
OperationThis singly linked listjava.util.LinkedListArrayList
addFirstO(1)O(1)O(n)
addLastO(1) with tailO(1)O(1) amortized
removeFirstO(1)O(1)O(n)
removeLastO(n): must find the node before tailO(1): prev referencesO(1)
get(i)O(n)O(n), from the nearer endO(1)
remove a node you holdO(n) to find prevO(1) through an iteratorO(n) to shift

Building the list shows where every cost comes from. It also shows why the library's classes are long: they handle nulls, check indexes, keep modification counts for fail-fast iterators, implement dozens of interface methods and are tested against millions of programs. In real code, use the library. Write your own structure only to learn, or when no library structure fits and you have measured that it matters.

Try it yourself

Counting the nodes

TagList has no size field. Complete countStartingWith so it walks the chain from head and counts the tags that start with the given prefix.

The program should print cargo bikes: 2 and all tags: 4.

public class Main {
    public static void main(String[] args) {
        TagList tags = new TagList();
        for (String t : new String[] {"SG-0003-CA", "SG-0007-CI", "SG-0012-CA", "SG-0015-TA"}) tags.addLast(t);
        System.out.println("cargo bikes: " + tags.countEndingWith("-CA"));
        System.out.println("all tags: " + tags.countStartingWith("SG-"));
    }
}

class TagList {
    private static class Node {
        final String value;
        Node next;
        Node(String value) { this.value = value; }
    }

    private Node head, tail;

    void addLast(String value) {
        Node n = new Node(value);
        if (tail == null) head = tail = n; else { tail.next = n; tail = n; }
    }

    int countEndingWith(String suffix) {
        int c = 0;
        for (Node n = head; n != null; n = n.next) if (n.value.endsWith(suffix)) c++;
        return c;
    }

    int countStartingWith(String prefix) {
        return 0;
    }
}

Try it yourself

removeFirst

Complete removeFirst so it removes and returns the first tag. Move head on, and when the list becomes empty set tail to null too. If the list is already empty, throw NoSuchElementException.

The program should print served SG-0003-CI, served SG-0007-AR, [] and empty: true.

import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        TagList tags = new TagList();
        tags.addLast("SG-0003-CI");
        tags.addLast("SG-0007-AR");
        System.out.println("served " + tags.removeFirst());
        System.out.println("served " + tags.removeFirst());
        System.out.println(tags);
        System.out.println("empty: " + tags.isEmpty());
    }
}

class TagList {
    private static class Node {
        final String value;
        Node next;
        Node(String value) { this.value = value; }
    }

    private Node head, tail;

    void addLast(String value) {
        Node n = new Node(value);
        if (tail == null) head = tail = n; else { tail.next = n; tail = n; }
    }

    String removeFirst() {
        return head.value;
    }

    boolean isEmpty() { return head == null && tail == null; }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (Node n = head; n != null; n = n.next) sb.append(n.value).append(n.next != null ? ", " : "");
        return sb.append("]").toString();
    }
}

Common mistakes

  • MistakeReassigning head before linking the new node to the old head.

    InsteadLink first, then move: new Node(value, head), and only then head = the new node.

  • MistakeForgetting to update tail when the last node is removed or the first node is added to an empty list.

    InsteadCheck the empty and one-element cases in every method that changes the ends.

  • MistakeWalking past the end and getting a NullPointerException.

    InsteadCheck the index against size first and throw IndexOutOfBoundsException with a clear message.

  • MistakeLosing the rest of the list while reversing it.

    InsteadSave cur.next in a variable before changing cur.next.

  • MistakeUsing a home-made list in production code.

    InsteadBuild your own to learn; use ArrayList, ArrayDeque or LinkedList in real programs.

Summary and key terms

  • A linked list is a chain of nodes, each holding an element and a reference to the next node, with the list holding a reference to the head and the last node's next set to null.
  • Almost every method walks the chain with for (Node n = head; n != null; n = n.next). addFirst is O(1): link the new node to the old head, then move head.
  • Keeping a tail reference makes addLast O(1) too, at the cost of one more invariant. get(i) must walk i nodes and is O(n), and it should check the index and throw IndexOutOfBoundsException.
  • Removing a node from a singly linked list needs the node before it, so the walk keeps a prev reference; a sentinel node removes the special case at the front, and a doubly linked list removes the need for the walk.
  • A list becomes generic with a type parameter and usable in for-each by implementing Iterable.
  • Reversing in place turns every next reference around using prev, cur and a saved next.
  • Building one teaches the costs; in real code, use the library.
Node
An object holding one element and a reference to the next node.
Head
The reference to the first node of a linked list.
Tail
The reference to the last node, kept to make addLast O(1).
Singly linked list
A linked list whose nodes refer only to the next node.
Doubly linked list
A linked list whose nodes refer to both the next and the previous node.
Invariant
A condition that must always hold, such as head being null exactly when the list is empty.
Sentinel node
A dummy node before the first element that removes special cases at the front.
Static nested class
A class declared inside another with static, used here for Node.
IndexOutOfBoundsException
The exception thrown for an index outside 0 to size minus 1.
Garbage collection
The JVM reclaiming objects, such as unlinked nodes, that nothing refers to.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. Why is addFirst O(1) in a linked list?

    Show answer

    It changes only two references, whatever the length of the list.

  2. What does a tail reference buy you, and what does it cost?

    Show answer

    O(1) addLast, at the cost of updating tail in every method that changes the ends.

  3. Why is removing a node harder than adding one in a singly linked list?

    Show answer

    You must change the next of the node before it, so the walk must keep a prev reference.

  4. What three references does an in-place reverse need?

    Show answer

    prev, cur and the saved next.

  5. Should you use your own linked list in production code?

    Show answer

    No; use the library's collections and build your own only to learn.

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz