Singly Linked List — The Bug That Lost 8% of User Tabs

A singly linked list is a dynamic data structure where each element (node) stores a value and a pointer to the next node. Unlike arrays, nodes are not contiguous in memory — each node can be anywhere on the heap. This gives O(1) insertion and deletion at the head, but O(n) random access.

The structure solves the rigid-size problem of arrays. No pre-allocated block. No resizing overhead. Nodes are allocated on demand and linked via pointers. Deletion is a arrays.

The common misconception is that linked lists are always better than arrays. They are not. Linked lists have poor cache locality (nodes scattered on the heap), O(n) random access, and per-node pointer overhead. Use them when front insertion/deletion is frequent and random access is rare.

Singly Linked List — The Bug That Lost 8% of User Tabs

A singly linked list is a sequence of nodes where each node holds a value and a single pointer to the next node. The list is defined by its head — the first node. Traversal is strictly forward; there is no way to go back. This minimal structure gives O(1) insertion and deletion at the head, but O(n) random access and O(n) search. The tail node points to null, marking the end.

In practice, the key property is that inserting or removing an element at an arbitrary position requires first finding that position — an O(n) walk. This makes singly linked lists excellent for stacks (LIFO) and queues (FIFO with a tail pointer), where all operations happen at the ends. They are also the foundation for adjacency lists in graph algorithms and for implementing hash table buckets via separate chaining. However, they are a poor choice for indexed access or frequent middle-of-list modifications.

Real systems use singly linked lists when memory overhead per element must be low and the access pattern is strictly sequential. Java’s LinkedList is a doubly linked list, but the singly linked variant appears in low-level allocators, kernel task queues, and lock-free data structures where the single pointer simplifies atomic operations. Understanding the trade-off between pointer cost and traversal flexibility is what separates a correct design from a performance trap.

Worked Example — Tracing Insertion, Deletion, and Reversal

Build list: insert 1,2,3 at head → 3→2→1→None. Insert 4 at tail: traverse to tail (node 1), set node1.next = Node(4) → 3→2→1→4→None.

Delete node with value 2: 1. prev=None, curr=3. 3!=2, prev=3, curr=2. 2. 2==2: prev.next = curr.next = 1. Skip node 2. List: 3→1→4→None.

Reverse 3→1→4→None: 1. prev=None, curr=3. Save next=1. Set 3.next=None. prev=3, curr=1. 2. Save next=4. Set 1.next=3. prev=1, curr=4. 3. Save next=None. Set 4.next=1. prev=4, curr=None. 4. New head=prev=4. List: 4→1→3→None.

Find middle of 4→1→3→None: Slow=4, fast=4. Step 1: slow=1, fast=3. Step 2: fast.next=None, stop. Middle=slow=1 (second of three nodes).

How a Singly Linked List Works — Plain English and Operations

A singly linked list is a chain of nodes where each node stores a value and a pointer to the next node. The last node's next pointer is None. A head pointer tracks the first node.

Unlike an array, nodes are not contiguous in memory — each node can be anywhere on the heap. This means random access requires traversal (O(n)), but insertion and deletion at a known position are O(1) — just update pointers.

Key operations: 1. Insert at head (O(1)): new.next = head; head = new. 2. Insert at tail (O(n) without tail pointer; O(1) with): traverse to last, last.next = new. 3. Delete node with value v (O(n)): traverse until prev.next.val == v; prev.next = prev.next.next. 4. Search for value v (O(n)): traverse comparing each node's value.

Worked example — insert 1, then 2 at head, then delete 1: Insert 1: head -> [1] -> None. Insert 2 at head: head -> [2] -> [1] -> None. Delete 1: traverse — head.next.val=1. Set head.next = head.next.next = None. Result: head -> [2] -> None.

What a Node Actually Is — The Building Block of Everything

Before you can understand a linked list, you need to deeply understand a node — because the list IS just a collection of nodes.

Think of a node like a Post-it note stuck to a wall. The Post-it has two things written on it: the actual information you care about (say, a person's name) and an arrow pointing to the next Post-it on the wall. That arrow is the 'next pointer'. Without it, each Post-it is just a lonely, disconnected piece of paper.

In Java, a node is a small class with exactly two fields. First: the data it holds (could be a number, a name, anything). Second: a reference — Java's version of a pointer — to another node object. When that reference is null, you've hit the end of the list. Java uses null the same way the last clue in our treasure hunt says 'dead end'.

Here's the key insight that trips beginners up: the node doesn't know its own position. It has no idea it's node number 5. It only knows two things — its own data, and who comes next. That simplicity is what makes the whole structure so flexible.

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);
    }
}

Building a Singly Linked List — Insert, Traverse and Delete

Now that you understand a node, let's build an actual linked list. A singly linked list needs one thing to function: a reference to the very first node, called the 'head'. If you lose the head reference, you lose the entire list — like dropping the first clue in the treasure hunt and having no idea where to start.

The three operations you must master are: inserting a node (at the beginning, end, or middle), traversing the list (walking through it from head to tail), and deleting a node.

Inserting at the front is O(1) — lightning fast. You create a new node, point it at the current head, then make it the new head. Done. Inserting at the end is O(n) because you have to walk all the way to the last node first.

Deletion is where linked lists really shine compared to arrays. To remove a node, you just redirect the previous node's pointer to skip over the target node. The target becomes unreachable and Java's garbage collector cleans it up. No shifting of elements like in an array. No copy operations. Just a pointer redirect.

The code below builds a complete, working linked list with all three operations. Read the comments carefully — they tell the story of what's happening at each step.

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();
    }
}

Singly Linked List vs Array — When to Use Which

Understanding WHEN to use a singly linked list is just as important as knowing how to build one. The honest answer: arrays are often the better default choice, but linked lists win in specific scenarios.

Arrays store elements in contiguous memory, which means accessing element at index 7 is instant — O(1). The CPU can calculate the memory address directly. Linked lists can't do this. To reach node 7, you must start at the head and hop through 7 pointers one by one — O(n). If you're doing a lot of random access by index, an array will run circles around a linked list.

However, linked lists dominate when you're doing frequent insertions and deletions — especially at the front of the list. Adding to the front of an array means shifting every existing element one slot to the right — O(n). Adding to the front of a linked list is three lines of code and O(1). No shifting. No resizing.

The memory story is also interesting. Arrays can waste memory if you pre-allocate a large block and only use half of it. Linked lists only allocate exactly as much memory as they need — but each node pays a tax: it needs extra memory to store the 'next' pointer itself. For small data types like integers, that pointer overhead can actually be larger than the data you're storing.

Use a linked list when: insertion/deletion at the front is frequent, the list size is truly unpredictable, and you never need random index access.

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 + ")");
    }
}

Why Your Linked List Implementation Will Leak Memory

Every tutorial shows you how to build a linked list. None of them tell you how to tear it down. In garbage-collected languages like Java, you'd think you're safe. You're not.

The head node holds a reference chain to every subsequent node. If you drop the head reference, the GC can collect the chain — eventually. But what if your list holds file handles, network sockets, or database connections? Those resources don't wait for GC. They leak.

The pattern is brutal: you null out the head, but nodes keep references to each other. The GC sees a circular reference? No. But it sees a reachable island of objects until the next collection cycle. In high-throughput systems, that 'eventually' becomes 'during peak load.'

Here's the fix: iterate through the list, nullify each node's next reference, then release the head. For production code holding non-memory resources, implement AutoCloseable and call close() on each node. Don't trust the garbage collector to clean up your mess.

// io.thecodeforge — dsa tutorial

public class LinkedListCleaner {
    public static void destroyList(Node head) {
        Node current = head;
        while (current != null) {
            Node next = current.next;
            // Release any resource held by this node
            if (current.data instanceof AutoCloseable) {
                try {
                    ((AutoCloseable) current.data).close();
                } catch (Exception e) {
                    // Log and continue — don't block cleanup
                }
            }
            current.next = null; // Break the reference chain
            current = next;
        }
        head = null; // Final release
    }
}

// Usage example:
// Node head = buildListWithResources();
// destroyList(head);

The Hidden Complexity of Singly Linked List Reversal

Reversing a singly linked list is the interview question every junior memorizes. But the real problem isn't reversing — it's reversing under constraints. Production code doesn't give you the luxury of O(n) extra space or mutating the original list.

Let's talk about in-place reversal. The iterative approach uses three pointers: previous, current, and next. One mistake in pointer order and you get a null pointer exception or a cycle. The recursive version looks elegant but blows the stack for lists longer than a few thousand nodes — default JVM stack depth is around 10,000 frames. Good luck debugging that at 3 AM.

The senior move: always validate the input list length before choosing your approach. For lists under 1,000 nodes, recursion is readable and safe. For anything larger, use the iterative method and unit test the edge cases — single node, two nodes, and full list.

And never reverse a list you don't own. If the list is passed into your method, the caller expects it unchanged. Clone first, or return a new reversed list. That means O(n) space, but it's the contractually safe choice.

// io.thecodeforge — dsa tutorial

public class SafeReversal {
    
    // Iterative in-place reversal — safe for large lists
    public static Node reverseIterative(Node head) {
        Node prev = null;
        Node current = head;
        Node next;
        
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev; // new head
    }
    
    // Recursive — elegant but stack-sensitive
    public static Node reverseRecursive(Node node) {
        if (node == null || node.next == null) {
            return node;
        }
        Node newHead = reverseRecursive(node.next);
        node.next.next = node;
        node.next = null;
        return newHead;
    }
    
    // Test with a 5-node list
    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);
        head.next.next.next.next = new Node(5);
        
        Node reversed = reverseIterative(head);
        // Output: 5 -> 4 -> 3 -> 2 -> 1 -> null
        printList(reversed);
    }
    
    private static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

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

The Real Disadvantage: Random Access Is a Myth

Arrays give you O(1) lookup by index. Linked lists give you nothing but a pointer to the first node. Want element at position 5? You walk 5 steps. Every. Single. Time.

This isn't a theoretical nitpick — it's a production disaster waiting to happen. I've seen teams replace arrays with linked lists for "flexibility" and then wonder why their pagination endpoint takes 2 seconds. Because every next_page call traversed the entire list up to that point.

The WHY is simple: nodes only know their next neighbor. There's no address calculation, no memory block to jump to. You pay for every element you skip. In a 10,000-node list, element 9,999 costs 9,999 pointer chases. Cache misses multiply the pain.

Before you reach for a linked list, ask: "Do I ever need the 5th element without walking through the first 4?" If yes, use an array or ArrayList. Linked lists are for sequential access, not your random-access fantasy.

// io.thecodeforge — dsa tutorial

public class NoRandomAccess {
    static class Node {
        int data;
        Node next;
        Node(int d) { data = d; }
    }

    static int getAtIndex(Node head, int index) {
        Node current = head;
        for (int i = 0; i < index; i++) {
            if (current == null) throw new IndexOutOfBoundsException();
            current = current.next;  // walk walk walk
        }
        return current.data;
    }

    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
        System.out.println(getAtIndex(head, 2)); // steps: 2
    }
}

Memory Bloat: Each Node Is a Hoarder

Every node in a singly linked list carries two things: your data and a pointer to the next node. That pointer is overhead — usually 8 bytes on a 64-bit JVM. For an int (4 bytes), you're wasting 200% extra memory just for the link. For small objects, the overhead can triple your memory footprint.

Why does this matter? Production servers have finite heap. A linked list of one million integers eats 12 MB for data plus 16 MB for node objects and pointers — 28 MB total. The same array fits in 4 MB. That 24 MB difference might crash your app under load when the GC starts fighting for space.

Worse: memory locality. Array elements sit adjacent in RAM, so CPU cache prefetches them. Linked list nodes are scattered across heap — every next pointer is a potential cache miss. Your list traversal becomes a memory-stall nightmare.

The rule: if you care about memory — and you should — linked lists are for when you need cheap insertions/deletions in the middle, not for memory efficiency. Arrays win on memory almost every time.

// io.thecodeforge — dsa tutorial

public class MemoryWaste {
    static class Node {
        int data;
        Node next;
        Node(int d) { data = d; }
    }

    public static void main(String[] args) {
        // 3 nodes: each has 4 bytes data + 8 bytes pointer + object header (12-16 bytes)
        // Total: ~72 bytes for 3 ints. Array: 12 bytes.
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        
        int[] arr = {1, 2, 3};  // 12 bytes, contiguous
        System.out.println("Linked list wins flexibility, loses RAM.");
    }
}