Delete the nth node of a doubly linked list

You're working through a mock interview at Oracle when the interviewer hands you a marker and says, "Draw me a doubly linked list. Now delete the fourth node." You reach for the eraser, but she stops you. "Not just the value. Show me how the pointers change." This problem, sometimes known as "Delete Node in a Doubly Linked List" on other platforms, tests whether you genuinely understand bidirectional pointer manipulation, not just forward-only linked list traversal.

TL;DR

Use a sentinel (dummy) node before the head to unify edge cases, then traverse to the node just before the target. Unlink the target by adjusting both the next pointer of the preceding node and the previous pointer of the following node. This runs in O(n) time and O(1) space. The sentinel trick eliminates the need for separate head-deletion logic, keeping the code clean and interview-friendly.

Why This Problem Matters

Doubly linked lists appear in real systems more often than most engineers realize. LRU caches, text editor undo buffers, and browser history all rely on O(1) deletion from doubly linked lists. This problem forces you to handle both next and previous pointers correctly, and the sentinel node pattern it teaches carries over to dozens of other linked list problems. If you can delete a node cleanly here, you have the building blocks for LRU cache design questions.

Doubly Linked Lists: A Quick Refresher

A doubly linked list extends the singly linked list by giving each node a pointer back to its predecessor. Every node holds three things: its data, a reference to the next node, and a reference to the previous node.

Compared to singly linked lists:

• Bidirectional traversal: You can walk forward or backward through the list
• Easier deletion: Given a reference to a node, you can remove it without needing to find its predecessor first
• More pointers to maintain: Every insertion or deletion must update both next and previous

The tradeoff is straightforward: doubly linked lists use more memory per node (one extra pointer), but they make certain operations simpler.

Understanding the Problem

Let's pin down exactly what we need to do:

Given: The head node of a doubly linked list and an integer n Task: Delete the node at index n (zero-indexed, so the head is at n = 0) Return: The head of the modified list Constraints: If n is out of bounds, return the list unchanged. Use O(1) space.

Here's the example from the problem. Starting with [1, 2, 3, 4, 5] and n = 3:

After deleting the node at index 3 (value 4):

Node 3's next now points to node 5, and node 5's previous now points back to node 3. The node with value 4 is completely unlinked from the list.

Edge Cases to Consider

1. Empty list (null head): Return null immediately
2. Single node, n = 0: Delete the only node, return null
3. Deleting the head (n = 0): The second node becomes the new head
4. Deleting the tail: The second-to-last node becomes the new tail
5. n out of bounds: Return the list unchanged

Solution Approach

The core challenge is handling the head deletion case without writing a bunch of conditional branches. If you delete a middle node, you adjust the predecessor's next and the successor's previous. But if you delete the head, there is no predecessor, and the return value changes. That's two different code paths for what should be one operation.

The Sentinel Node Pattern

A sentinel node solves this elegantly. You create a dummy node that sits before the real head:

Now every real node has a predecessor, including the head. The sentinel's next points to the head, and the head's previous points to the sentinel. When you're done, you return sentinel.next as the new head. This works whether the head was deleted or not.

Prefer a different language? Jump to solutions in other languages.

Walking Through the Algorithm

Let's trace through deleting index 3 from [1, 2, 3, 4, 5]:

Setup: Create sentinel, set previous = sentinel

Iteration 1 (n = 3, decrement to 2): Advance previous to node 1

Iteration 2 (n = 2, decrement to 1): Advance previous to node 2

Iteration 3 (n = 1, decrement to 0): Advance previous to node 3

Now previous sits at node 3, and previous.next is node 4, the target to delete. We unlink it:

1. Set previous.next = previous.next.next (node 3's next becomes node 5)
2. Set previous.next.previous = previous (node 5's previous becomes node 3)

Return sentinel.next, which is still node 1.

Deleting the Head

When n = 0, the loop body never executes. previous stays at the sentinel. Then previous.next is the head itself, so the head gets unlinked. sentinel.next becomes the second node, which is exactly the new head.

After deleting at index 0:

No special-case code needed. The sentinel handles it.

Implementation

Here's the full solution with the sentinel node approach:

public class Solution {
  public DoubleLinkListNode deleteAtIndex(DoubleLinkListNode head, int n) {
    // Create a sentinel node pointing to the head
    DoubleLinkListNode sentinelNode =
      new DoubleLinkListNode(Integer.MIN_VALUE, null, head);

    // Traverse to the node just before the target
    DoubleLinkListNode previous = sentinelNode;
    while (--n >= 0 && previous.next != null) {
      previous = previous.next;
    }

    // Unlink the target node if it exists
    if (previous.next != null) {
      previous.next = previous.next.next;

      // Update the previous pointer of the node after the deleted one
      if (previous.next != null) {
        previous.next.previous = previous;
      }
    }

    // Return the new head via the sentinel
    return sentinelNode.next;
  }
}

Let's break down the key decisions:

The --n pre-decrement trick: By decrementing n before the comparison, the loop runs exactly n times, landing previous one node before the target. This is a compact pattern you'll see in many linked list solutions.

Two null checks after unlinking: After setting previous.next = previous.next.next, the new previous.next might be null (if we deleted the tail). The inner null check prevents a NullPointerException when updating the previous pointer.

Returning sentinelNode.next: Whether we deleted the head or any other node, sentinelNode.next always points to the correct new head.

Complexity Analysis

Time Complexity: O(n)

We traverse at most n nodes to reach the target position. Each step does constant work (one pointer comparison, one pointer advance). The unlinking itself is O(1) since it's just pointer reassignment.

Space Complexity: O(1)

We allocate one sentinel node and one previous pointer. No matter how long the list is, we use the same fixed amount of extra space. This meets the problem's constant space requirement.

Why Not a Recursive Solution?

A recursive approach would work, but it uses O(n) stack space. Since the problem specifically asks for constant space, the iterative approach with a sentinel node is the right call. Mentioning this tradeoff in an interview shows solid engineering judgment.

Common Pitfalls

Here are the mistakes I see most often with this problem:

1. Forgetting the previous pointer update: This is the big one. After previous.next = previous.next.next, many candidates forget to also set previous.next.previous = previous. The list looks correct going forward, but backward traversal breaks.

2. Null pointer on the last node: When deleting the tail, previous.next.next is null. Setting previous.next = null is fine, but then trying to access previous.next.previous crashes. Always guard with a null check.

3. Off-by-one in traversal: Using n-- (post-decrement) instead of --n (pre-decrement) shifts the landing position by one. Trace through with n = 0 to verify your loop is correct.

4. Special-casing head deletion unnecessarily: The sentinel pattern eliminates the need for if (n == 0) { head = head.next; ... }. If you find yourself writing separate head logic, reconsider your approach.

Interview Tips

When solving this problem in an interview:

1. Clarify the interface: Ask what methods DoubleLinkListNode exposes. Confirm zero-based indexing. Ask what to return for an empty list.

2. Mention the sentinel pattern early: Saying "I'll use a sentinel node to handle edge cases uniformly" signals experience. Interviewers love hearing you think about clean abstractions.

3. Draw the pointer updates: Sketch three nodes. Show the next pointer change and the previous pointer change as two separate steps. This makes your logic visible and easy to verify.

4. Trace through edge cases on the board: Run through n = 0 (head deletion) and n = last index (tail deletion) to demonstrate correctness.

5. Mention the broader pattern: "This sentinel approach also works for singly linked list deletion, insertion, and is the same pattern used in LRU cache design." This connects the dots for your interviewer.

Key Takeaways

• The sentinel node pattern eliminates special-case branches for head deletion, making linked list code shorter and less error-prone.
• Doubly linked list deletion requires updating two pointers: the next of the predecessor and the previous of the successor. Missing either one breaks traversal in one direction.
• The --n pre-decrement loop is a compact way to land one node before the target, avoiding a separate counter variable.
• Always guard the previous pointer update with a null check, since deleting the tail node leaves previous.next as null.
• This O(n) time, O(1) space iterative solution is preferred over recursion when constant space is required.

Related Problems and Practice

Once you're comfortable with this deletion pattern, try these related problems to solidify your doubly linked list skills:

• Insert a node in a doubly linked list at a specific index
• Reverse a doubly linked list
• Design an LRU cache (uses doubly linked list deletion as a building block)
• Delete the nth node from the end of a linked list (requires the two-pointer gap technique)

Consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or preparing for your dream job, mastering fundamentals like doubly linked list manipulation will set you up for success.

Solutions in Other Languages

Python

class Solution:
    def delete_at_index(self, head, n):
        sentinel_node = DoubleLinkListNode(-1, None, head)
        previous = sentinel_node

        while n > 0 and previous.next is not None:
            previous = previous.next
            n -= 1

        if previous.next is not None:
            previous.next = previous.next.next
            if previous.next is not None:
                previous.next.previous = previous

        return sentinel_node.next

JavaScript

class Solution {
  deleteAtIndex(head, n) {
    const sentinelNode =
      new DoubleLinkListNode(Number.NEGATIVE_INFINITY, null, head);
    let previous = sentinelNode;

    while (--n >= 0 && previous.next !== null) {
      previous = previous.next;
    }

    if (previous.next !== null) {
      previous.next = previous.next.next;
      if (previous.next !== null) {
        previous.next.previous = previous;
      }
    }

    return sentinelNode.next;
  }
}

TypeScript

class Solution {
    deleteAtIndex(head: DoubleLinkListNode | null, n: number): DoubleLinkListNode | null {
        const sentinelNode = new DoubleLinkListNode(Number.NEGATIVE_INFINITY, null, head);
        let previous: DoubleLinkListNode = sentinelNode;

        while (--n >= 0 && previous.next !== null) {
            previous = previous.next;
        }

        if (previous.next !== null) {
            previous.next = previous.next.next;
            if (previous.next !== null) {
                previous.next.prev = previous;
            }
        }

        return sentinelNode.next;
    }
}

C++

DoubleLinkListNode *deleteAtIndex(DoubleLinkListNode *head, int n) {
    DoubleLinkListNode sentinelNode(INT_MIN, nullptr, head);
    DoubleLinkListNode *previous = &sentinelNode;

    while (--n >= 0 && previous->next != nullptr) {
        previous = previous->next;
    }

    if (previous->next != nullptr) {
        previous->next = previous->next->next;
        if (previous->next != nullptr) {
            previous->next->previous = previous;
        }
    }

    return sentinelNode.next;
}

Note that in C++, the sentinel node is allocated on the stack rather than the heap, avoiding manual memory management.

Go

func (s *Solution) DeleteAtIndex(head *DoubleLinkListNode, n int) *DoubleLinkListNode {
    sentinelNode := &DoubleLinkListNode{Data: -1, Previous: nil, Next: head}
    previous := sentinelNode

    for n > 0 && previous.Next != nil {
        n--
        previous = previous.Next
    }

    if previous.Next != nil {
        previous.Next = previous.Next.Next
        if previous.Next != nil {
            previous.Next.Previous = previous
        }
    }

    return sentinelNode.Next
}

Scala

def deleteAtIndex(head: DoubleLinkListNode, n: Int): DoubleLinkListNode = {
    val sentinelNode = DoubleLinkListNode(Integer.MIN_VALUE, null, head)
    var previous = sentinelNode
    var counter = n

    while (counter > 0 && previous.next != null) {
        previous = previous.next
        counter -= 1
    }

    if (previous.next != null) {
        previous.next = previous.next.next
        if (previous.next != null) previous.next.previous = previous
    }

    sentinelNode.next
}

Kotlin

fun deleteAtIndex(head: DoubleLinkListNode?, n: Int): DoubleLinkListNode? {
    val sentinelNode = DoubleLinkListNode(Int.MIN_VALUE, null, head)
    var previous = sentinelNode
    var nVar = n

    while (--nVar >= 0 && previous.next != null) {
        previous = previous.next!!
    }

    if (previous.next != null) {
        previous.next = previous.next?.next
        if (previous.next != null) {
            previous.next?.prev = previous
        }
    }

    return sentinelNode.next
}

Swift

func deleteAtIndex(_ head: DoubleLinkListNode?, _ n: Int) -> DoubleLinkListNode? {
    let sentinelNode = DoubleLinkListNode(Int.min, nil, head)
    var previous: DoubleLinkListNode = sentinelNode
    var n = n

    while n > 0 && previous.next != nil {
        n -= 1
        previous = previous.next!
    }

    if previous.next != nil {
        previous.next = previous.next!.next
        if previous.next != nil {
            previous.next!.previous = previous
        }
    }

    return sentinelNode.next
}

Ruby

def delete_at_index(head, n)
    sentinel_node = DoubleLinkListNode.new(-Float::INFINITY, nil, head)
    previous = sentinel_node

    while (n -= 1) >= 0 && !previous.next.nil?
        previous = previous.next
    end

    if previous.next
        previous.next = previous.next.next
        previous.next.prev = previous if previous.next
    end

    sentinel_node.next
end

Rust

Rust's ownership model makes doubly linked list manipulation more involved. The solution uses raw pointers for the traversal to mirror the pointer-based approach from other languages:

pub fn delete_at_index(&self, head: Option<Box<DoubleLinkListNode>>, n: i32) -> Option<Box<DoubleLinkListNode>> {
    let mut sentinel = Box::new(DoubleLinkListNode::new(i32::MIN));
    sentinel.next = head;
    let mut previous: *mut DoubleLinkListNode = &mut *sentinel;
    let mut count = n;

    while count > 0 && unsafe { (*previous).next.is_some() } {
        previous = unsafe { (*previous).next.as_mut().unwrap().as_mut() };
        count -= 1;
    }

    unsafe {
        if (*previous).next.is_some() {
            (*previous).next = (*previous).next.as_mut().unwrap().next.take();
            if (*previous).next.is_some() {
                (*previous).next.as_mut().unwrap().previous = previous;
            }
        }
    }

    sentinel.next
}

C#

public DoubleLinkListNode? deleteAtIndex(DoubleLinkListNode? head, int n) {
    var sentinelNode = new DoubleLinkListNode(int.MinValue, null, head);
    DoubleLinkListNode previous = sentinelNode;

    while (--n >= 0 && previous.next != null) {
        previous = previous.next;
    }

    if (previous.next != null) {
        previous.next = previous.next.next;
        if (previous.next != null) {
            previous.next.previous = previous;
        }
    }

    return sentinelNode.next;
}

Dart

DoubleLinkListNode? deleteAtIndex(DoubleLinkListNode? head, int n) {
    DoubleLinkListNode sentinelNode =
        DoubleLinkListNode(-1 << 31, null, head);
    DoubleLinkListNode previous = sentinelNode;

    while (--n >= 0 && previous.next != null) {
        previous = previous.next!;
    }

    if (previous.next != null) {
        previous.next = previous.next!.next;
        if (previous.next != null) {
            previous.next!.previous = previous;
        }
    }

    return sentinelNode.next;
}

PHP

public function deleteAtIndex(?DoubleLinkListNode $head, int $n): ?DoubleLinkListNode {
    $sentinelNode = new DoubleLinkListNode(PHP_INT_MIN, null, $head);
    $previous = $sentinelNode;

    while (--$n >= 0 && $previous->next !== null) {
        $previous = $previous->next;
    }

    if ($previous->next !== null) {
        $previous->next = $previous->next->next;
        if ($previous->next !== null) {
            $previous->next->previous = $previous;
        }
    }

    return $sentinelNode->next;
}