Linked Lists in Java

A linked list stores each element in its own node. A node holds a value and a reference to the next node, and the last node's reference is null, which means "no node".

graph LR
    H(["head"]) --> A["1"]
    A --> B["2"]
    B --> C["3"]
    C --> N(["null"])

Unlike an array, the nodes aren't next to each other in memory, so there's no indexing: to reach the 3rd node, you follow next twice from the head. In exchange, adding or removing a node at a known position doesn't shift anything.

Operation	Array / `ArrayList`	Singly linked list
access element `i`	`O(1)`	`O(i)`, follow `next` `i` times
insert or remove at the front	`O(n)` (shift)	`O(1)`
insert or remove after a node you already have	`O(n)` (shift)	`O(1)`
insert at the end	`O(1)` amortized	`O(n)` without a tail reference
search for a value	`O(n)`	`O(n)`

A doubly linked list also stores a prev reference in each node, so it can be walked in both directions, and a node can be removed without knowing its predecessor. Java's standard library has one: java.util.LinkedList.

In practice, ArrayList and ArrayDeque are faster than a linked list for almost everything, because of CPU caching. Linked lists matter in interviews because they test whether you can rewire references correctly.

References and `null`

A Java variable of a class type holds a reference to an object, not the object itself. Two variables can refer to the same node, and assigning a reference copies only the reference. Linked list code therefore works by changing next fields. Every next access on a null reference throws NullPointerException, so each loop checks for null before it reads next.

There is no Box, Option, or ownership wrapper here: a node is an object with mutable fields, and null marks the end. The garbage collector reclaims a node when nothing refers to it, so removing a node means only making the list skip it.

The node type

LeetCode's Java problems use a ListNode class with an int val and a ListNode next, and every lesson in this section uses the same shape:

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1, null);
        head.next = new ListNode(2, null);
        head.next.next = new ListNode(3, null);
        System.out.println(head.val + " -> " + head.next.val + " -> " + head.next.next.val);
    }
}

Output

1 -> 2 -> 3

Expression	Meaning
`ListNode` variable	a reference to one node, or `null`
`head`	the first node, or `null` for an empty list
`node.next`	the link out of `node`, which can be reassigned
`static class ListNode`	a nested class; the examples nest it in `Main` so each block is one complete program

A class can hold a reference to its own type, because a reference has a fixed size.

Two helpers for examples

Every example in this section builds a list from an array and prints it back as a List<Integer>:

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    public static void main(String[] args) {
        ListNode list = fromArray(1, 2, 3);
        System.out.println(toList(list));
    }
}

Output

[1, 2, 3]

fromArray builds the list backwards: each new node is created with the current list as its next, which is an O(1) insert at the head. toList walks the list with a loop that stops at null, which is pattern 4 below. fromArray(int... values) takes a variable number of arguments, so fromArray() builds an empty list (null).

Pattern 1: save `next` before relinking

To move or reverse a node, first save its next in a local variable, because assigning a new value to node.next loses the old one. Reversing a list uses this on every node:

graph LR
    subgraph before["before"]
        n1["node 1"] --> n2["2"] --> n3["3"] --> x1(["null"])
    end
    subgraph after["after: next = node.next; node.next = null"]
        m1["node 1"] --> x2(["null"])
        r(["next"]) --> m2["2"] --> m3["3"] --> x3(["null"])
    end

Now next refers to the rest of the list, and node can be pointed somewhere else.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next; // save the rest
            head.next = prev;          // point this node backwards
            prev = head;               // this node is now the front of the reversed part
            head = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        System.out.println(toList(reverseList(fromArray(1, 2, 3))));
        System.out.println(toList(reverseList(null)));
    }
}

Output

[3, 2, 1]
[]

Use it for reversing, reordering, and swapping nodes.

Pattern 2: a dummy node and a `tail` reference

To build a list from front to back, start with a dummy node and keep a reference to the last node. Each append assigns tail.next and then moves tail to the new node:

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode build(int[] values) {
        ListNode dummy = new ListNode(0, null);
        ListNode tail = dummy;
        for (int val : values) {
            tail.next = new ListNode(val, null);
            tail = tail.next; // move tail to the node just added
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        System.out.println(toList(build(new int[]{4, 5, 6})));
        System.out.println(toList(build(new int[]{})));
    }
}

Output

[4, 5, 6]
[]

The dummy means the first append isn't a special case, since there's always a node to append after. The real list starts at dummy.next. Use it for merging, partitioning, and building results.

Pattern 3: a trailing `prev` pointer

To insert or delete, keep prev, a reference to the node before the one being examined. Setting prev.next changes what the list contains. Starting prev at a dummy node placed before the head makes deleting the first node work like deleting any other:

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode removeAll(ListNode head, int target) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        while (prev.next != null) {
            if (prev.next.val == target) {
                prev.next = prev.next.next; // the list now skips the removed node
            } else {
                prev = prev.next;           // move on only when nothing was removed
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        System.out.println(toList(removeAll(fromArray(2, 1, 2, 3, 2), 2)));
    }
}

Output

[1, 3]

The removed nodes have no references left, so the garbage collector reclaims them. Use this pattern for removing, inserting after a position, and deduplicating.

Pattern 4: read-only traversal

When the list is only read, walk with a local variable that starts at head and moves to next until it is null. The parameter head is a copy of the reference, so moving it does not change the caller's variable:

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static int sum(ListNode head) {
        int total = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            total += cur.val;
        }
        return total;
    }

    public static void main(String[] args) {
        System.out.println(sum(fromArray(1, 2, 3, 4)));
        System.out.println(sum(null));
    }
}

Output

10
0

Any number of references can point into the same list, so fast and slow pointers work directly: both are ordinary variables that move at different speeds. A loop that moves fast two nodes at a time checks fast != null && fast.next != null first, so it never reads next on null. Because nodes are mutable, a problem that needs a position and a change can also be solved in one pass. The lessons that use a second pass (count first, then walk to an index) do it because it is simpler, not because Java requires it.

Two traps apply to every pattern:

Assigning a = b for two nodes copies the reference, not the node. A change through one is visible through the other.
A loop that never reaches null (a list with a cycle) never ends. See Detect a Cycle in a Linked List.

Cycles and doubly linked lists

Singly linked list problems need no wrapper types. Two cases involve more than one reference to a node:

Cycles: the last node's next refers to an earlier node. A HashSet of nodes or fast and slow pointers detects it. See Detect a Cycle in a Linked List.
Doubly linked lists: each node also has a prev field. Use java.util.LinkedList, which implements both List and Deque. See Doubly Linked List Palindrome.

Interview points

A linked list gives O(1) insertion and deletion at a known position and O(n) access by index.
A dummy node removes the special case for the head.
Save next before overwriting it.
Check for null before reading next.
Fast and slow pointers find the middle and detect cycles in O(1) space.

Summary

A node holds a value and a next reference; null ends the list.
Reassigning next fields changes the list; no data is copied.
The four patterns are: save next and relink, a dummy node with a tail reference, a trailing prev pointer, and read-only traversal.
java.util.LinkedList is a doubly linked list.

References and null

The node type

Two helpers for examples

Pattern 1: save next before relinking

Pattern 2: a dummy node and a tail reference

Pattern 3: a trailing prev pointer

Pattern 4: read-only traversal

Cycles and doubly linked lists

Interview points

Summary

References and `null`

Pattern 1: save `next` before relinking

Pattern 2: a dummy node and a `tail` reference

Pattern 3: a trailing `prev` pointer