Insert at End Tail Insert in DSA C# - Execution Trace

Concept Flow - Insert at End Tail Insert

Create new node with data

↓

Is list empty?

↓

Set head = new

↓

Traverse until current.next == null

↓

Set current.next = new node

↓

Done

This flow shows how to add a new node at the end of a singly linked list by creating the node, checking if the list is empty, and then either setting head or traversing to the last node to link the new node.

Execution Sample

DSA C#

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

void InsertAtEnd(ref Node head, int val) {
  Node newNode = new Node(val);
  if (head == null) {
    head = newNode;
    return;
  }
  Node current = head;
  while (current.next != null) {
    current = current.next;
  }
  current.next = newNode;
}

This code defines a node and a method to insert a new node with value val at the end of the linked list starting at head.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=40	10 -> 20 -> 30 -> null	newNode = Node(40)	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head
2	Check if head is null	10 -> 20 -> 30 -> null	head != null (No change)	Same as step 1
3	Start traversal at head	10 -> 20 -> 30 -> null	current = head (10)	Same as step 1, current points to 10
4	Check current.next != null (10.next != null)	10 -> 20 -> 30 -> null	Move current to 20	Same as step 1, current points to 20
5	Check current.next != null (20.next != null)	10 -> 20 -> 30 -> null	Move current to 30	Same as step 1, current points to 30
6	Check current.next != null (30.next == null)	10 -> 20 -> 30 -> null	Stop traversal	Current at 30 (last node)
7	Set current.next = newNode	10 -> 20 -> 30 -> 40 -> null	30.next → newNode(40)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
8	Done	10 -> 20 -> 30 -> 40 -> null	No pointer changes	Final list with new tail node 40

💡 Traversal stops when current.next is null, then new node is linked as last node.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	Final
head	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
current	null	Node(10)	Node(20)	Node(30)	Node(30)	Node(30)
newNode	null	Node(40)	Node(40)	Node(40)	Node(40)	Node(40)

Key Moments - 3 Insights

Why do we check current.next != null instead of current != null during traversal?

Because we want to stop at the last node, not after it. current.next == null means current is last node. See steps 4-6 in execution_table where traversal moves until current.next is null.

What happens if the list is empty (head == null)?

We set head to the new node directly, making it the first and last node. This is shown in concept_flow's 'Yes' branch after checking if list is empty.

How does the pointer change when inserting the new node?

The last node's next pointer changes from null to point to the new node. See step 7 in execution_table where 30.next points to newNode(40).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 5?

A Node with data 20

B Node with data 30

C Node with data 40

D null

💡 Hint

Check the 'current' variable in variable_tracker after step 5.

At which step does the traversal stop because current.next is null?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in execution_table around steps 5 and 6.

If the list was empty initially, what would be the pointer change?

A head = newNode

B current.next = newNode

C No pointer changes

D newNode.next = head

💡 Hint

Refer to concept_flow's branch when list is empty.

Concept Snapshot

Insert at End (Tail Insert) in singly linked list:
- Create new node with data
- If list empty (head == null), set head = new node
- Else traverse from head until last node (current.next == null)
- Set last node's next pointer to new node
- New node's next is null (new tail)
- Time complexity: O(n) for traversal

Full Transcript

This concept shows how to insert a new node at the end of a singly linked list. First, a new node is created with the given data. If the list is empty, the new node becomes the head. Otherwise, we start at the head and move through nodes until we find the last node, identified by its next pointer being null. Then, we link the last node's next pointer to the new node, making it the new tail. The traversal stops when current.next is null, not when current is null, to ensure we link correctly. The pointer changes are carefully tracked to show how the list grows. This process takes linear time proportional to the list length.

Practice

1. What does the InsertAtEnd method do in a singly linked list?

easy

A. Adds a new node at the end (tail) of the list

B. Removes the first node of the list

C. Inserts a new node at the beginning (head) of the list

D. Deletes the last node of the list

Solution

1. Step 1: Understand the method name

   The method name InsertAtEnd suggests adding a node at the end of the list.

2. Step 2: Recall linked list operations

   Inserting at the end means adding a new node after the current last node (tail).

3. Final Answer:

   Adds a new node at the end (tail) of the list -> Option A

4. Quick Check:

   InsertAtEnd = Add node at tail [OK]

Hint: InsertAtEnd means add node at tail, not head or remove [OK]

Common Mistakes:

• Confusing insert at end with insert at beginning
• Thinking it removes nodes instead of adding
• Mixing up tail and head operations

2. Which of the following is the correct syntax to create a new node and insert it at the end of a singly linked list in C#?

easy

A. Node newNode = new Node(data); tail.next = newNode; tail = newNode;

B. Node newNode = new Node(data); newNode.next = head;

C. Node newNode = new Node(data); newNode.prev = tail; tail = newNode;

D. Node newNode = new Node(data); head = newNode;

Solution

1. Step 1: Create a new node with data

   We create a new node using new Node(data).

2. Step 2: Link new node at the end

   To insert at end, set tail.next = newNode and update tail = newNode.

3. Final Answer:

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

4. Quick Check:

   Insert at tail = tail.next = newNode; tail = newNode [OK]

Hint: Tail insert needs tail.next and tail update [OK]

Common Mistakes:

• Assigning newNode.next to head instead of tail.next
• Forgetting to update tail pointer
• Using prev pointer in singly linked list

3. What will be the output linked list after executing the following code?

LinkedList list = new LinkedList();
list.InsertAtEnd(10);
list.InsertAtEnd(20);
list.InsertAtEnd(30);
list.PrintList();

Assuming PrintList() prints nodes as value -> value -> ... -> null.

medium

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

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

C. 10 -> 20 -> null

D. null

Solution

1. Step 1: Insert nodes at end in order

   Nodes 10, 20, 30 are inserted at the tail one by one, so list order is 10, then 20, then 30.

2. Step 2: Print list in order

   Printing shows nodes in insertion order ending with null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option B

4. Quick Check:

   InsertAtEnd preserves order: 10,20,30 [OK]

Hint: InsertAtEnd keeps order; print shows same sequence [OK]

Common Mistakes:

• Assuming insert at end reverses order
• Missing last node in print
• Confusing head and tail positions

4. The following code tries to insert a node at the end of a singly linked list but causes a runtime error. What is the error?

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

medium

A. Node constructor is missing

B. The head is not updated when list is empty

C. The while loop condition is incorrect

D. The line temp = newNode; does not link the new node to the list

Solution

1. Step 1: Analyze the while loop

   The loop finds the last node where temp.next == null.

2. Step 2: Check how new node is linked

   Assigning temp = newNode; only changes local variable, not the last node's next pointer.

3. Step 3: Correct linking

   Should assign temp.next = newNode; to link new node at end.

4. Final Answer:

   The line temp = newNode; does not link the new node to the list -> Option D

5. Quick Check:

   Must set temp.next = newNode, not temp = newNode [OK]

Hint: Assign newNode to temp.next, not temp variable [OK]

Common Mistakes:

• Assigning newNode to temp instead of temp.next
• Not updating head when list empty
• Incorrect loop condition causing infinite loop

5. You have a singly linked list with nodes: 5 -> 15 -> 25 -> null. You want to insert a new node with value 35 at the end. After insertion, what will be the correct sequence of nodes? Also, what changes must be made if the list is empty initially?

hard

A. Sequence: 5 -> 15 -> 25 -> null; No changes needed for empty list

B. Sequence: 35 -> 5 -> 15 -> 25 -> null; If empty, set tail = newNode only

C. Sequence: 5 -> 15 -> 25 -> 35 -> null; If empty, set head = newNode and tail = newNode

D. Sequence: 5 -> 15 -> 25 -> 35 -> null; If empty, set tail.next = newNode only

Solution

1. Step 1: Insert new node at end

   Adding 35 at end appends it after 25, so list becomes 5 -> 15 -> 25 -> 35 -> null.

2. Step 2: Handle empty list case

   If list is empty, both head and tail must point to the new node to start the list properly.

3. Final Answer:

   Sequence: 5 -> 15 -> 25 -> 35 -> null; If empty, set head = newNode and tail = newNode -> Option C

4. Quick Check:

   Insert at end appends; empty list needs head and tail set [OK]

Hint: Empty list: set head and tail to new node; else tail.next = newNode [OK]

Common Mistakes:

• Not updating both head and tail when list is empty
• Inserting new node at head instead of tail
• Only updating tail without linking new node