Operations on Singly Linked List

A singly linked list works because each node stores a value plus one pointer to the next node, so any structural change — insert, delete, traverse — is done by rewiring a handful of next pointers rather than shifting a contiguous block of memory; the cost of an operation is dominated entirely by how many nodes you must walk to reach the rewiring point, not by how many nodes exist after it.

Recognize the pattern

• The problem talks about a sequence where elements are added/removed frequently at arbitrary positions, and random access (arr[i]) is not required.
• You see phrases like "insert before/after a given node", "remove the node with value X", or "reverse a list" — all pointer-rewiring tasks.
• The data structure is drawn as boxes connected by arrows in one direction only (no arrow back to the previous box) — that single-direction constraint is the tell that separates it from a doubly linked list.

Brute force vs optimal

Brute force (array-backed sequence): to insert or delete at position k in an array, every element after k must be shifted — O(n) data movement per operation, plus occasional O(n) resize copies.

Optimal (linked list): once you hold a reference to the node just before the target position, insertion/deletion is O(1) pointer updates — no data movement. The only O(n) cost left is the search to reach that position, which is unavoidable in a singly linked list because there is no random access.

So the real trade is: arrays pay O(n) to move data; linked lists pay O(n) to locate a spot, then O(1) to change it. When the position is already known (e.g., you're holding the predecessor node while scanning), the linked list wins outright.

Complexity, derived

Space is O(1) for every operation because we mutate pointers in place — the only extra memory is a fixed number of reference variables (current, prev), independent of n. This is the recurrence-free case: cost = (nodes visited to locate the target) × O(1) work per node. One caveat: reversing the list is Θ(n) time either way, but only the iterative version (three rolling references) is Θ(1) space — the recursive version unwinds T(n)=T(n−1)+O(1) across Θ(n) stack frames, so it is not an O(1)-space reverse.

Worked example

List: 10 -> 20 -> 30 -> NULL. Insert value 25 at position 2 (0-indexed, so it lands between 20 and 30).

Total links walked: 1 (to reach node 20). Total pointer writes: 2. Deleting 25 back out reverses the same two writes: prev.next = prev.next.next.

Code (Java)

import java.util.NoSuchElementException;

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

class SinglyLinkedList {
    Node head;

    void insertAt(int position, int value) {
        Node newNode = new Node(value);
        if (position == 0) {
            newNode.next = head;
            head = newNode;
            return;
        }
        Node prev = head;
        for (int i = 0; i < position - 1 && prev != null; i++) prev = prev.next;
        if (prev == null) throw new IndexOutOfBoundsException("invalid position");
        newNode.next = prev.next;
        prev.next = newNode;
    }

    void deleteAt(int position) {
        if (head == null) throw new NoSuchElementException("list is empty");
        if (position == 0) { head = head.next; return; }
        Node prev = head;
        for (int i = 0; i < position - 1 && prev.next != null; i++) prev = prev.next;
        if (prev.next == null) throw new IndexOutOfBoundsException("invalid position");
        prev.next = prev.next.next;
    }

    void traverse() {
        Node current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }
}

Pitfalls

• Losing the head: overwriting head before saving a reference to the old first node causes the entire list to leak/become unreachable.
• Off-by-one on the predecessor: inserting/deleting at position k needs the node at k-1, not k — a common bug is stopping one step too early or late.
• Null dereference at the tail: forgetting to check prev == null / prev.next == null before dereferencing when the position exceeds list length.
• Write-order bug on insert: you must set newNode.next = prev.next before prev.next = newNode — reversing the order overwrites the only reference to the rest of the list before newNode has captured it, silently truncating the list (see the diagram above).
• Dangling node.next after deletion: in garbage-collected languages this is harmless, but in manual-memory languages failing to free the removed node leaks memory; conversely, freeing it before rewiring prev.next causes a use-after-free.
• Forgetting to update a tail pointer (if maintained) after deleting the last node, leaving it stale.

When to use / when not

Use a singly linked list when insertions/deletions happen at the front or at a position you already hold a reference to (e.g., implementing a stack, or a queue with head+tail pointers), and you don't need backward traversal or random access.

vs. Doubly Linked List: a doubly linked list adds a prev pointer, enabling O(1) deletion given only a reference to the node itself (no need to re-scan for the predecessor) and O(1) traversal in both directions — at the cost of extra memory per node (one more pointer) and more pointer writes to keep consistent. Choose singly linked when memory is tight and you never need to walk backward or delete via a bare node reference; choose doubly linked (e.g., LRU cache implementations) when O(1) arbitrary deletion matters.

vs. Dynamic array (ArrayList): arrays give O(1) random access and better cache locality (contiguous memory) but O(n) shifting for mid-list insert/delete. Linked lists give O(1) structural edits at a known point but O(n) search and poor cache locality due to scattered allocations.

Takeaways

• Every linked-list operation's cost = (nodes traversed to reach the edit point) + O(1) pointer rewiring — there's no hidden data-shifting cost.
• Head operations are always O(1); anything else pays for the walk.
• Guard against null before dereferencing .next — that's the single most common bug source.
• Pick doubly linked lists over singly linked ones specifically when you need O(1) deletion from a bare node reference or backward traversal.

Recall: Why is deleting the last node of a singly linked list O(n) even though deleting the first node is O(1)?

Synthesized from standard DSA curricula (CLRS-style linked list treatment) and the source lesson's traversal/insertion/deletion algorithm walkthroughs.