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, link new node at end with proper prev and next pointers.

Execution Sample

DSA C

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

void insertEnd(struct Node** head, int val) {
  // Insert val at end
}

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	Empty	new_node created with data=10, prev=∅, next=∅	∅ (empty list)
2	Check if list is empty	Empty	head == ∅ (true)	∅ (empty list)
3	Set head = new_node	1 node	head → new_node	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head
4	Create new node with data=20	1 node	new_node created with data=20, prev=∅, next=∅	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ head
5	Check if list is empty	1 node	head != ∅ (false)	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head
6	Traverse to last node	1 node	current = head (data=10), current.next == ∅ (stop)	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head, current
7	Set last.next = new_node	2 nodes	current.next → new_node (data=20)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head current.next
8	Set new_node.prev = last	2 nodes	new_node.prev → current (data=10)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │ │ prev:──┼──→ head │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head new_node
9	Done	2 nodes	List updated with new tail	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │←───┤ prev:──┼──→ ∅ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head tail

💡 Insertion complete; new node linked at end with correct prev and next pointers.

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)
new_node	∅	node(10)	node(10)	node(20)	node(20)	node(20)	node(20)	node(20)
current	∅	∅	∅	∅	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 == ∅), we must set head to the new node directly (see execution_table step 2 and 3). Otherwise, traversal to the last node is needed.

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

In a doubly linked list, each node points back to its previous node. Setting new_node.prev to last node maintains this backward link (see execution_table step 8).

How do we know where to insert the new node?

We traverse from head until current.next is ∅, meaning current is the last node. Then we link new_node after current (see execution_table step 6 and 7).

Visual Quiz - 3 Questions

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

A head is still empty (∅)

B head points to node with data 10

C head points to node with data 20

D head points to new_node with data 20

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 3 in execution_table.

At which step does the traversal to the last node stop?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in execution_table to find when current.next == ∅.

If the list was empty, which step would be skipped?

A Step 6 (traverse to last node)

B Step 3 (set head = new_node)

C Step 2 (check if list is empty)

D Step 8 (set new_node.prev = last)

💡 Hint

Refer to the concept_flow and execution_table steps for empty list insertion.

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, start from head and move through nodes until reaching the last node (where next is null). Then link the new node after the last node by setting last.next to new node and new_node.prev to last node. The new node's next pointer is set to null. This maintains the doubly linked structure with forward and backward links. The list now has one more node at the end.

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 list structure

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

2. Step 2: Purpose of insertion at end

   Inserting at the end means adding a new node after the last node, extending the list.

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 happens at the start
• Mixing up singly and doubly linked list operations

2. Which of the following is the correct way to update the 'next' pointer of the last node when inserting a new node at the end in C?

easy

A. last->next = newNode;

B. newNode->next = last;

C. last->prev = newNode;

D. newNode->prev = NULL;

Solution

1. Step 1: Identify the last node's next pointer

   The last node's 'next' pointer should point to the new node to link it at the end.

2. Step 2: Correct pointer assignment

   Assigning 'last->next = newNode;' correctly links the new node after the last node.

3. Final Answer:

   last->next = newNode; -> Option A

4. Quick Check:

   Last node's next points to new node [OK]

Hint: Last node's next points to new node [OK]

Common Mistakes:

• Assigning newNode->next to last (wrong direction)
• Changing last->prev instead of last->next
• Setting newNode->prev to NULL instead of last

3. What will be the output of the following code snippet after inserting a node with value 5 at the end of the doubly linked list 1 <-> 3 <-> 4?

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

void insertEnd(struct Node** head, int val) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = val;
  newNode->next = NULL;
  if (*head == NULL) {
    newNode->prev = NULL;
    *head = newNode;
    return;
  }
  struct Node* temp = *head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->next = newNode;
  newNode->prev = temp;
}

void printList(struct Node* head) {
  while (head != NULL) {
    printf("%d ", head->data);
    head = head->next;
  }
}

int main() {
  struct Node* head = malloc(sizeof(struct Node));
  head->data = 1; head->prev = NULL;
  struct Node* second = malloc(sizeof(struct Node));
  second->data = 3; second->prev = head; head->next = second;
  struct Node* third = malloc(sizeof(struct Node));
  third->data = 4; third->prev = second; second->next = third; third->next = NULL;
  insertEnd(&head, 5);
  printList(head);
  return 0;
}

medium

A. 1 3 4 0

B. 1 3 4 5

C. 1 3 4

D. 5 1 3 4

Solution

1. Step 1: Understand initial list and insertion

   The list is 1 <-> 3 <-> 4. The function inserts 5 at the end by traversing to last node (4) and linking new node after it.

2. Step 2: Trace printList output

   After insertion, list is 1 <-> 3 <-> 4 <-> 5. Printing nodes in order outputs "1 3 4 5 "

3. Final Answer:

   1 3 4 5 -> Option B

4. Quick Check:

   List after insertEnd = 1 3 4 5 [OK]

Hint: Traverse to last, link new node, print all nodes [OK]

Common Mistakes:

• Not setting newNode->prev correctly
• Forgetting to set last node's next to newNode
• Printing before insertion

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

void insertEnd(struct Node** head, int val) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = val;
  newNode->next = NULL;
  if (*head == NULL) {
    *head = newNode;
    return;
  }
  struct Node* temp = *head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->next = newNode;
}

medium

A. Wrong condition in while loop

B. Incorrect malloc size

C. Missing setting newNode->prev pointer

D. Not updating head pointer

Solution

1. Step 1: Check pointer assignments for doubly linked list

   In doubly linked list, newNode->prev must point to the last node (temp) after insertion.

2. Step 2: Identify missing pointer update

   The code sets temp->next = newNode but does not set newNode->prev = temp, breaking backward link.

3. Final Answer:

   Missing setting newNode->prev pointer -> Option C

4. Quick Check:

   newNode->prev must be set [OK]

Hint: Always set newNode->prev to last node [OK]

Common Mistakes:

• Forgetting newNode->prev assignment
• Assuming singly linked list logic applies
• Not handling empty list case

5. Given a doubly linked list with nodes 10 <-> 20 <-> 30, write the sequence of pointer changes when inserting a new node with value 40 at the end. Which of the following correctly describes the final connections?

hard

A. newNode->prev = NULL; newNode->next = NULL; last->next = NULL

B. newNode->next = last; last->prev = newNode; newNode->prev = NULL

C. last->prev = newNode; newNode->next = last; newNode->prev = NULL

D. last->next = newNode; newNode->prev = last; newNode->next = NULL

Solution

1. Step 1: Identify last node and new node pointers

   Last node is 30. New node 40 should be linked after 30 with next NULL.

2. Step 2: Correct pointer assignments

   Set last->next = newNode to link forward, newNode->prev = last for backward link, and newNode->next = NULL as it is new end.

3. Final Answer:

   last->next = newNode; newNode->prev = last; newNode->next = NULL -> Option D

4. Quick Check:

   New node linked after last with proper prev and next [OK]

Hint: New node's prev = last; last's next = new node; new node's next = NULL [OK]

Common Mistakes:

• Reversing prev and next pointers
• Setting newNode->prev to NULL incorrectly
• Not setting last->next to newNode