Java Linked Lists (from scratch)

A linked list is a data structure made of nodes, where each node stores a value and a reference to the next node. Instead of storing items side by side like an array, a linked list connects items one at a time.

Java already has java.util.LinkedList, but building a small one from scratch helps you understand how node-based data structures work.

The Node Idea

Each node needs two pieces of information: the value it stores and a reference to the next node. The first node is usually called head. If you also store a tail reference, adding to the end can be direct because the list remembers its last node.

• head points to the first node.
• tail points to the last node.
• next points from one node to the following node.
• null means there is no next node.

Build A Simple Linked List

This example creates a small linked list that stores int values. It supports adding to the front, adding to the back, removing the first node, searching, checking the size, and printing the list.

public class Main {
    static class Node {
        int value;
        Node next;

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

    static class IntLinkedList {
        private Node head;
        private Node tail;
        private int size;

        public void addFirst(int value) {
            Node node = new Node(value);

            if (head == null) {
                head = node;
                tail = node;
            } else {
                node.next = head;
                head = node;
            }

            size++;
        }

        public void addLast(int value) {
            Node node = new Node(value);

            if (tail == null) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                tail = node;
            }

            size++;
        }

        public boolean removeFirst() {
            if (head == null) {
                return false;
            }

            head = head.next;
            if (head == null) {
                tail = null;
            }

            size--;
            return true;
        }

        public boolean contains(int value) {
            Node current = head;

            while (current != null) {
                if (current.value == value) {
                    return true;
                }
                current = current.next;
            }

            return false;
        }

        public int size() {
            return size;
        }

        public void print() {
            Node current = head;

            while (current != null) {
                System.out.print(current.value);
                if (current.next != null) {
                    System.out.print(" -> ");
                }
                current = current.next;
            }

            System.out.println();
        }
    }

    public static void main(String[] args) {
        IntLinkedList numbers = new IntLinkedList();

        numbers.addLast(10);
        numbers.addLast(20);
        numbers.addFirst(5);

        numbers.print();
        System.out.println("Contains 20: " + numbers.contains(20));

        numbers.removeFirst();
        numbers.print();
        System.out.println("Size: " + numbers.size());
    }
}

Output:

5 -> 10 -> 20
Contains 20: true
10 -> 20
Size: 2

How It Works

addFirst() creates a new node, points it at the old head, and then makes the new node the head. If the list was empty, both head and tail point to the same new node.

addLast() uses tail.next to attach the new node after the old last node, then moves tail forward. This is why keeping a tail reference is useful.

removeFirst() moves head to head.next. If that makes head become null, the list is empty, so tail must also become null.

Traversal

Traversal means walking through the list one node at a time. The contains() and print() methods both start at head, use a current variable, and repeatedly move to current.next until they reach null.

Performance Basics

Operation	With This Design	Why
Add first	O(1)	Only changes head
Add last	O(1)	Uses stored tail
Search	O(n)	May visit every node
Access by index	O(n)	Must walk from head

Common Mistakes

• Forgetting to update tail when the list becomes empty.
• Losing the rest of the list by changing head before saving the needed reference.
• Using a linked list when frequent index access would make an array or ArrayList simpler.

Takeaway: a linked list is a chain of nodes, and most operations work by carefully changing which node each reference points to.