Insert a node in a doubly linked list at a specific index

You're in the middle of a systems design round at Pivotal, and the interviewer pivots to a data structures warmup. "We have a doubly linked list," they say, sketching nodes with arrows going both ways. "I need you to insert a new node at a given index. Handle all the edge cases." This is the kind of problem that separates candidates who truly understand pointer manipulation from those who memorize patterns. Doubly linked lists add an extra layer of complexity over singly linked lists because every insertion requires updating pointers in both directions.

TL;DR

Insert a node into a doubly linked list at index i by using a sentinel (dummy) node to unify all edge cases. Create the sentinel pointing to head, traverse i positions with a previous pointer, then wire in the new node by setting its next and previous references and updating the surrounding nodes. This runs in O(n) time and O(1) space. The sentinel trick eliminates special-case logic for head insertion, making the code clean and less error-prone.

Why This Problem Matters

Doubly linked list insertion is a foundational operation that tests your ability to reason about bidirectional pointer manipulation. Unlike singly linked lists where you only worry about next pointers, doubly linked lists require you to keep both next and previous in sync. Get one wrong, and the list appears correct when traversed forward but breaks when traversed backward. This bidirectional thinking translates directly to real-world data structures like LRU caches, text editor buffers, and browser history navigation.

Doubly Linked Lists: A Quick Refresher

A doubly linked list is like a singly linked list with superpowers. Each node holds three things: the data, a reference to the next node, and a reference to the previous node. This means you can walk the list in either direction.

In our DoubleLinkListNode class, each node has:

• data: The value stored in the node
• previous: A reference to the node before this one
• next: A reference to the node after this one

The first node's previous is null, and the last node's next is null.

Understanding the Problem

Here is what we need to do:

Given: The head of a doubly linked list, an integer n, and an index i (zero-indexed) Task: Insert a new DoubleLinkListNode with data set to n at position i Return: The head of the modified list Edge case: If i exceeds the list length, append the node at the end

Consider the list [1, 2, 3]:

insertAtIndex(head, -1, 0)  ->  [-1, 1, 2, 3]
insertAtIndex(head, -1, 1)  ->  [1, -1, 2, 3]
insertAtIndex(head, -1, 3)  ->  [1, 2, 3, -1]

Inserting -1 at index 0 (before the head):

Inserting -1 at index 1 (middle of the list):

Inserting -1 at index 3 (end of the list):

Edge Cases to Consider

1. Empty list (null head): Create a new single-node list
2. Index 0: Insert before the current head
3. Index equals list length: Append at the end
4. Index exceeds list length: Also append at the end
5. Single-node list: Both head and tail insertion scenarios

Solution Approach

The tricky part of this problem is handling insertion at index 0. When you insert before the head, the head itself changes. You could write an if statement for this special case, but there is a cleaner way.

The Sentinel Node Trick

A sentinel node is a dummy node that sits before the actual head of the list. It does not hold meaningful data, but it gives us a consistent "previous node" for every position, including position 0.

With a sentinel, inserting at index 0 means inserting after the sentinel, which uses the exact same logic as inserting anywhere else in the list. At the end, we return sentinelNode.next as the new head, which correctly handles all cases.

Building the Algorithm

Let's walk through inserting -1 at index 2 in the list [1, 2, 3]:

Step 1: Create a sentinel node pointing to head. Initialize previous at the sentinel.

Step 2: Decrement i and advance previous to node 1. Now i = 1.

Step 3: Decrement i again and advance previous to node 2. Now i = 0, so we stop.

Step 4: Create the new node with previous set to node 2 and next set to node 3. Update node 2's next to point to the new node, and update node 3's previous to point to the new node.

The four pointer updates that happen during insertion:

1. newNode.previous = previous (new node points back to node 2)
2. newNode.next = previous.next (new node points forward to node 3)
3. previous.next = newNode (node 2 now points forward to new node)
4. newNode.next.previous = newNode (node 3 now points back to new node)

Implementation

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

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

    // Start traversal from the sentinel
    DoubleLinkListNode previous = sentinelNode;

    // Advance previous to the node just before the insertion point
    while (--i >= 0 && previous.next != null) {
      previous = previous.next;
    }

    // Create new node wired between previous and previous.next
    DoubleLinkListNode newNode =
      new DoubleLinkListNode(n, previous, previous.next);
    previous.next = newNode;

    // Update the backward pointer of the node after the new node
    if (newNode.next != null) {
      newNode.next.previous = newNode;
    }

    // Return the actual head (skip the sentinel)
    return sentinelNode.next;
  }
}

Let's trace through this with the list [1, 2, 3, 4, 5] and inserting -1 at index 3:

Iteration 1: --i makes i = 2. previous moves from sentinel to node 1. Iteration 2: --i makes i = 1. previous moves to node 2. Iteration 3: --i makes i = 0. previous moves to node 3. Loop ends because i is now negative.

We insert -1 after node 3:

Why --i Instead of i--?

The pre-decrement --i is deliberate. We want to stop previous at the node just before the insertion point. Since previous starts at the sentinel (one position before index 0), we need exactly i advances. Pre-decrementing checks the decremented value immediately, giving us the correct number of loop iterations.

Complexity Analysis

Time Complexity: O(n)

We traverse at most n nodes to reach the insertion point, where n is the smaller of the index and the list length. Each step does constant work. The actual insertion after traversal is O(1), involving just four pointer assignments.

Space Complexity: O(1)

We use a fixed number of extra variables: the sentinel node, the previous pointer, and the new node. None of these scale with input size.

Common Pitfalls

From reviewing hundreds of submissions on Firecode, these are the mistakes that trip people up most often:

1. Forgetting the backward pointer update: After inserting the new node, many candidates forget newNode.next.previous = newNode. The list looks correct going forward but is broken going backward.

2. Null pointer on backward update: If you insert at the end, newNode.next is null. Always check for null before updating newNode.next.previous.

3. Not returning the correct head: When inserting at index 0 without a sentinel, you must return the new node as the head. The sentinel approach sidesteps this entirely by always returning sentinelNode.next.

4. Off-by-one in traversal: Using i-- instead of --i (or vice versa) shifts the insertion position by one. Trace through a small example to verify.

Interview Tips

When tackling this problem in an interview:

1. Mention the sentinel approach early. It shows you know how to simplify edge cases, which is a sign of experience with linked list problems.

2. Draw the pointers. Sketch out the four pointer updates on the whiteboard. Interviewers love seeing candidates work through pointer manipulation visually.

3. Talk through the null checks. Explicitly mention that the node after the insertion point might be null (end-of-list case). This shows attention to detail.

4. Discuss the DoubleLinkListNode constructor. Clarify that it accepts (data, previous, next) so the new node is wired correctly at creation time, reducing the number of follow-up assignments.

5. Mention the trade-offs of doubly vs. singly linked lists: Extra memory per node (one more pointer) in exchange for O(1) backward traversal and easier deletion when you have a direct reference to the node.

Key Takeaways

• A sentinel (dummy) node eliminates special-case logic for head insertion, making doubly linked list operations cleaner and less error-prone.
• Doubly linked list insertion requires four pointer updates: the new node's next and previous, the preceding node's next, and the following node's previous. Missing any one of these breaks the list in one traversal direction.
• Pre-decrementing the index (--i) with a sentinel-based previous pointer naturally positions you at the correct insertion point after exactly i advances.
• When the index exceeds the list length, the traversal loop stops at the last node and the new node is appended at the end, which is the expected behavior per the problem constraints.
• Always check for null before updating newNode.next.previous to avoid null pointer exceptions when inserting at the tail.

Practice and Related Problems

Once you are comfortable with this insertion technique, try these related linked list problems to solidify your pointer manipulation skills:

• Insert a node at the head of a doubly linked list
• Remove duplicate nodes from a sorted linked list
• Reverse a linked list

Each of these builds on the same core skill: carefully updating pointers while keeping both directions of the list consistent.

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. Doubly linked list operations are a staple of coding interviews, and practicing them until the pointer updates feel automatic is one of the best investments you can make.

Solutions in Other Languages

Python

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

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

        new_node = DoubleLinkListNode(n, previous, previous.next)
        previous.next = new_node

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

        return sentinel_node.next

JavaScript

insertAtIndex(head, n, i) {
  const sentinelNode =
    new DoubleLinkListNode(Number.NEGATIVE_INFINITY, null, head);
  let previous = sentinelNode;

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

  const newNode = new DoubleLinkListNode(n, previous, previous.next);
  previous.next = newNode;

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

  return sentinelNode.next;
}

TypeScript

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

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

  const newNode = new DoubleLinkListNode(n, previous, previous.next);
  previous.next = newNode;

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

  return sentinelNode.next;
}

C++

DoubleLinkListNode *insertAtIndex(DoubleLinkListNode *head, int n, int i) {
  DoubleLinkListNode *sentinelNode = new DoubleLinkListNode(INT_MIN, nullptr, head);
  DoubleLinkListNode *previous = sentinelNode;

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

  previous->next = new DoubleLinkListNode(n, previous, previous->next);

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

  return sentinelNode->next;
}

Scala

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

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

  val newNode = DoubleLinkListNode(n, previous, previous.next)
  previous.next = newNode

  if (newNode.next != null) newNode.next.previous = newNode

  sentinelNode.next
}

Kotlin

fun insertAtIndex(head: DoubleLinkListNode?, n: Int, i: Int): DoubleLinkListNode? {
    val sentinelNode = DoubleLinkListNode(Int.MIN_VALUE, null, head)
    var previous = sentinelNode
    var index = i

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

    val newNode = DoubleLinkListNode(n, previous, previous.next)
    previous.next = newNode

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

    return sentinelNode.next
}

Swift

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

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

    let newNode = DoubleLinkListNode(n, previous, previous.next)
    previous.next = newNode

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

    return sentinelNode.next
}

Ruby

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

  while i >= 0 && !previous.next.nil?
    previous = previous.next
    i -= 1
  end

  new_node = DoubleLinkListNode.new(n, previous, previous.next)
  previous.next = new_node
  new_node.next.prev = new_node if !new_node.next.nil?

  sentinel_node.next
end

Rust

pub fn insert_at_index(&self, head: Option<Box<DoubleLinkListNode>>, n: i32, i: 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 idx = i;

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

        let mut new_node = Box::new(DoubleLinkListNode::new(n));
        new_node.previous = previous;
        new_node.next = (*previous).next.take();
        (*previous).next = Some(new_node);

        if let Some(ref mut next_node) = (*previous).next.as_mut().unwrap().next {
            next_node.previous = (*previous).next.as_mut().unwrap().as_mut() as *mut DoubleLinkListNode;
        }
    }

    sentinel.next
}

Dart

DoubleLinkListNode? insertAtIndex(DoubleLinkListNode? head, int n, int i) {
  DoubleLinkListNode sentinelNode = DoubleLinkListNode(0, null, head);
  DoubleLinkListNode previous = sentinelNode;

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

  DoubleLinkListNode newNode = DoubleLinkListNode(n, previous, previous.next);
  previous.next = newNode;

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

  return sentinelNode.next;
}

C#

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

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

    var newNode = new DoubleLinkListNode(n, previous, previous.next);
    previous.next = newNode;

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

    return sentinelNode.next;
}

PHP

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

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

    $newNode = new DoubleLinkListNode($n, $previous, $previous->next);
    $previous->next = $newNode;

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

    return $sentinelNode->next;
}