Insert at Specific Position in Doubly Linked List in DSA C

Mental Model

A doubly linked list lets you move forward and backward through nodes. To insert at a specific spot, you find that spot and adjust the links around it.

Analogy: Imagine a train with cars connected front and back. To add a new car in the middle, you disconnect the cars at that spot, insert the new car, then reconnect the cars before and after it.

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ null
          ↑

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 4 ↔ null, insert value 3 at position 3

Goal: Insert the value 3 at the 3rd position so the list becomes 1 ↔ 2 ↔ 3 ↔ 4 ↔ null

Step 1: start at head node (1)

head -> [1] ↔ 2 ↔ 4 ↔ null

Why: We begin from the start to find the insertion point

Step 2: move to next node (2)

head -> 1 ↔ [2] ↔ 4 ↔ null

Why: We move forward to reach position 2, just before insertion point

Step 3: create new node with value 3

new_node(3) created, not linked yet

Why: Prepare the new node to insert

Step 4: link new node between 2 and 4

head -> 1 ↔ 2 ↔ [3] ↔ 4 ↔ null

Why: Adjust pointers to insert new node at position 3

Result:

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for doubly linked list
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

// Create a new node with given data
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Insert node at specific position (1-based index)
void insertAtPosition(Node** head, int data, int position) {
    Node* newNode = createNode(data); // create new node
    if (position == 1) { // insert at head
        newNode->next = *head; // new node points to current head
        if (*head != NULL) {
            (*head)->prev = newNode; // current head points back to new node
        }
        *head = newNode; // update head to new node
        return;
    }

    Node* curr = *head;
    int count = 1;
    // move to node before insertion point
    while (curr != NULL && count < position - 1) {
        curr = curr->next; // advance curr
        count++;
    }

    if (curr == NULL) { // position is beyond list length
        free(newNode); // free unused node
        return; // do nothing
    }

    newNode->next = curr->next; // new node points to next node
    newNode->prev = curr; // new node points back to curr
    if (curr->next != NULL) {
        curr->next->prev = newNode; // next node points back to new node
    }
    curr->next = newNode; // curr points forward to new node
}

// Print list forward
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d", curr->data);
        if (curr->next != NULL) {
            printf(" ↔ ");
        }
        curr = curr->next;
    }
    printf(" ↔ null\n");
}

int main() {
    // Create initial list: 1 ↔ 2 ↔ 4
    Node* head = createNode(1);
    Node* second = createNode(2);
    Node* fourth = createNode(4);
    head->next = second;
    second->prev = head;
    second->next = fourth;
    fourth->prev = second;

    // Insert 3 at position 3
    insertAtPosition(&head, 3, 3);

    // Print final list
    printList(head);
    return 0;
}

Node* newNode = createNode(data);

create new node with given data

if (position == 1) { ... }

handle insertion at head separately

while (curr != NULL && count < position - 1) { curr = curr->next; count++; }

move curr to node before insertion point

if (curr == NULL) { free(newNode); return; }

guard against invalid position beyond list length

newNode->next = curr->next; newNode->prev = curr;

link new node forward and backward

if (curr->next != NULL) { curr->next->prev = newNode; }

adjust next node's prev pointer if exists

curr->next = newNode;

link current node forward to new node

Output

1 ↔ 2 ↔ 3 ↔ 4 ↔ null

Complexity Analysis

Time: O(n) because we may need to traverse up to n nodes to reach the insertion point

Space: O(1) because we only create one new node and use a few pointers

vs Alternative: Compared to inserting in an array which requires shifting elements (O(n)), doubly linked list insertion only needs pointer changes (O(1) after traversal)

Edge Cases

insert at position 1 (head insertion)

new node becomes new head, previous head's prev pointer updated

DSA C

if (position == 1) { ... }

insert at position beyond list length

insertion is ignored, new node freed to avoid memory leak

DSA C

if (curr == NULL) { free(newNode); return; }

insert into empty list at position 1

new node becomes head with next and prev as NULL

DSA C

if (position == 1) { ... }

When to Use This Pattern

When you need to add an element at a specific place in a list that allows backward and forward moves, use doubly linked list insertion to adjust pointers efficiently.

Common Mistakes

Mistake: Not updating the prev pointer of the node after the inserted node
Fix: Always set curr->next->prev = newNode if curr->next is not NULL

Mistake: Not handling insertion at head separately
Fix: Check if position is 1 and update head pointer and prev links accordingly

Summary

Inserts a new node at a given position in a doubly linked list by adjusting next and prev pointers.

Use when you want to add an element anywhere in a list that supports forward and backward traversal.

The key is to carefully update four pointers around the insertion point to keep the list connected.

Practice

1. What happens when you insert a new node at position 1 in a doubly linked list?

easy

A. The new node becomes the new head of the list.

B. The new node is added at the end of the list.

C. The new node replaces the last node.

D. The list remains unchanged.

Solution

1. Step 1: Understand position 1 insertion

   Inserting at position 1 means adding the node at the start of the list.

2. Step 2: Effect on head pointer

   The new node becomes the head, and its next points to the old head.

3. Final Answer:

   The new node becomes the new head of the list. -> Option A

4. Quick Check:

   Position 1 insertion updates head [OK]

Hint: Position 1 means new head insertion [OK]

Common Mistakes:

• Thinking position 1 means end insertion
• Not updating the head pointer
• Ignoring previous pointer updates

2. Which of the following is the correct way to update pointers when inserting a node at position 3 in a doubly linked list?

easy

A. newNode->next = temp; newNode->prev = temp->prev; temp->prev->next = newNode; temp->prev = newNode;

B. newNode->prev = temp->prev; newNode->next = temp; temp->prev->next = newNode; temp->prev = newNode;

C. newNode->next = temp->next; newNode->prev = temp; temp->next->prev = newNode; temp->next = newNode;

D. newNode->next = temp->next; newNode->prev = temp->prev; temp->next = newNode; temp->prev = newNode;

Solution

1. Step 1: Identify insertion point

   At position 3, newNode is inserted after temp (node at position 2).

2. Step 2: Update pointers correctly

   newNode's next points to temp's next, prev to temp; temp's next's prev updated to newNode; temp's next updated to newNode.

3. Final Answer:

   newNode->next = temp->next; newNode->prev = temp; temp->next->prev = newNode; temp->next = newNode; -> Option C

4. Quick Check:

   Correct pointer updates for middle insertion [OK]

Hint: Update newNode next/prev before changing temp pointers [OK]

Common Mistakes:

• Swapping next and prev pointers
• Not updating temp->next->prev
• Forgetting to update temp->next

3. What will be the list after inserting a node with value 10 at position 2 in the doubly linked list: 5 <-> 15 <-> 20?

medium

A. 5 <-> 15 <-> 10 <-> 20

B. 10 <-> 5 <-> 15 <-> 20

C. 5 <-> 15 <-> 20 <-> 10

D. 5 <-> 10 <-> 15 <-> 20

Solution

1. Step 1: Locate position 2

   Position 2 means new node goes between nodes 1 (5) and 2 (15).

2. Step 2: Insert new node with value 10

   New node's prev points to 5, next points to 15; update 5's next and 15's prev accordingly.

3. Final Answer:

   5 <-> 10 <-> 15 <-> 20 -> Option D

4. Quick Check:

   Inserted node at position 2 between 5 and 15 [OK]

Hint: Position 2 means between first and second nodes [OK]

Common Mistakes:

• Inserting at wrong position
• Not updating both next and prev pointers
• Appending instead of inserting

4. Given the code snippet below, what is the error when inserting at position 4 in a list of 3 nodes?

void insertAtPosition(Node** head, int data, int pos) {
  Node* newNode = createNode(data);
  Node* temp = *head;
  for (int i = 1; i < pos - 1; i++) {
    temp = temp->next;
  }
  newNode->next = temp->next;
  newNode->prev = temp;
  temp->next->prev = newNode;
  temp->next = newNode;
}

medium

A. newNode is not allocated properly.

B. temp->next is NULL, so temp->next->prev causes a runtime error.

C. Loop runs one time too many causing segmentation fault.

D. prev pointer of newNode is not set.

Solution

1. Step 1: Analyze loop for position 4 in 3-node list

   Loop moves temp to node at position 3; temp->next is NULL (end of list).

2. Step 2: Check pointer updates

   Accessing temp->next->prev causes runtime error because temp->next is NULL.

3. Final Answer:

   temp->next is NULL, so temp->next->prev causes a runtime error. -> Option B

4. Quick Check:

   Accessing NULL pointer causes runtime error [OK]

Hint: Check for NULL before accessing next->prev [OK]

Common Mistakes:

• Not checking if temp->next is NULL
• Assuming list is longer than it is
• Ignoring edge case at list end

5. You have a doubly linked list: 1 <-> 3 <-> 5 <-> 7. You want to insert a node with value 4 at position 3. After insertion, what will be the correct list and how do you handle the pointers to maintain list integrity?

hard

A. 1 <-> 3 <-> 4 <-> 5 <-> 7; Set newNode->prev = node at pos 2, newNode->next = node at pos 3, update adjacent nodes' pointers.

B. 1 <-> 3 <-> 5 <-> 4 <-> 7; Insert newNode after node at pos 3 without updating prev pointers.

C. 1 <-> 4 <-> 3 <-> 5 <-> 7; Insert newNode at head and shift others.

D. 1 <-> 3 <-> 5 <-> 7 <-> 4; Append newNode at end regardless of position.

Solution

1. Step 1: Identify insertion position and nodes

   Position 3 means new node goes between nodes with values 3 (pos 2) and 5 (pos 3).

2. Step 2: Update pointers to insert new node

   Set newNode->prev to node with value 3, newNode->next to node with value 5; update node 3's next and node 5's prev to newNode.

3. Step 3: Verify list integrity

   After insertion, list is 1 <-> 3 <-> 4 <-> 5 <-> 7 with all pointers correctly linked.

4. Final Answer:

   1 <-> 3 <-> 4 <-> 5 <-> 7; Set newNode->prev = node at pos 2, newNode->next = node at pos 3, update adjacent nodes' pointers. -> Option A

5. Quick Check:

   Proper pointer updates maintain doubly linked list [OK]

Hint: Insert between nodes, update both next and prev pointers [OK]

Common Mistakes:

• Inserting at wrong position
• Not updating both adjacent nodes' pointers
• Breaking list links causing traversal errors