Java Linked Lists (from scratch)

A linked list is a data structure made of individual nodes, where each node stores a value and a reference to the next node in the sequence. Unlike an array, a linked list does not live in one contiguous block of memory — it grows and shrinks by simply creating nodes and rewiring references. Understanding how to build one from scratch is one of the best ways to truly understand how Java references, the heap, and pointer-based structures work, and it forms the foundation for stacks, queues, and trees.

Overview: How a Linked List Works

An array allocates one contiguous block of memory up front. Accessing element i is O(1) because the runtime can compute its address directly, but inserting or removing an element in the middle means shifting every element after it, and resizing means copying the whole array. A linked list solves this differently: instead of one big block, every element is its own small object (a node) allocated separately on the heap. Each node holds two things: the data, and a reference (in Java, an object reference, conceptually a pointer) to the next node. The list itself only needs to remember one thing — a reference to the first node, called the head. The last node’s next reference is set to null, which marks the end of the list.

Because nodes are scattered across the heap and linked only by references, insertion and deletion at a known position are O(1) — you just rewire a couple of references, no shifting required. The trade-off is that you lose random access: to reach the 500th node you must walk the list one next reference at a time from the head, which is O(n). This is the fundamental trade-off between arrays and linked lists, and it is why real programs choose one or the other based on whether they insert/delete a lot (favor linked lists) or read by index a lot (favor arrays).

This lesson builds a singly linked list, where each node points only forward. A doubly linked list adds a prev reference so you can walk backward too (this is what java.util.LinkedList actually is internally). Every node you create with new Node(...) is a genuine heap-allocated object; once no live reference points to it (for example after you unlink it from the list), it becomes eligible for garbage collection just like any other unreachable object — you never manually free memory in Java.

Syntax

A linked list is built from two pieces: a node class that holds data and a reference to the next node, and a wrapper class that tracks the head (and often a size) and exposes operations like addFirst, addLast, and delete.

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
  • data — the value stored in this node (here an int; in real code this is often a generic type T).
  • next — a reference to the following node, or null if this is the last node.
  • The constructor initializes data and defaults next to null, since a brand-new node is not yet linked to anything.
  • The list wrapper class keeps a head field (a reference to the first Node, or null for an empty list) and typically a size counter so callers do not have to walk the whole list just to count it.

Examples

Example 1: A Singly Linked List With Insert, Delete, and Search

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    Node head;
    int size;

    void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
        size++;
    }

    void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    boolean delete(int data) {
        if (head == null) return false;
        if (head.data == data) {
            head = head.next;
            size--;
            return true;
        }
        Node current = head;
        while (current.next != null) {
            if (current.next.data == data) {
                current.next = current.next.next;
                size--;
                return true;
            }
            current = current.next;
        }
        return false;
    }

    boolean contains(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) return true;
            current = current.next;
        }
        return false;
    }

    void printList() {
        Node current = head;
        StringBuilder sb = new StringBuilder();
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) sb.append(" -> ");
            current = current.next;
        }
        System.out.println(sb.toString());
    }
}

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.addLast(10);
        list.addLast(20);
        list.addLast(30);
        list.addFirst(5);
        list.printList();
        System.out.println("Size: " + list.size);
        list.delete(20);
        list.printList();
        System.out.println("Contains 30? " + list.contains(30));
        System.out.println("Contains 20? " + list.contains(20));
    }
}
5 -> 10 -> 20 -> 30
Size: 4
5 -> 10 -> 30
Contains 30? true
Contains 20? false

Output: addLast walks to the last node and attaches a new one, so 10, 20, and 30 get chained in order. addFirst makes the new node point at the current head, then reassigns head to the new node — this is why 5 ends up in front. delete(20) walks the list looking one step ahead (current.next) so it can skip over the matching node by linking current.next directly to current.next.next, cutting node 20 out of the chain entirely.

Example 2: Reversing a Linked List In Place

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

public class Main {
    static Node reverse(Node head) {
        Node prev = null;
        Node current = head;
        while (current != null) {
            Node nextNode = current.next;
            current.next = prev;
            prev = current;
            current = nextNode;
        }
        return prev;
    }

    static void print(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data);
            if (current.next != null) System.out.print(" -> ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);

        System.out.print("Original: ");
        print(head);

        Node reversed = reverse(head);
        System.out.print("Reversed: ");
        print(reversed);
    }
}
Original: 1 -> 2 -> 3 -> 4
Reversed: 4 -> 3 -> 2 -> 1

This is the classic in-place reversal algorithm. It uses three pointers — prev, current, and a temporary nextNode — to flip each next reference without losing track of the rest of the list. It runs in O(n) time and O(1) extra space, since no new nodes are allocated.

Example 3: Using a Linked List to Build a Stack

class StackNode {
    int data;
    StackNode next;

    StackNode(int data) {
        this.data = data;
    }
}

class LinkedStack {
    private StackNode top;

    void push(int data) {
        StackNode node = new StackNode(data);
        node.next = top;
        top = node;
    }

    int pop() {
        if (top == null) throw new RuntimeException("Stack is empty");
        int value = top.data;
        top = top.next;
        return value;
    }

    boolean isEmpty() {
        return top == null;
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedStack stack = new LinkedStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}
3
2
1

This shows why linked lists matter beyond being a teaching exercise: a stack is naturally a linked list where you only ever insert and remove at the head (here called top). Because that operation is O(1) on a linked list, there is no shifting or resizing — pushing and popping are as cheap as they can possibly be.

Under the Hood: Step by Step

Walking through reverse() on the list 1 -> 2 -> 3 -> null makes the pointer manipulation concrete:

  • Start: prev = null, current = 1.
  • Iteration 1: save nextNode = 2; point 1.next at prev (null), so node 1 now terminates the list; move prev = 1, current = 2.
  • Iteration 2: save nextNode = 3; point 2.next at prev (node 1); move prev = 2, current = 3.
  • Iteration 3: save nextNode = null; point 3.next at prev (node 2); move prev = 3, current = null.
  • Loop ends because current is null. prev now points at node 3, the new head, and the chain reads 3 -> 2 -> 1 -> null.

Notice that at every step the algorithm saves current.next into nextNode before overwriting current.next. Skipping that save is exactly how you accidentally sever a list, because once current.next is overwritten, the original rest of the list is unreachable.

Common Mistakes

Mistake 1: Traversing Without a Null Check

A very common bug is walking the list looking for a value without checking whether you have run off the end:

Node current = head;
while (current.data != target) {
    current = current.next;
}
System.out.println("Found: " + current.data);

If target is not in the list, current eventually becomes null, and the next loop check current.data throws a NullPointerException. The loop condition must check for the end of the list first:

Node current = head;
while (current != null && current.data != target) {
    current = current.next;
}
if (current != null) {
    System.out.println("Found: " + current.data);
} else {
    System.out.println("Not found");
}

Mistake 2: Reordering Pointer Assignments When Inserting

When inserting a new node in the middle of a list, the order of the two pointer assignments matters. This version links the new node in first, then tries to point it at the rest of the list — but by then the rest of the list is already gone:

Node newNode = new Node(data);
current.next = newNode;
newNode.next = current.next;

After the first line, current.next already is newNode, so the second line sets newNode.next = newNode — the node now points at itself, creating a cycle and silently dropping everything that used to follow current. The fix is to always capture the old next reference before overwriting it:

Node newNode = new Node(data);
newNode.next = current.next;
current.next = newNode;

Best Practices

  • Always assign a new node’s next reference before you rewire the existing node’s next reference, or you will lose the rest of the list.
  • Handle the empty-list case (head == null) and the single-node case explicitly — they are the most common source of edge-case bugs.
  • Keep a size field updated on every insert/delete so callers get O(1) size lookups instead of an O(n) traversal.
  • Never mutate head directly while searching — use a separate current pointer for traversal so you do not lose the start of the list.
  • Prefer iteration over recursion for list operations; a recursive traversal on a very long list can throw StackOverflowError.
  • In real production code, reach for java.util.LinkedList (a doubly linked, well-tested implementation of List and Deque) rather than hand-rolling one, unless the point of the exercise is to learn the internals.
  • Write a toString() or printList() helper early — visualizing the chain makes every other bug easier to spot.

Practice Exercises

  • Write a method int size(Node head) that counts the nodes in a list by traversal, without relying on a stored size field. Test it against the list built in Example 1.
  • Implement Node findMiddle(Node head) using the classic fast/slow pointer technique (the fast pointer moves two nodes at a time, the slow pointer moves one) so it finds the middle node in a single pass.
  • Write a method that removes duplicate values from a linked list of integers while preserving the order of first occurrence. For input 1 -> 2 -> 2 -> 3 -> 1 -> 4, the expected output is 1 -> 2 -> 3 -> 4.

Summary

  • A linked list is a chain of independently heap-allocated Node objects, each holding data and a reference to the next node; the list itself only needs to remember the head.
  • Insertion and deletion at a known position are O(1) because they only rewire references, but random access by index is O(n) because you must walk from the head.
  • Building operations like addFirst, addLast, delete, and contains requires careful traversal and pointer bookkeeping — always check for null before dereferencing.
  • Reversing a list in place uses three pointers (prev, current, and a saved next) to flip each link without losing the rest of the chain.
  • Linked lists are the natural backing structure for stacks and queues, since both only insert/remove at one end.
  • The two most common bugs are missing null checks during traversal and reordering pointer assignments during insertion — both cause either crashes or silently lost nodes.