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 in a doubly linked list

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

DSA C++

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
public:
    Node* head;
    DoublyLinkedList() : head(nullptr) {}

    void append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
        newNode->prev = temp;
    }

    void insertAtPosition(int val, int pos) {
        Node* newNode = new Node(val);
        if (pos == 1) {
            newNode->next = head;
            if (head) head->prev = newNode;
            head = newNode;
            return;
        }
        Node* temp = head;
        int count = 1;
        while (temp && count < pos - 1) {
            temp = temp->next;
            count++;
        }
        if (!temp) return; // position out of bounds
        newNode->next = temp->next;
        if (temp->next) temp->next->prev = newNode;
        temp->next = newNode;
        newNode->prev = temp;
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data;
            if (temp->next) std::cout << " <-> ";
            temp = temp->next;
        }
        std::cout << " <-> null" << std::endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.append(10);
    dll.append(20);
    dll.append(30);
    dll.append(40);
    dll.insertAtPosition(25, 3);
    dll.printList();
    return 0;
}

A 10 <-> 20 <-> 30 <-> 25 <-> 40 <-> null

B 10 <-> 25 <-> 20 <-> 30 <-> 40 <-> null

C 25 <-> 10 <-> 20 <-> 30 <-> 40 <-> null

D 10 <-> 20 <-> 25 <-> 30 <-> 40 <-> null

💡 Hint

Remember that position 3 means the new node should be the third node in the list.

The list initially is 10 <-> 20 <-> 30 <-> 40 <-> null. Inserting 25 at position 3 places it between 20 and 30.

❓ Predict Output

intermediate

Output after inserting at position 1 in a doubly linked list

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

DSA C++

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
public:
    Node* head;
    DoublyLinkedList() : head(nullptr) {}

    void append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
        newNode->prev = temp;
    }

    void insertAtPosition(int val, int pos) {
        Node* newNode = new Node(val);
        if (pos == 1) {
            newNode->next = head;
            if (head) head->prev = newNode;
            head = newNode;
            return;
        }
        Node* temp = head;
        int count = 1;
        while (temp && count < pos - 1) {
            temp = temp->next;
            count++;
        }
        if (!temp) return; // position out of bounds
        newNode->next = temp->next;
        if (temp->next) temp->next->prev = newNode;
        temp->next = newNode;
        newNode->prev = temp;
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data;
            if (temp->next) std::cout << " <-> ";
            temp = temp->next;
        }
        std::cout << " <-> null" << std::endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.append(10);
    dll.append(20);
    dll.append(30);
    dll.insertAtPosition(5, 1);
    dll.printList();
    return 0;
}

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

B 10 <-> 20 <-> 30 <-> 5 <-> 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 before the current head (10), becoming the new head.

🔧 Debug

advanced

Identify the error in insertAtPosition method

What error will occur when trying to insert at position 5 in a list of 3 nodes using this insertAtPosition method?

DSA C++

void insertAtPosition(int val, int pos) {
    Node* newNode = new Node(val);
    if (pos == 1) {
        newNode->next = head;
        if (head) head->prev = newNode;
        head = newNode;
        return;
    }
    Node* temp = head;
    int count = 1;
    while (temp && count < pos - 1) {
        temp = temp->next;
        count++;
    }
    if (!temp) return; // Added check to prevent nullptr dereference
    newNode->next = temp->next;
    if (temp->next) temp->next->prev = newNode;
    temp->next = newNode;
    newNode->prev = temp;
}

A Compilation error due to missing return

B No error, insertion succeeds at end

C Segmentation fault due to dereferencing nullptr

D Logical error: node inserted at wrong position

💡 Hint

Consider what happens if pos is greater than the length + 1 of the list.

If pos is beyond the list length + 1, temp becomes nullptr and accessing temp->next causes a segmentation fault.

🧠 Conceptual

advanced

Effect of inserting at position beyond list length + 1

What happens if you try to insert a node at position 10 in a doubly linked list that currently has 5 nodes, using the insertAtPosition method shown?

A The insertion is ignored and the list remains unchanged

B The node is appended at the end of the list

C The program crashes due to invalid memory access

D The node is inserted at position 5 instead

💡 Hint

Look at how the method handles the case when temp becomes nullptr.

The method returns early if temp is nullptr, so no insertion happens and the list stays the same.

🚀 Application

expert

Final list after multiple insertions at various positions

Given an initially empty doubly linked list, after performing these operations in order: 1. append(10) 2. append(20) 3. insertAtPosition(15, 2) 4. insertAtPosition(5, 1) 5. insertAtPosition(25, 5) What is the printed state of the list?

DSA C++

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
public:
    Node* head;
    DoublyLinkedList() : head(nullptr) {}

    void append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
        newNode->prev = temp;
    }

    void insertAtPosition(int val, int pos) {
        Node* newNode = new Node(val);
        if (pos == 1) {
            newNode->next = head;
            if (head) head->prev = newNode;
            head = newNode;
            return;
        }
        Node* temp = head;
        int count = 1;
        while (temp && count < pos - 1) {
            temp = temp->next;
            count++;
        }
        if (!temp) return;
        newNode->next = temp->next;
        if (temp->next) temp->next->prev = newNode;
        temp->next = newNode;
        newNode->prev = temp;
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data;
            if (temp->next) std::cout << " <-> ";
            temp = temp->next;
        }
        std::cout << " <-> null" << std::endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.append(10);
    dll.append(20);
    dll.insertAtPosition(15, 2);
    dll.insertAtPosition(5, 1);
    dll.insertAtPosition(25, 5);
    dll.printList();
    return 0;
}

A 5 <-> 10 <-> 15 <-> 25 <-> 20 <-> null

B 5 <-> 10 <-> 15 <-> 20 <-> 25 <-> null

C 10 <-> 5 <-> 15 <-> 20 <-> 25 <-> null

D 5 <-> 10 <-> 20 <-> 15 <-> 25 <-> null

💡 Hint

Track each insertion carefully and remember the list positions shift after each insertion.

After all operations, the list is: 5 (pos 1), 10 (pos 2), 15 (pos 3), 20 (pos 4), 25 (pos 5).

Practice

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

easy

A. The list remains unchanged.

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

C. The new node replaces the last node.

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

Solution

1. Step 1: Understand position 1 in doubly linked list

   Position 1 means the start of the list, so the new node should be the first node.

2. Step 2: Insert new node at head

   The new node's next pointer points to the old head, and the old head's previous pointer points back to the new node.

3. Final Answer:

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

4. Quick Check:

   Insert at position 1 = new head [OK]

Hint: Position 1 means insert at the start [OK]

Common Mistakes:

• Inserting at position 1 but not updating head pointer
• Not updating previous pointer of old head
• Confusing position 1 with end of list

2. Which of the following is the correct syntax to insert a new node at position pos in a doubly linked list in C++?

easy

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

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

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

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

Solution

1. Step 1: Identify correct pointer updates for insertion

   When inserting after temp, newNode's next points to temp's next, and newNode's prev points to temp.

2. Step 2: Update surrounding nodes' pointers

   temp's next's prev must point to newNode, and temp's next must point to newNode.

3. Final Answer:

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

4. Quick Check:

   Correct pointer updates = newNode->next = temp->next; temp->next->prev = newNode; temp->next = newNode; newNode->prev = temp; [OK]

Hint: Update next and prev pointers carefully [OK]

Common Mistakes:

• Mixing up next and prev pointers
• Not updating temp->next->prev pointer
• Assigning pointers in wrong order causing broken links

3. Given the doubly linked list: 10 <-> 20 <-> 30 <-> null, what will be the list after inserting 15 at position 2?

void insertAtPosition(Node*& head, int data, int pos) {
  Node* newNode = new Node(data);
  if (pos == 1) {
    newNode->next = head;
    if (head) head->prev = newNode;
    head = newNode;
    return;
  }
  Node* temp = head;
  for (int i = 1; i < pos - 1 && temp != nullptr; i++) {
    temp = temp->next;
  }
  if (temp == nullptr) return;
  newNode->next = temp->next;
  if (temp->next) temp->next->prev = newNode;
  temp->next = newNode;
  newNode->prev = temp;
}

medium

A. 10 <-> 15 <-> 20 <-> 30 <-> null

B. 15 <-> 10 <-> 20 <-> 30 <-> null

C. 10 <-> 20 <-> 15 <-> 30 <-> null

D. 10 <-> 20 <-> 30 <-> 15 <-> null

Solution

1. Step 1: Locate position 2 in the list

   Position 2 means after the first node (10). So temp points to node with data 10.

2. Step 2: Insert new node with data 15 after temp

   New node's next points to 20, and prev points to 10. Update 10's next to new node and 20's prev to new node.

3. Final Answer:

   10 <-> 15 <-> 20 <-> 30 <-> null -> Option A

4. Quick Check:

   Insert at position 2 places new node after first node [OK]

Hint: Position 2 means insert after first node [OK]

Common Mistakes:

• Inserting before first node instead of after
• Not updating prev pointer of next node
• Skipping position count in loop

4. Identify the error in the following code snippet for inserting at position pos in a doubly linked list:

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

medium

A. The newNode->next pointer is assigned after temp->next is changed.

B. The newNode->prev pointer is not set correctly.

C. The head pointer is not updated when inserting at position 1.

D. The loop does not check if temp is nullptr, causing possible crash.

Solution

1. Step 1: Analyze the for loop traversal

   The loop moves temp forward but does not check if temp becomes nullptr, risking null pointer dereference.

2. Step 2: Identify missing safety check

   Without checking temp != nullptr, accessing temp->next can cause a crash if pos is invalid or list is short.

3. Final Answer:

   The loop does not check if temp is nullptr, causing possible crash. -> Option D

4. Quick Check:

   Always check temp != nullptr in traversal loops [OK]

Hint: Always check for nullptr when traversing [OK]

Common Mistakes:

• Ignoring nullptr checks in loops
• Not updating head for position 1 insert
• Incorrect order of pointer assignments

5. You have a doubly linked list: 5 <-> 10 <-> 15 <-> 20 <-> null. You want to insert a new node with value 12 at position 3. After insertion, what will be the correct sequence of the list? Also, explain how to handle insertion at the last position if the position is greater than the list length.

hard

A. 5 <-> 12 <-> 10 <-> 15 <-> 20 <-> null; Insert at last by replacing last node.

B. 5 <-> 10 <-> 15 <-> 12 <-> 20 <-> null; Insert at last by adding node before head.

C. 5 <-> 10 <-> 12 <-> 15 <-> 20 <-> null; Insert at last by traversing till last node and updating pointers.

D. 5 <-> 10 <-> 15 <-> 20 <-> 12 <-> null; Insert at last by ignoring position.

Solution

1. Step 1: Insert 12 at position 3

   Position 3 means after second node (10). Insert new node between 10 and 15, updating next and prev pointers accordingly.

2. Step 2: Handle insertion at last position if position > length

   Traverse to last node, then insert new node after it, updating last node's next and new node's prev pointers.

3. Final Answer:

   5 <-> 10 <-> 12 <-> 15 <-> 20 <-> null; Insert at last by traversing till last node and updating pointers. -> Option C

4. Quick Check:

   Insert at position 3 places node between 10 and 15; last insert by traversal [OK]

Hint: Insert at position or append if position too large [OK]

Common Mistakes:

• Inserting at wrong position
• Not updating prev pointer of next node
• Ignoring last position insertion logic