Singly Linked List Explained — Build One From Scratch in Java

package io.thecodeforge.ds;

/**
 * A Node is the fundamental building block of a singly linked list.
 * Each node holds a value and a reference to the next node.
 * When nextNode is null, this is the last node in the chain.
 */
public class Node {

    int data;
    Node nextNode;

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

    public static void main(String[] args) {
        Node firstNode = new Node(42);
        Node secondNode = new Node(99);

        firstNode.nextNode = secondNode;

        System.out.println("First node data:  " + firstNode.data);
        System.out.println("Second node data: " + firstNode.nextNode.data);
        System.out.println("End of chain:     " + firstNode.nextNode.nextNode);
    }
}

package io.thecodeforge.ds;

/**
 * Production-grade singly linked list with insert, delete, traverse,
 * reverse, cycle detection, and tail-pointer optimization.
 */
public class SinglyLinkedList {

    static class Node {
        int data;
        Node nextNode;

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

    private Node head;
    private Node tail;
    private int size;

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void insertAtFront(int value) {
        Node newNode = new Node(value);
        newNode.nextNode = head;
        head = newNode;
        if (tail == null) {
            tail = newNode;
        }
        size++;
    }

    public void insertAtEnd(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.nextNode = newNode;
            tail = newNode;
        }
        size++;
    }

    public boolean deleteByValue(int value) {
        if (head == null) return false;

        if (head.data == value) {
            head = head.nextNode;
            if (head == null) {
                tail = null;
            }
            size--;
            return true;
        }

        Node previousNode = head;
        Node currentNode = head.nextNode;

        while (currentNode != null) {
            if (currentNode.data == value) {
                previousNode.nextNode = currentNode.nextNode;
                if (currentNode == tail) {
                    tail = previousNode;
                }
                size--;
                return true;
            }
            previousNode = currentNode;
            currentNode = currentNode.nextNode;
        }

        return false;
    }

    public void reverse() {
        Node prev = null;
        Node current = head;
        tail = head;

        while (current != null) {
            Node next = current.nextNode;
            current.nextNode = prev;
            prev = current;
            current = next;
        }

        head = prev;
    }

    public int findMiddle() {
        if (head == null) throw new IllegalStateException("List is empty");

        Node slow = head;
        Node fast = head;

        while (fast.nextNode != null && fast.nextNode.nextNode != null) {
            slow = slow.nextNode;
            fast = fast.nextNode.nextNode;
        }

        return slow.data;
    }

    public boolean hasCycle() {
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.nextNode != null) {
            slow = slow.nextNode;
            fast = fast.nextNode.nextNode;
            if (slow == fast) return true;
        }

        return false;
    }

    public void printList() {
        if (head == null) {
            System.out.println("[ Empty List ]");
            return;
        }

        Node currentNode = head;
        StringBuilder sb = new StringBuilder();

        while (currentNode != null) {
            sb.append(currentNode.data);
            if (currentNode.nextNode != null) {
                sb.append(" -> ");
            }
            currentNode = currentNode.nextNode;
        }

        sb.append(" -> null");
        System.out.println(sb);
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.printList();

        list.insertAtFront(5);
        list.printList();

        list.deleteByValue(20);
        list.printList();

        System.out.println("Middle: " + list.findMiddle());
        System.out.println("Has cycle: " + list.hasCycle());

        list.reverse();
        System.out.print("Reversed: ");
        list.printList();
    }
}

package io.thecodeforge.benchmark;

import java.util.LinkedList;
import java.util.ArrayList;

/**
 * Benchmark: LinkedList vs ArrayList for front insertion and random access.
 * Demonstrates why linked lists win at front insertion and lose at random access.
 */
public class LinkedListVsArray {

    public static void main(String[] args) {
        int insertionCount = 100_000;

        ArrayList<Integer> arrayList = new ArrayList<>();
        long arrayStart = System.nanoTime();
        for (int i = 0; i < insertionCount; i++) {
            arrayList.add(0, i);
        }
        long arrayDuration = (System.nanoTime() - arrayStart) / 1_000_000;

        LinkedList<Integer> linkedList = new LinkedList<>();
        long linkedStart = System.nanoTime();
        for (int i = 0; i < insertionCount; i++) {
            linkedList.addFirst(i);
        }
        long linkedDuration = (System.nanoTime() - linkedStart) / 1_000_000;

        System.out.println("Front insertion (100k elements):");
        System.out.println("  ArrayList:  " + arrayDuration + " ms");
        System.out.println("  LinkedList: " + linkedDuration + " ms");

        long arrAccessStart = System.nanoTime();
        int arrVal = arrayList.get(50_000);
        long arrAccessTime = System.nanoTime() - arrAccessStart;

        long llAccessStart = System.nanoTime();
        int llVal = linkedList.get(50_000);
        long llAccessTime = System.nanoTime() - llAccessStart;

        System.out.println("\nRandom access (index 50,000):");
        System.out.println("  ArrayList:  " + arrAccessTime + " ns (value=" + arrVal + ")");
        System.out.println("  LinkedList: " + llAccessTime + " ns (value=" + llVal + ")");
    }
}