Singly Linked List Explained — Build One From Scratch in Java

// A Node is the fundamental building block of a singly linked list.
// Think of it as one link in a metal chain — it holds a value and
// connects to the next link.

public class Node {

    // 'data' is the actual value this node is storing.
    // We're using int here, but this could be a String, an Object, anything.
    int data;

    // 'nextNode' is the reference (pointer) to the next Node in the chain.
    // When nextNode is null, this is the LAST node — the chain ends here.
    Node nextNode;

    // Constructor: creates a fresh node with a value and no connection yet.
    // nextNode defaults to null automatically in Java, but being explicit is good practice.
    public Node(int data) {
        this.data = data;
        this.nextNode = null; // No next node yet — this node is currently alone
    }

    public static void main(String[] args) {
        // Create two individual nodes — they're not connected yet
        Node firstNode = new Node(42);
        Node secondNode = new Node(99);

        // NOW connect them: firstNode points to secondNode
        firstNode.nextNode = secondNode;

        // Reading the chain: start at firstNode, follow the pointer to secondNode
        System.out.println("First node data:  " + firstNode.data);               // 42
        System.out.println("Second node data: " + firstNode.nextNode.data);      // 99
        System.out.println("End of chain:     " + firstNode.nextNode.nextNode);  // null
    }
}

// A complete, runnable singly linked list implementation in Java.
// We define the Node class and the LinkedList class together for simplicity.

public class SinglyLinkedList {

    // ── Inner Node class ──────────────────────────────────────────
    static class Node {
        int data;
        Node nextNode;

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

    // ── LinkedList class ──────────────────────────────────────────
    static class LinkedList {
        Node head; // The entry point to the entire list. Lose this, lose everything.

        // Constructor: start with an empty list (head is null = no nodes yet)
        LinkedList() {
            this.head = null;
        }

        // INSERT AT FRONT — O(1)
        // The new node jumps to the front and points to whoever WAS the head.
        void insertAtFront(int value) {
            Node newNode = new Node(value);
            newNode.nextNode = head; // New node now points to the old first node
            head = newNode;          // New node IS now the first node
        }

        // INSERT AT END — O(n)
        // We have to walk the whole list to find the last node, then attach.
        void insertAtEnd(int value) {
            Node newNode = new Node(value);

            // Edge case: if the list is empty, the new node becomes the head
            if (head == null) {
                head = newNode;
                return;
            }

            // Walk until we find the node whose nextNode is null (the last one)
            Node currentNode = head;
            while (currentNode.nextNode != null) {
                currentNode = currentNode.nextNode; // Move one step forward
            }

            // currentNode is now the last node. Attach the new node after it.
            currentNode.nextNode = newNode;
        }

        // DELETE BY VALUE — O(n)
        // Find the node with this value and "unlink" it from the chain.
        void deleteByValue(int value) {
            // Edge case: list is empty — nothing to delete
            if (head == null) {
                System.out.println("List is empty. Nothing to delete.");
                return;
            }

            // Special case: the node to delete IS the head
            if (head.data == value) {
                head = head.nextNode; // Head now points to the second node (old head is gone)
                return;
            }

            // Walk the list, keeping track of the PREVIOUS node
            // because we need to rewire its nextNode pointer
            Node previousNode = head;
            Node currentNode = head.nextNode;

            while (currentNode != null) {
                if (currentNode.data == value) {
                    // Found it! Skip over currentNode by connecting previousNode to currentNode's next
                    previousNode.nextNode = currentNode.nextNode;
                    System.out.println("Deleted node with value: " + value);
                    return;
                }
                // Not found yet — move both pointers one step forward
                previousNode = currentNode;
                currentNode = currentNode.nextNode;
            }

            System.out.println("Value " + value + " not found in the list.");
        }

        // TRAVERSE (PRINT) — O(n)
        // Walk from head to tail, printing each node's data.
        void printList() {
            if (head == null) {
                System.out.println("[ Empty List ]");
                return;
            }

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

            while (currentNode != null) {
                listVisual.append(currentNode.data);
                if (currentNode.nextNode != null) {
                    listVisual.append(" -> "); // Arrow shows the pointer relationship
                }
                currentNode = currentNode.nextNode;
            }

            listVisual.append(" -> null"); // null marks the end of the chain
            System.out.println(listVisual);
        }
    }

    // ── Main method — put it all together ─────────────────────────
    public static void main(String[] args) {
        LinkedList myList = new LinkedList();

        System.out.println("=== Building the list ===");
        myList.insertAtEnd(10);
        myList.insertAtEnd(20);
        myList.insertAtEnd(30);
        myList.printList(); // 10 -> 20 -> 30 -> null

        System.out.println("\n=== Inserting 5 at the front ===");
        myList.insertAtFront(5);
        myList.printList(); // 5 -> 10 -> 20 -> 30 -> null

        System.out.println("\n=== Deleting node with value 20 ===");
        myList.deleteByValue(20);
        myList.printList(); // 5 -> 10 -> 30 -> null

        System.out.println("\n=== Trying to delete a value that doesn't exist ===");
        myList.deleteByValue(99);

        System.out.println("\n=== Deleting the head node (value 5) ===");
        myList.deleteByValue(5);
        myList.printList(); // 10 -> 30 -> null
    }
}

// This demo shows WHY inserting at the front of a linked list
// is dramatically faster than inserting at the front of an array.
// We time both operations with 100,000 insertions to make the
// difference visible.

import java.util.LinkedList;  // Java's built-in linked list
import java.util.ArrayList;   // Java's built-in dynamic array

public class LinkedListVsArray {

    public static void main(String[] args) {
        int insertionCount = 100_000; // Insert 100,000 elements at the front

        // ── Test 1: ArrayList (array-backed) front insertion ──────
        ArrayList<Integer> arrayList = new ArrayList<>();
        long arrayStartTime = System.nanoTime();

        for (int i = 0; i < insertionCount; i++) {
            // Index 0 = insert at front. Every existing element shifts right.
            // This is O(n) per insertion — very expensive for large lists.
            arrayList.add(0, i);
        }

        long arrayEndTime = System.nanoTime();
        long arrayDurationMs = (arrayEndTime - arrayStartTime) / 1_000_000;

        // ── Test 2: LinkedList front insertion ────────────────────
        LinkedList<Integer> linkedList = new LinkedList<>();
        long linkedStartTime = System.nanoTime();

        for (int i = 0; i < insertionCount; i++) {
            // addFirst() just rewires a pointer. No shifting. O(1) every time.
            linkedList.addFirst(i);
        }

        long linkedEndTime = System.nanoTime();
        long linkedDurationMs = (linkedEndTime - linkedStartTime) / 1_000_000;

        // ── Results ───────────────────────────────────────────────
        System.out.println("Inserting " + insertionCount + " elements at the FRONT:");
        System.out.println("  ArrayList (array):   " + arrayDurationMs + " ms");
        System.out.println("  LinkedList:          " + linkedDurationMs + " ms");
        System.out.println();
        System.out.println("Random access — get element at index 50,000:");

        long arrayAccessStart = System.nanoTime();
        int arrayResult = arrayList.get(50_000); // Direct memory jump — O(1)
        long arrayAccessEnd = System.nanoTime();

        long linkedAccessStart = System.nanoTime();
        int linkedResult = linkedList.get(50_000); // Must hop 50,000 pointers — O(n)
        long linkedAccessEnd = System.nanoTime();

        System.out.println("  ArrayList get(50000):  " + (arrayAccessEnd - arrayAccessStart) + " ns  | value=" + arrayResult);
        System.out.println("  LinkedList get(50000): " + (linkedAccessEnd - linkedAccessStart) + " ns  | value=" + linkedResult);
        System.out.println();
        System.out.println("Conclusion: LinkedList wins at front insertion. ArrayList wins at random access.");
    }
}