Algorithms from zero

Pointer manipulation on linked lists

Crux Insert a node into a linked list, delete a node, and reverse the list using pointer updates. Learn the dummy-head (sentinel) pattern to eliminate edge cases and write cleaner code.

◷ 22 min

Last lesson you learned that pushing to the head is O(1), but accessing position i is O(n). Today you will learn how to insert and delete at arbitrary positions, how to reverse a list, and how to use a clever trick—the dummy head—that eliminates most edge cases and makes your code simpler.

Goal

After this lesson you can insert a node at a given position in a linked list by updating pointers, delete a node from a linked list (given a reference to the previous node), reverse an entire linked list by pointer manipulation alone, implement the dummy-head (sentinel) pattern to handle head edge cases elegantly, and recognize when dummy heads make code cleaner and safer.

The idea

The core problem: linking and unlinking

To insert or delete a node in a linked list, you must carefully update pointers. It is not about creating or destroying nodes in memory (that is the allocator’s job); it is about changing where next points.

Insertion: the splice operation

Imagine a linked list [10] → [20] → [30] and you want to insert 15 between 10 and 20.

To insert a node after a given node:

Create the new node (15).
Set the new node’s next to point to the old successor (20).
Set the given node’s next to point to the new node (15).

This is a “splice”—you break the link from 10 → 20, insert 15 in between, and rebuild the chain: 10 → 15 → 20.

Before:  [10 | next → ] → [20 | next → ] → [30 | null]

After:   [10 | next → ] → [15 | next → ] → [20 | next → ] → [30 | null]
                            ↑ newly inserted

The operation is O(1) in time because you only change pointers; you do not traverse the list. But you must have a reference to the node before the insertion point. If you want to insert at position i (and you only have the head), you first traverse to position i-1, costing O(i) time total.

Deletion: the unlinking operation

Now delete the 15 from [10] → [15] → [20] → [30].

To delete a node, you need a reference to the node before it. Then:

Set the previous node’s next to skip the target, pointing directly to the target’s successor.

Before:  [10 | next → ] → [15 | next → ] → [20 | next → ] → [30 | null]

After:   [10 | next → ] ─────────────────> [20 | next → ] → [30 | null]
                        (15 is now unreachable)

Time: O(1) to delete given a reference to the previous node. O(i) if you must traverse to find it first.

The head edge case: why dummy heads matter

Insertion and deletion are easy if the target is in the middle. But what if you want to insert at the head or delete the head? Then there is no “previous node.” This forces you to write special cases:

if (insertingAtHead) {
  // Special case: create new head
  const newNode = new Node(value);
  newNode.next = head;
  head = newNode;
} else {
  // Normal case: insert after some node
  const prev = findNodeBefore(position);
  const newNode = new Node(value);
  newNode.next = prev.next;
  prev.next = newNode;
}

This duplication is ugly. The trick: introduce a dummy node.

The dummy head (sentinel node) pattern

Create a special node, the dummy head, that always points to the real head. This dummy is not part of your data; it is just an anchor.

Dummy (0) → [10 | next → ] → [20 | next → ] → [30 | null]
   ↑
 Always exists; acts as the previous node for insertions at the real head

Now every operation has a “previous node”—either a real node or the dummy. Insert and delete use the same logic everywhere:

// No special cases needed
const newNode = new Node(value);
newNode.next = prev.next;  // prev might be the dummy
prev.next = newNode;

Benefits:

Unified code. One insertion/deletion logic works for head and middle.
Cleaner deletions. Even if you delete the head, the dummy still points to the new head.
Safer. You eliminate null-pointer checks for “is there a previous node?”
Easier to code correctly. Fewer edge cases = fewer bugs.

Reversal: flipping all pointers

Reversing [10] → [20] → [30] → [null] to [30] → [20] → [10] → [null] means changing every next pointer to point backward.

One approach: iterate through the list, and at each node, reverse its pointer.

Step 0: prev = null,  current = 10 → 20 → 30
        next = 20 (save it before we change current.next)
        
Step 1: prev = 10 ← null (we flipped it),  current = 20 → 30
        next = 30 (save it)
        
Step 2: prev = 20 ← 10,  current = 30 → null
        next = null (save it)
        
Step 3: prev = 30 ← 20,  current = null (done)

Result: prev points to the new head (30).

The key insight: save the next pointer before you overwrite it. Otherwise, you lose the link and cannot continue.

let prev = null;
let current = head;

while (current !== null) {
  const next = current.next;  // Save the next node
  current.next = prev;        // Reverse the pointer
  prev = current;             // Move forward
  current = next;
}

head = prev;  // New head is the last node we processed

Time: O(n) (one pass through the list). Space: O(1) (only a few pointers, no new data).

The code

Insertion after a node:

function insertAfter(prevNode, value) {
  if (prevNode === null) {
    throw new Error("Cannot insert after null");
  }
  const newNode = new Node(value);
  newNode.next = prevNode.next;
  prevNode.next = newNode;
}

Deletion of a node (given the previous node):

function deleteAfter(prevNode) {
  if (prevNode === null || prevNode.next === null) {
    throw new Error("Nothing to delete");
  }
  prevNode.next = prevNode.next.next;
}

Reversal (in-place):

function reverseList(head) {
  let prev = null;
  let current = head;
  
  while (current !== null) {
    const next = current.next;  // Save next before we change it
    current.next = prev;        // Reverse the pointer
    prev = current;             // Move prev forward
    current = next;             // Move current forward
  }
  
  return prev;  // prev is now the new head
}

The dummy-head pattern:

function insertDummy(head, position, value) {
  // Create dummy node that points to head
  const dummy = new Node(0);  // Value doesn't matter
  dummy.next = head;
  
  // Traverse to position - 1 (now we can always find a previous node)
  let prev = dummy;
  for (let i = 0; i < position; i++) {
    if (prev.next === null) {
      throw new Error("Position out of bounds");
    }
    prev = prev.next;
  }
  
  // Insert (same logic as always)
  const newNode = new Node(value);
  newNode.next = prev.next;
  prev.next = newNode;
  
  return dummy.next;  // Return the new head
}

Try reversing a list and using the dummy head:

class Node {
constructor(value, next = null) {
  this.value = value;
  this.next = next;
}
}

function reverseList(head) {
let prev = null;
let current = head;

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

return prev;
}

function traverse(head) {
const values = [];
let current = head;
while (current !== null) {
  values.push(current.value);
  current = current.next;
}
return values;
}

function insertDummy(head, position, value) {
const dummy = new Node(0);
dummy.next = head;

let prev = dummy;
for (let i = 0; i < position; i++) {
  if (prev.next === null) return null;
  prev = prev.next;
}

const newNode = new Node(value);
newNode.next = prev.next;
prev.next = newNode;

return dummy.next;
}

// Build: [10, 20, 30]
let head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);

console.log("Original:", traverse(head));

// Reverse
head = reverseList(head);
console.log("Reversed:", traverse(head));

// Insert 5 at position 1 in reversed list [30, 20, 10]
head = insertDummy(head, 1, 5);
console.log("After insert 5 at pos 1:", traverse(head));

Output

Step-by-step trace

Let us trace the reversal of [10] → [20] → [30] step by step.


      1
      let prev = null;
    

      2
      let current = head;
    

      3
      while (current !== null) {
    

      4
        const next = current.next;
    

      5
        current.next = prev;
    

      6
        prev = current;
    

      7
        current = next;
    

      8
      }

Notice: we never allocate or free nodes. We only change pointers. The list structure is completely reversed by pointer updates alone.

Complexity

Pointer manipulation on linked lists:

Operation	Time	Space
Insert after a given node	O(1)	O(1)
Insert at position i	O(i)	O(1)
Delete after a given node	O(1)	O(1)
Delete at position i	O(i)	O(1)
Reverse the entire list	O(n)	O(1)

Why O(1) for insert/delete after a node? You only update pointers; no traversal needed.

Why O(i) for insert/delete at position i? You must traverse from head to position i (or i-1) to find the target. Traversal takes O(i) time.

Why O(n) for reversal? You visit each node once and flip its pointer. One pass through all n nodes.

Why O(1) space for all? You use only a few pointers (prev, current, next). No new data structure is allocated.

Practice 0 / 5

You want to insert a node with value 15 after the node with value 10 in the list [10] → [20] → [30]. What are the pointer updates?

To delete the node with value 20 from [10] → [20] → [30], what do you do?

After reversing [10] → [20] → [30], the new head and the final structure should be:

What is the time complexity of reversing a linked list with n nodes?

Why is the dummy-head pattern useful?

Edge cases

Insertion at the head with dummy: With a dummy head, insertion at position 0 (the real head) is just insertion after the dummy. No special case needed. The new node becomes the first real data node, and dummy.next points to it.

Common mistake

“I can delete a node by just setting node.next = null.” No. This does not unlink the node from the list. The previous node still points to it, and the node still points to its successor. True deletion requires changing the previous node’s next pointer.

Common mistake

“When reversing, I can just use recursion to flip pointers.” Recursion works (and is elegant), but it costs O(n) space for the call stack. The iterative approach (with prev, current, next pointers) does it in O(1) space.

Check yourself

Quiz

Why is deletion of a node in a linked list O(1) only if you have a reference to the previous node, but O(n) if you only have the head?

Recap

Pointer manipulation on linked lists:

Insertion after a node: Create a new node, set its next to the old successor, set the node’s next to the new node. Time: O(1) if you have the node; O(i) if you must traverse to position i first.
Deletion after a node: Set the previous node’s next to skip the target and point to its successor. Time: O(1) given the previous node; O(n) if you must search from the head.
Reversal: Use three pointers (prev, current, next) to iterate through the list and flip each pointer. Time: O(n), space: O(1). The last node becomes the new head.
The dummy-head (sentinel) pattern: Place a dummy node before the real head. Now every operation has a guaranteed “previous node,” eliminating special cases for head operations. Cleaner code, fewer bugs.
Always save the next pointer before overwriting it. When you set current.next = prev, you lose the link to the successor unless you saved it first.
Pointer manipulation is all about updates, not allocation. You are rearranging existing nodes, not creating new ones.

Next, you will learn the stack and queue—two sequential data structures built on linked lists, each imposing a discipline on when you can insert and delete.

Continue the climb ↑Fast and slow pointers