Insert at Specific Position in Doubly Linked List in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting at position 3

What is the printed state of the doubly linked list after inserting the value 25 at position 3?

DSA C

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

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

void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

Node* insertAtPosition(Node* head, int data, int pos) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;

    if (pos == 1) {
        newNode->next = head;
        if (head != NULL) head->prev = newNode;
        return newNode;
    }

    Node* temp = head;
    int count = 1;
    while (temp != NULL && count < pos - 1) {
        temp = temp->next;
        count++;
    }

    if (temp == NULL) return head; // position out of bounds

    newNode->next = temp->next;
    if (temp->next != NULL) temp->next->prev = newNode;
    temp->next = newNode;
    newNode->prev = temp;

    return head;
}

int main() {
    Node* head = NULL;
    head = insertAtPosition(head, 10, 1);
    head = insertAtPosition(head, 20, 2);
    head = insertAtPosition(head, 30, 3);
    head = insertAtPosition(head, 25, 3);
    printList(head);
    return 0;
}

A 10 <-> 20 <-> 25 <-> 30 <-> NULL

B 10 <-> 25 <-> 20 <-> 30 <-> NULL

C 10 <-> 20 <-> 30 <-> 25 <-> NULL

D 25 <-> 10 <-> 20 <-> 30 <-> NULL

💡 Hint

Remember that position 3 means the new node goes after the second node.

The new node with value 25 is inserted after the second node (20), so the order becomes 10, 20, 25, 30.

❓ Predict Output

intermediate

Output after inserting at position 1 (head)

What is the printed state of the doubly linked list after inserting the value 5 at position 1?

DSA C

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

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

void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

Node* insertAtPosition(Node* head, int data, int pos) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;

    if (pos == 1) {
        newNode->next = head;
        if (head != NULL) head->prev = newNode;
        return newNode;
    }

    Node* temp = head;
    int count = 1;
    while (temp != NULL && count < pos - 1) {
        temp = temp->next;
        count++;
    }

    if (temp == NULL) return head; // position out of bounds

    newNode->next = temp->next;
    if (temp->next != NULL) temp->next->prev = newNode;
    temp->next = newNode;
    newNode->prev = temp;

    return head;
}

int main() {
    Node* head = NULL;
    head = insertAtPosition(head, 10, 1);
    head = insertAtPosition(head, 20, 2);
    head = insertAtPosition(head, 30, 3);
    head = insertAtPosition(head, 5, 1);
    printList(head);
    return 0;
}

A 10 <-> 20 <-> 30 <-> 5 <-> NULL

B 5 <-> 10 <-> 20 <-> 30 <-> NULL

C 10 <-> 5 <-> 20 <-> 30 <-> NULL

D 5 <-> 20 <-> 10 <-> 30 <-> NULL

💡 Hint

Inserting at position 1 means the new node becomes the new head.

The new node with value 5 is inserted at the start, so the list starts with 5 followed by the original nodes.

🔧 Debug

advanced

Identify the bug causing incorrect insertion at tail

The following code attempts to insert a node at a specific position in a doubly linked list. However, inserting at the last position does not link the new node correctly. What is the bug?

DSA C

Node* insertAtPosition(Node* head, int data, int pos) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;

    if (pos == 1) {
        newNode->next = head;
        if (head != NULL) head->prev = newNode;
        return newNode;
    }

    Node* temp = head;
    int count = 1;
    while (temp != NULL && count < pos - 1) {
        temp = temp->next;
        count++;
    }

    if (temp == NULL) return head; // position out of bounds

    newNode->next = temp->next;
    if (temp->next != NULL) temp->next->prev = newNode;
    temp->next = newNode;
    newNode->prev = temp;

    return head;
}

A The code does not handle insertion when pos is one more than the length, so temp->next is NULL and newNode is not linked properly.

B The newNode->prev is not set correctly before insertion.

C The code does not allocate memory for newNode properly.

D The code does not update head pointer when inserting at the tail.

💡 Hint

Check what happens when inserting at the end of the list.

When inserting at the last position (pos = length + 1), temp points to the last node, temp->next is NULL. The code sets newNode->next = NULL and temp->next = newNode, which is correct. But if pos is beyond length + 1, temp becomes NULL and insertion is skipped. The bug is that the code does not allow insertion exactly at the tail if pos is length + 1 because the while loop stops early or temp becomes NULL incorrectly.

❓ Predict Output

advanced

Output after inserting at position beyond list length

What is the printed state of the doubly linked list after attempting to insert the value 40 at position 10, given the list has only 3 nodes?

DSA C

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

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

void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

Node* insertAtPosition(Node* head, int data, int pos) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;

    if (pos == 1) {
        newNode->next = head;
        if (head != NULL) head->prev = newNode;
        return newNode;
    }

    Node* temp = head;
    int count = 1;
    while (temp != NULL && count < pos - 1) {
        temp = temp->next;
        count++;
    }

    if (temp == NULL) return head; // position out of bounds

    newNode->next = temp->next;
    if (temp->next != NULL) temp->next->prev = newNode;
    temp->next = newNode;
    newNode->prev = temp;

    return head;
}

int main() {
    Node* head = NULL;
    head = insertAtPosition(head, 10, 1);
    head = insertAtPosition(head, 20, 2);
    head = insertAtPosition(head, 30, 3);
    head = insertAtPosition(head, 40, 10);
    printList(head);
    return 0;
}

A 40 <-> 10 <-> 20 <-> 30 <-> NULL

B 10 <-> 20 <-> 30 <-> 40 <-> NULL

C 10 <-> 20 <-> 30 <-> NULL

D NULL

💡 Hint

Inserting beyond the list length should not change the list.

Since position 10 is beyond the current list length (3), the insertion is ignored and the list remains unchanged.

🧠 Conceptual

expert

Time complexity of insertion at specific position

What is the time complexity of inserting a node at a specific position in a doubly linked list of length n, assuming you have only the head pointer?

A O(1) because doubly linked lists allow direct access to any position

B O(n^2) because each insertion requires traversing the entire list multiple times

C O(log n) because the list is sorted and binary search can be used

D O(n) because you must traverse the list to reach the position before insertion

💡 Hint

Think about how you find the position before inserting.

Without direct access, you must traverse from the head to the position before insertion, which takes O(n) time.

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