Insert, delete and the dummy head

You need the node before

In a singly linked list, a node only knows the node after it. So to change what comes after a node, you need a pointer to that node, and to remove a node, you need a pointer to the node before it.

With that pointer in hand, both operations are constant time:

def insert_after(p, val):
    n = Node(val)
    n.next = p.next      # 1. the new node takes over p's successor
    p.next = n           # 2. p now leads to the new node
 
def delete_after(p):
    p.next = p.next.next # skip over the node after p

The order of the two writes in insert_after matters for the same reason as in the reversal: if p.next = n came first, the old successor would be lost before the new node could link to it. In a language without garbage collection, delete_after must also free the unlinked node, or it leaks.

The catch is in "with that pointer in hand". If you have to find the position first, by searching for a value or counting to an index, the search is O(n) and dominates. Linked lists are fast to rewire, not to find things in.

The head is a special case

The first node has no node before it. Removing it means changing head itself rather than some node's next, so naive code needs a branch for it, and another for an empty list, and the loop has to be careful when several matching nodes are adjacent, including at the start.

A dummy head, also called a sentinel, removes those branches. Before doing anything, create one extra node whose next is the real head. Now every real node, including the first, has a node before it, and a single loop with a prev pointer handles every position the same way. At the end, the real head is dummy.next, whatever happened to the original first node.

The trace above removes every 3 from 3 → 1 → 3 → 2. The first 3 is the head, but the loop removes it with the same line as the second one. Notice also that prev advances only past nodes that are kept. After an unlink, prev.next is a node nobody has checked yet, so the loop looks at it next. That rule is what makes adjacent matches work.

Dummy heads appear whenever code builds a new list, too. Merging two sorted lists, adding two numbers stored digit by digit, or partitioning a list around a value all start with dummy = Node(0) and a tail pointer that new nodes are attached to, so the first node needs no special handling either.

Doubly linked lists

A doubly linked node holds two pointers, prev and next. That costs another 8 bytes per node, and every insertion or deletion has to update both directions, but it buys something a singly linked list can't do: remove a node in O(1) given only a pointer to that node.

def unlink(node):
    node.prev.next = node.next
    node.next.prev = node.prev

Those two lines assume the node has neighbors on both sides. A circular doubly linked list with one sentinel node makes that always true: the sentinel's next is the first node and its prev is the last, and an empty list is just the sentinel pointing at itself. Every insertion and deletion becomes the same few lines, with no null checks at all. The Linux kernel's list_head, used for thousands of lists inside the kernel, works exactly this way.

The LRU cache

The classic use of a doubly linked list is a least recently used (LRU) cache: a fixed-size cache that, when full, evicts the entry used longest ago. Web browsers, databases and operating systems all use variants of it.

It needs three operations to be fast:

1. Look up a key. A hash map from key to node gives O(1) on average.
2. Mark an entry as just used. Keep entries in a doubly linked list ordered by last use. Unlink the node, which is O(1) because it is doubly linked, and reinsert it at the front, also O(1).
3. Evict the least recently used entry. It is at the back of the list, next to the sentinel: unlink it and delete its key from the map.

Neither structure could do this alone. A hash map has no order, and a list can't find a key without a search. Together, each operation is O(1). The practice problem LRU cache asks you to build it, and the interview question for this lesson asks you to explain it.

Copying and other pointer puzzles

Some list problems are really about bookkeeping between two sets of nodes. Copying a list in which each node also has a random pointer to any node is a good example: the copy's random pointers must lead to copy nodes, not originals. A hash map from each original node to its copy solves it in two passes. A trickier version interleaves each copy right after its original, so that original.random.next is the copy's target, and then separates the two lists, using O(1) extra memory. Both rely on the same habit as everything in this lesson: decide, before writing a pointer, what each node must point to when you are done.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Insert, delete and the dummy head from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function reverse_and_find_mid(head):
    slow = head; fast = head
    while fast != null and fast.next != null:
        slow = slow.next
        fast = fast.next.next
    prev = null; curr = slow
    while curr != null:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};
 
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr != nullptr) {
        ListNode* nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

public class LinkedListSolver {
    public static class ListNode {
        int val; ListNode next;
        ListNode(int v) { this.val = v; }
    }
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
}

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None) -> None:
        self.val = val
        self.next = next
 
def reverse_list(head: ListNode | None) -> ListNode | None:
    prev, curr = None, head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.