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

Concept Flow - Insert at End of Doubly Linked List

Create new node

↓

Is list empty?

Yes→Set head and tail to new node

No↓

Set tail.next to new node

↓

Set new node.prev to tail

↓

Update tail to new node

↓

Done

This flow shows how to add a new node at the end of a doubly linked list, handling empty and non-empty cases.

Execution Sample

DSA C#

class Node {
  public int data;
  public Node prev, next;
  public Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
  public Node head, tail;

  // Insert at end
  public void InsertEnd(int val) {
    Node newNode = new Node(val);
    if (head == null) {
      head = tail = newNode;
    } else {
      tail.next = newNode;
      newNode.prev = tail;
      tail = newNode;
    }
  }
}

This code creates a new node and inserts it 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	newNode = Node(10)	∅
2	Check if list is empty	Empty	head = null, tail = null	∅
3	List empty: set head and tail to newNode	10	head → newNode, tail → newNode	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head/tail
4	Create new node with data=20	10	newNode = Node(20)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ head/tail
5	Check if list is empty	10	head != null, tail != null	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ head/tail
6	Set tail.next to newNode	10 -> 20	tail.next → newNode	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ head/tail
7	Set newNode.prev to tail	10 <-> 20	newNode.prev → tail	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ prev:∅ │←───│ prev:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ head/tail
8	Update tail to newNode	10 <-> 20	tail → newNode	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ prev:∅ │←───│ prev:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ head tail ✓
9	Create new node with data=30	10 <-> 20	newNode = Node(30)	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ data:30│ │ prev:∅ │←───│ prev:──┼ │ prev:∅ │ │ next:──┼ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
10	Set tail.next to newNode	10 <-> 20 -> 30	tail.next → newNode	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│───→│ data:20│───→│ data:30│ │ prev:∅ │←───│ prev:──┼ │ prev:∅ │ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
11	Set newNode.prev to tail	10 <-> 20 <-> 30	newNode.prev → tail	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│───→│ data:20│───→│ data:30│ │ prev:∅ │←───│ prev:──┼←───│ prev:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
12	Update tail to newNode	10 <-> 20 <-> 30	tail → newNode	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│───→│ data:20│───→│ data:30│ │ prev:∅ │←───│ prev:──┼←───│ prev:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail ✓

💡 Insertion stops after tail is updated to new node at the end.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12
head	null	null	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
tail	null	null	Node(10)	Node(10)	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)	Node(20)	Node(30)
newNode	null	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)	Node(20)	Node(30)	Node(30)	Node(30)	Node(30)

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 both head and tail to the new node. This is shown in execution_table step 3 where head and tail are assigned to newNode.

Why do we update tail.next and newNode.prev when list is not empty?

To link the new node at the end, tail.next points to newNode and newNode.prev points back to tail. This double link is shown in steps 6 and 7, ensuring traversal both ways.

Why do we update tail to newNode at the end?

Because the new node becomes the last node, so tail must point to it. This update is shown in step 8 and step 12, marking the new end of the list.

Visual Quiz - 3 Questions

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

A 10 -> 20 with tail at 10

B 10 <-> 20 with tail at 10

C Only node 10 with tail at 10

D Empty list

💡 Hint

Check the Visual State column at step 7 showing double links and tail pointer

At which step does the tail pointer first update to the new node?

A Step 8

B Step 6

C Step 3

D Step 12

💡 Hint

Look at Pointer Changes column for tail updates in the execution_table

If the list was empty, which step sets both head and tail to the new node?

A Step 2

B Step 5

C Step 3

D Step 8

💡 Hint

Refer to the operation description and pointer changes in step 3

Concept Snapshot

Insert at End of Doubly Linked List:
- Create new node with data
- If list empty: head and tail = new node
- Else: tail.next = new node, new node.prev = tail
- Update tail to new node
- Doubly linked list allows forward and backward traversal

Full Transcript

To insert a node at the end of a doubly linked list, first create the new node. Check if the list is empty by seeing if head is null. If empty, set both head and tail to the new node. If not empty, link the current tail's next pointer to the new node, and the new node's prev pointer back to the tail. Finally, update the tail pointer to the new node. This maintains the double links and updates the list's end correctly.

Practice

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

easy

A. To remove the first node

B. To find the middle node

C. To reverse the list

D. To add a new element after the last 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 D

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 reverses the list
• Assuming insertion happens at the start

2. Which of the following is the correct syntax to create a new node in C# for a doubly linked list?

easy

A. Node newNode = new Node(data);

B. Node newNode = Node(data);

C. newNode = Node.new(data);

D. Node newNode = new Node[];

Solution

1. Step 1: Understand object creation in C#

   In C#, objects are created using the 'new' keyword followed by the constructor call.

2. Step 2: Apply to Node creation

   Creating a new node requires calling the Node constructor with data inside parentheses after 'new'.

3. Final Answer:

   Node newNode = new Node(data); -> Option A

4. Quick Check:

   Use 'new' keyword with constructor call [OK]

Hint: Use 'new' keyword with constructor parentheses [OK]

Common Mistakes:

• Omitting 'new' keyword
• Using array syntax incorrectly
• Calling constructor without 'new'

3. Given the following code snippet, what will be the printed output after inserting 30 at the end of the doubly linked list?

class Node {
  public int data;
  public Node next, prev;
  public Node(int d) { data = d; next = prev = null; }
}

class DoublyLinkedList {
  public Node head;
  public void InsertAtEnd(int data) {
    Node newNode = new Node(data);
    if (head == null) {
      head = newNode;
      return;
    }
    Node temp = head;
    while (temp.next != null) {
      temp = temp.next;
    }
    temp.next = newNode;
    newNode.prev = temp;
  }
  public void PrintList() {
    Node temp = head;
    while (temp != null) {
      Console.Write(temp.data + " -> ");
      temp = temp.next;
    }
    Console.WriteLine("null");
  }
}

DoublyLinkedList dll = new DoublyLinkedList();
dll.InsertAtEnd(10);
dll.InsertAtEnd(20);
dll.InsertAtEnd(30);
dll.PrintList();

medium

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

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

C. 10 -> 20 -> null

D. null

Solution

1. Step 1: Trace InsertAtEnd calls

   First insert 10: list is 10 -> null. Then insert 20: list is 10 -> 20 -> null. Then insert 30: list is 10 -> 20 -> 30 -> null.

2. Step 2: PrintList outputs nodes in order

   PrintList prints each node's data followed by '->', ending with 'null'. So output is '10 -> 20 -> 30 -> null'.

3. Final Answer:

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

4. Quick Check:

   Insertion at end appends nodes in order [OK]

Hint: Insert at end appends nodes; print shows order [OK]

Common Mistakes:

• Confusing insertion order
• Printing in reverse order
• Missing 'null' at end

4. Identify the error in the following InsertAtEnd method for a doubly linked list:

public void InsertAtEnd(int data) {
  Node newNode = new Node(data);
  if (head == null) {
    head = newNode;
  }
  Node temp = head;
  while (temp.next != null) {
    temp = temp.next;
  }
  temp.next = newNode;
  newNode.prev = temp;
}

medium

A. Loop condition should be temp != null

B. Missing return after setting head when list is empty

C. Incorrect assignment of newNode.prev

D. Node constructor is called incorrectly

Solution

1. Step 1: Analyze empty list case

   If head is null, head is set to newNode but code continues to loop and assign pointers again, causing newNode to link to itself.

2. Step 2: Fix by adding return after setting head

   Adding 'return;' after 'head = newNode;' stops further code execution, preventing incorrect pointer assignments.

3. Final Answer:

   Missing return after setting head when list is empty -> Option B

4. Quick Check:

   Return after empty list insert prevents errors [OK]

Hint: Add return after empty list insertion [OK]

Common Mistakes:

• Not returning after setting head
• Wrong loop condition
• Misassigning prev pointer

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25. You want to insert 35 at the end. After insertion, which of the following correctly describes the pointers of the new node and the previous last node?

hard

A. newNode.prev points to null; node with 25.next points to newNode

B. newNode.next points to node with 25; node with 25.prev points to newNode

C. newNode.prev points to node with 25; node with 25.next points to newNode

D. newNode.prev and newNode.next both point to null; node with 25.next points to null

Solution

1. Step 1: Understand pointer updates when inserting at end

   The new node's prev pointer should point to the current last node (25), and the current last node's next pointer should point to the new node.

2. Step 2: Confirm new node's next pointer

   The new node's next pointer should be null because it is now the last node.

3. Final Answer:

   newNode.prev points to node with 25; node with 25.next points to newNode -> Option C

4. Quick Check:

   Prev points backward; next points forward [OK]

Hint: New node prev = old last; old last next = new node [OK]

Common Mistakes:

• Swapping prev and next pointers
• Setting newNode.prev to null
• Not updating old last node's next pointer