Insert at End of Doubly Linked List in DSA C++ - Execution Trace

Concept Flow - Insert at End of Doubly Linked List

Create new node with data

↓

Is list empty?

↓

Set head = new

↓

Traverse to last node

↓

Set last.next = new

↓

Set new.prev = last

↓

Done

Create a new node, check if list is empty, if yes set head to new node; else traverse to last node and link new node at end with proper prev and next pointers.

Execution Sample

DSA C++

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

void insertEnd(Node*& head, int val) {
  Node* newNode = new Node{val, nullptr, nullptr};
  if (!head) head = newNode;
  else {
    Node* curr = head;
    while (curr->next) curr = curr->next;
    curr->next = newNode;
    newNode->prev = curr;
  }
}

Insert a new node with given value at the end of a doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	∅	newNode → Node(10, prev=∅, next=∅)	∅
2	Check if head is null	∅	head = ∅ (empty list)	∅
3	List empty, set head = newNode	Node(10)	head → newNode	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head
4	Create new node with data=20	Node(10)	newNode → Node(20, prev=∅, next=∅)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ head
5	Check if head is null	Node(10)	head → Node(10) (not empty)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ head
6	Traverse to last node starting at head	Node(10)	curr → Node(10)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ head newNode
7	Set last.next = newNode	Node(10) → Node(20)	Node(10).next → Node(20)	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ head
8	Set newNode.prev = last	Node(10) ↔ Node(20)	Node(20).prev → Node(10)	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ prev:∅ │ │ prev:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ head
9	Done	Node(10) ↔ Node(20)	No pointer changes	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ prev:∅ │ │ prev:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ head

💡 Traversal ends when curr->next is null; new node linked at end.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 6	After Step 7	After Step 8	Final
head	∅	∅	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
newNode	∅	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)	Node(20)	Node(20)
curr	∅	∅	∅	∅	Node(10)	Node(10)	Node(10)	Node(10)

Key Moments - 3 Insights

Why do we check if the list is empty before inserting?

Because if the list is empty (head is null), we must set head to the new node directly. This is shown in execution_table step 3 where head changes from null to the new node.

Why do we traverse to the last node before inserting?

We need to find the current last node to link its next pointer to the new node. This traversal is shown in step 6 and 7 where curr moves to last node and then curr->next is set.

Why do we set newNode.prev to the last node?

Because in a doubly linked list, each node must know its previous node. This backward link is set in step 8, ensuring the list can be traversed backwards.

Visual Quiz - 3 Questions

Look at the execution_table, what is the state of the list after step 3?

A List is empty, head is null

B List has one node with data 10, head points to it

C List has two nodes linked

D New node is not created yet

💡 Hint

Check the Visual State column at step 3 in execution_table

At which step does the new node's prev pointer get set?

A Step 8

B Step 6

C Step 7

D Step 9

💡 Hint

Look at Pointer Changes column for newNode.prev assignment

If the list was initially empty, which steps would be skipped?

A Steps 4, 5, 6

B Steps 1, 2, 3

C Steps 6, 7, 8

D No steps are skipped

💡 Hint

Refer to the concept_flow where traversal happens only if list is not empty

Concept Snapshot

Insert at End of Doubly Linked List:
- Create new node with data
- If list empty, set head = new node
- Else traverse to last node
- Set last.next = new node
- Set new node.prev = last node
- New node's next = null
- List size increases by 1

Full Transcript

To insert at the end of a doubly linked list, first create a new node with the given data. Check if the list is empty by seeing if head is null. If empty, set head to the new node. If not empty, start from head and traverse nodes until reaching the last node (where next is null). Then set the last node's next pointer to the new node, and set the new node's prev pointer back to the last node. The new node's next pointer is null, marking it as the new tail. This process maintains the doubly linked structure allowing traversal in both directions.

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