Insert at End of Doubly Linked List in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting nodes at the end

What is the printed state of the doubly linked list after inserting 10, 20, and 30 at the end?

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 insertAtEnd(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 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.insertAtEnd(10);
    dll.insertAtEnd(20);
    dll.insertAtEnd(30);
    dll.printList();
    return 0;
}

A 10 -> 20 -> 30 -> null

B null

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

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

💡 Hint

Remember that inserting at the end adds nodes after the last node, preserving order.

The insertAtEnd function adds nodes at the end, so the list maintains insertion order: 10, then 20, then 30. The printList function prints nodes from head to tail with arrows.

🧠 Conceptual

intermediate

Understanding pointer updates in insertion at end

When inserting a new node at the end of a doubly linked list, which pointers must be updated to maintain list integrity?

A The new node's next points to the head; the head's prev points to the new node

B The new node's prev points to the last node; the last node's next points to the new node

C Only the head pointer needs to be updated to the new node

D The new node's prev and next pointers remain null

💡 Hint

Think about how the new node connects to the existing last node.

To insert at the end, the new node's prev pointer must point to the current last node, and the last node's next pointer must point to the new node. This keeps the chain intact.

🔧 Debug

advanced

Identify the bug in this insertion code

What error will occur when running this code snippet to insert at the end of a doubly linked list?

DSA C++

void insertAtEnd(int val) {
    Node* newNode = new Node(val);
    if (!head) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = newNode;
    // Missing line here
}

A The new node's prev pointer is not set, causing incorrect backward traversal

B The head pointer is overwritten, losing the list

C The code causes a segmentation fault due to null dereference

D No error; code works correctly

💡 Hint

Check if all pointers of the new node are properly assigned.

The code sets temp->next to newNode but forgets to set newNode->prev to temp. This breaks backward links in the doubly linked list.

❓ Predict Output

advanced

Output after inserting into an empty list

What is the output after inserting a single node with value 5 into an empty doubly linked list and printing it?

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 insertAtEnd(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 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.insertAtEnd(5);
    dll.printList();
    return 0;
}

A 5 -> null

B 5 <-> null

C null

D 5 <-> 5 -> null

💡 Hint

A single node has no next node, so no backward or forward arrows except the end.

The list has one node with data 5. The printList prints the data and then '-> null' since next is null. No '<->' appears because there is no next node.

🧠 Conceptual

expert

Time complexity of inserting at the end with and without tail pointer

What is the time complexity of inserting a node at the end of a doubly linked list if we do NOT maintain a tail pointer, and how does it change if we DO maintain a tail pointer?

A Without tail pointer: O(n^2); With tail pointer: O(n)

B Without tail pointer: O(1); With tail pointer: O(n)

C Without tail pointer: O(n); With tail pointer: O(1)

D Without tail pointer: O(log n); With tail pointer: O(log n)

💡 Hint

Think about how many nodes you must traverse to find the end.

Without a tail pointer, you must traverse the entire list to find the last node, which takes O(n) time. With a tail pointer, you can access the last node directly, so insertion is O(1).

Practice

1. What is the main purpose of inserting a node at the end of a doubly linked list?

easy

A. To add a new element after the last node

B. To remove the first node

C. To reverse the list

D. To find the middle node

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes connected forward and backward, allowing traversal in both directions.

2. Step 2: Purpose of insertion at the end

   Inserting at the end means adding a new node after the current last node, updating pointers accordingly.

3. Final Answer:

   To add a new element after the last node -> Option A

4. Quick Check:

   Insert at end = Add after last node [OK]

Hint: Insert at end means add after last node [OK]

Common Mistakes:

• Confusing insertion at end with deletion
• Thinking insertion at end reverses the list
• Assuming insertion happens at the start

2. Which of the following is the correct way to update the tail pointer when inserting a new node at the end of a doubly linked list in C++?

easy

A. tail = NULL;

B. tail = tail->prev;

C. tail = head;

D. tail = newNode;

Solution

1. Step 1: Identify the new tail after insertion

   When a new node is added at the end, it becomes the new tail of the list.

2. Step 2: Update the tail pointer

   Assign the tail pointer to point to the new node to reflect the updated end of the list.

3. Final Answer:

   tail = newNode; -> Option D

4. Quick Check:

   New tail points to newNode [OK]

Hint: Tail always points to the last inserted node [OK]

Common Mistakes:

• Setting tail to previous node instead of new node
• Resetting tail to head incorrectly
• Assigning tail to NULL after insertion

3. What will be the output of the following code snippet after inserting 30 at the end of the doubly linked list?

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

Node* head = new Node{10, NULL, NULL};
Node* tail = head;

Node* newNode = new Node{30, tail, NULL};
tail->next = newNode;
tail = newNode;

// Print list from head
Node* temp = head;
while(temp != NULL) {
  std::cout << temp->data << " ";
  temp = temp->next;
}

medium

A. 10 30

B. 30 10

C. 10

D. 30

Solution

1. Step 1: Initial list and insertion

   Initially, list has one node with data 10. New node with 30 is added at end, linked properly.

2. Step 2: Traversing and printing

   Starting from head (10), print data then move to next node (30), print data, then NULL ends loop.

3. Final Answer:

   10 30 -> Option A

4. Quick Check:

   List after insertion = 10 30 [OK]

Hint: Traverse from head to see all nodes in order [OK]

Common Mistakes:

• Printing nodes in reverse order
• Not updating tail->next pointer
• Forgetting to update tail pointer

4. Identify the error in the following code snippet that inserts a node at the end of a doubly linked list:

void insertEnd(Node*& head, Node*& tail, int val) {
  Node* newNode = new Node{val, NULL, NULL};
  if (head == NULL) {
    head = newNode;
    tail = newNode;
  } else {
    tail->next = newNode;
    newNode->prev = tail;
    head = newNode;  // Error here
  }
}

medium

A. head should be updated to newNode

B. newNode->prev should be NULL

C. tail should be updated to newNode

D. tail->next should be NULL

Solution

1. Step 1: Analyze pointer updates in else block

   tail->next points to newNode and newNode->prev points to tail correctly.

2. Step 2: Identify incorrect pointer assignment

   head is wrongly updated to newNode; it should remain unchanged. Instead, tail should be updated to newNode.

3. Final Answer:

   tail should be updated to newNode -> Option C

4. Quick Check:

   Tail points to last node after insertion [OK]

Hint: Update tail, not head, when inserting at end [OK]

Common Mistakes:

• Updating head instead of tail
• Not linking newNode's prev pointer
• Forgetting to set tail->next

5. Given a doubly linked list with nodes 5 <-> 10 <-> 15, write the sequence of node values after inserting 20 at the end and then 2 at the end. What is the final list?

hard

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

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

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

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

Solution

1. Step 1: Insert 20 at the end

   Starting list: 5 <-> 10 <-> 15. After inserting 20 at end: 5 <-> 10 <-> 15 <-> 20.

2. Step 2: Insert 2 at the end

   Now add 2 at end: 5 <-> 10 <-> 15 <-> 20 <-> 2.

3. Final Answer:

   5 <-> 10 <-> 15 <-> 20 <-> 2 -> Option B

4. Quick Check:

   Insertions add nodes at list end in order [OK]

Hint: Insertions add nodes at the end, order preserved [OK]

Common Mistakes:

• Inserting new nodes at the start instead of end
• Mixing order of inserted nodes
• Confusing next and prev pointers