Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Inserting into a Doubly Linked List

EASYProblemSolveExternal Links

Description

You are given the head of a doubly linked list, a position p (0-based indexed), and an integer x.

Your task is to create a new node with value x and insert it just after the p-th node in the doubly linked list. Return the head of the updated list.

In a doubly linked list, each node has three components:

  • data — the value stored in the node
  • next — a pointer to the next node (or null if it's the last node)
  • prev — a pointer to the previous node (or null if it's the first node)

When inserting a new node, you must correctly update both the next and prev pointers of the surrounding nodes so that the doubly linked structure remains intact.

Examples

Example 1

Input: LinkedList = 2 <-> 4 <-> 5, p = 2, x = 6

Output: 2 <-> 4 <-> 5 <-> 6

Explanation: We need to insert a node with value 6 after the 2nd node (0-indexed). The 2nd node is the node with value 5. After insertion, the new node with value 6 becomes the last node. The list becomes 2 <-> 4 <-> 5 <-> 6.

Example 2

Input: LinkedList = 1 <-> 2 <-> 3 <-> 4, p = 0, x = 44

Output: 1 <-> 44 <-> 2 <-> 3 <-> 4

Explanation: We need to insert a node with value 44 after the 0th node (the head node with value 1). After insertion, the new node sits between the original head (1) and the second node (2). The new node's prev points to 1, and its next points to 2.

Example 3

Input: LinkedList = 10, p = 0, x = 20

Output: 10 <-> 20

Explanation: The list has only one node (value 10). We insert value 20 after the 0th node. The new node's prev points to 10, and its next is null (it becomes the tail). Node 10's next now points to the new node 20.

Constraints

  • 0 ≤ p < list size ≤ 10^4
  • 0 ≤ x, node->data ≤ 10^4
  • The position p is always valid (guaranteed to be within the list).

Editorial

Direct Traversal and Insertion

Intuition

Inserting a node into a doubly linked list at a given position is a fundamental linked list operation. Unlike arrays where insertion might require shifting elements, a linked list insertion only requires updating a few pointers — making it an O(1) operation once we've found the right position.

The challenge is in two parts:

  1. Navigate to the p-th node by walking through the list one node at a time.
  2. Insert the new node by carefully rewiring four pointers.

Think of a doubly linked list like a chain of people holding hands in a line. Each person holds the hand of the person in front (next) and behind (prev). To insert a new person after the 3rd person:

  • Walk along the line counting people until you reach the 3rd person.
  • The new person grabs the hand of the 3rd person with their left hand (prev pointer).
  • The new person grabs the hand of the 4th person with their right hand (next pointer).
  • The 3rd person releases their right hand from the 4th person and grabs the new person's hand instead.
  • The 4th person releases their left hand from the 3rd person and grabs the new person's hand instead.

The crucial detail in a doubly linked list is that you must update four pointers, not just two as in a singly linked list:

  • newNode.next = node after position p
  • newNode.prev = node at position p
  • nodeAtP.next = newNode
  • If the node after position p exists: nodeAfterP.prev = newNode

Step-by-Step Explanation

Let's trace through with LinkedList = 1 <-> 2 <-> 3 <-> 4, p = 0, x = 44:

Step 1: Create the new node with value 44. Its next and prev are initially null.

Step 2: Start at the head node (position 0, value 1). We need to reach position p=0. Since we're already at position 0, no traversal is needed.

Step 3: We've found the node at position p=0 (value 1). Let's call it curr. The node after curr is the node with value 2. Let's call it nextNode.

Step 4: Set newNode.next = nextNode (newNode(44).next → node(2)). The new node now points forward to node 2.

Step 5: Set newNode.prev = curr (newNode(44).prev → node(1)). The new node now points backward to node 1.

Step 6: Set curr.next = newNode (node(1).next → newNode(44)). Node 1 now points forward to the new node instead of node 2.

Step 7: Since nextNode exists (it's node 2, not null), set nextNode.prev = newNode (node(2).prev → newNode(44)). Node 2 now points backward to the new node instead of node 1.

Step 8: All four pointers updated. The list is now: 1 <-> 44 <-> 2 <-> 3 <-> 4.

Result: Return the head (unchanged, still node 1).

Inserting Node 44 After Position 0 in a Doubly Linked List — Watch how we traverse to the target position, create a new node, and rewire four pointers to splice it into the doubly linked list.

Algorithm

  1. Create a new node with value x.
  2. Initialize a pointer curr at the head of the list.
  3. Traverse the list by moving curr = curr.next for p steps to reach the p-th node.
  4. Save the reference to the node after curr: nextNode = curr.next.
  5. Set newNode.next = nextNode — the new node points forward to the node that was after position p.
  6. Set newNode.prev = curr — the new node points backward to the node at position p.
  7. Set curr.next = newNode — the node at position p now points forward to the new node.
  8. If nextNode is not null, set nextNode.prev = newNode — the node that was after position p now points backward to the new node.
  9. Return the head of the list (unchanged).

Code

class Solution {
public:
    Node* addNode(Node* head, int p, int x) {
        // Create the new node
        Node* newNode = new Node(x);
        
        // Traverse to the p-th node
        Node* curr = head;
        for (int i = 0; i < p; i++) {
            curr = curr->next;
        }
        
        // Save the node after curr
        Node* nextNode = curr->next;
        
        // Rewire pointers to insert newNode after curr
        newNode->next = nextNode;
        newNode->prev = curr;
        curr->next = newNode;
        
        // If inserting before the end, update the backward pointer
        if (nextNode != nullptr) {
            nextNode->prev = newNode;
        }
        
        return head;
    }
};
class Solution:
    def addNode(self, head, p, x):
        # Create the new node
        new_node = Node(x)
        
        # Traverse to the p-th node
        curr = head
        for i in range(p):
            curr = curr.next
        
        # Save the node after curr
        next_node = curr.next
        
        # Rewire pointers to insert new_node after curr
        new_node.next = next_node
        new_node.prev = curr
        curr.next = new_node
        
        # If inserting before the end, update the backward pointer
        if next_node is not None:
            next_node.prev = new_node
        
        return head
class Solution {
    Node addNode(Node head, int p, int x) {
        // Create the new node
        Node newNode = new Node(x);
        
        // Traverse to the p-th node
        Node curr = head;
        for (int i = 0; i < p; i++) {
            curr = curr.next;
        }
        
        // Save the node after curr
        Node nextNode = curr.next;
        
        // Rewire pointers to insert newNode after curr
        newNode.next = nextNode;
        newNode.prev = curr;
        curr.next = newNode;
        
        // If inserting before the end, update the backward pointer
        if (nextNode != null) {
            nextNode.prev = newNode;
        }
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the list from the head to the p-th node, which takes at most O(n) steps where n is the length of the list. Once at the target position, the actual insertion (pointer rewiring) is O(1) — we update exactly 4 pointers regardless of list size. Overall: O(p) which is O(n) in the worst case when p = n − 1.

Space Complexity: O(1)

We only allocate one new node (which is required by the problem — it's not auxiliary space) and use a constant number of pointer variables (curr, nextNode, newNode). No additional data structures are created.