Insert at End of Doubly Linked List in DSA C++

Mental Model

A doubly linked list has nodes connected both forward and backward. To add a new node at the end, we link it after the last node and update pointers.

Analogy: Imagine a train where each carriage is connected to the one before and after. Adding a new carriage at the end means attaching it to the last carriage and making sure both know about each other.

head -> [1] ↔ [2] ↔ [3] -> null
null ← [1] ↔ [2] ↔ [3] ← tail

Dry Run Walkthrough

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

Goal: Add a new node with value 4 at the end of the doubly linked list

Step 1: Create new node with value 4

new_node: [4] null null

Why: We need a new node to insert at the end

Step 2: Find last node (3) by traversing from head

head -> [1] ↔ [2] ↔ [3] ← tail
new_node: [4] null null

Why: We must link new node after the last node

Step 3: Set last node's next pointer to new node

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

Why: Link last node forward to new node

Step 4: Set new node's previous pointer to last node

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

Why: Link new node backward to last node

Result:

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

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Node {
public:
    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); // create new node
        if (!head) {
            head = newNode; // empty list, new node is head
            return;
        }
        Node* curr = head;
        while (curr->next) {
            curr = curr->next; // move to last node
        }
        curr->next = newNode; // link last node forward
        newNode->prev = curr; // link new node backward
    }

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

int main() {
    DoublyLinkedList dll;
    dll.insertAtEnd(1);
    dll.insertAtEnd(2);
    dll.insertAtEnd(3);
    dll.printList();
    dll.insertAtEnd(4);
    dll.printList();
    return 0;
}

Node* newNode = new Node(val); // create new node

create new node with given value

if (!head) { head = newNode; // empty list, new node is head return; }

handle empty list by setting head to new node

while (curr->next) { curr = curr->next; // move to last node }

traverse to last node in list

curr->next = newNode; // link last node forward newNode->prev = curr; // link new node backward

link new node after last node in both directions

Output

1 ↔ 2 ↔ 3 -> null

1 ↔ 2 ↔ 3 ↔ 4 -> null

Complexity Analysis

Time: O(n) because we traverse all nodes once to reach the end

Space: O(1) because we only create one new node and use constant extra space

vs Alternative: Compared to inserting at head which is O(1), inserting at end requires traversal making it O(n)

Edge Cases

empty list

new node becomes the head with no previous or next nodes

DSA C++

if (!head) {
    head = newNode; // empty list, new node is head
    return;
}

single element list

new node is linked after the single node, updating next and prev pointers correctly

DSA C++

while (curr->next) {
    curr = curr->next; // move to last node
}

When to Use This Pattern

When you need to add an element at the end of a doubly linked list, use the insert at end pattern to update both next and prev pointers correctly.

Common Mistakes

Mistake: Forgetting to update the new node's prev pointer to the last node
Fix: Always set newNode->prev = curr after linking curr->next = newNode

Mistake: Not handling empty list case, causing null pointer errors
Fix: Check if head is null and set head to new node before traversal

Summary

Adds a new node at the end of a doubly linked list by updating next and prev pointers.

Use when you want to append data to the end of a doubly linked list.

Remember to link both directions: last node's next to new node, and new node's prev to last node.

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