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.