Insert at End Tail Insert in DSA Go - Execution Trace

Concept Flow - Insert at End Tail Insert

Create new node

↓

Is list empty?

↓

Set head

↓

Traverse until current.next == nil

↓

Set current.next = new node

↓

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.

Execution Sample

DSA Go

type Node struct {
    data int
    next *Node
}

func InsertAtEnd(head *Node, val int) *Node {
    newNode := &Node{data: val}
    if head == nil {
        return newNode
    }
    current := head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
    return head
}

This code inserts a new node with given value at the end of a singly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	∅	newNode → Node(data:10, next:∅)	∅
2	Check if head is nil (empty list)	∅	head = nil	List empty
3	Set head = newNode (list was empty)	Node(10)	head → newNode	┌────────┐ │ data:10│ │ next:∅ │ └────────┘ head
4	Create new node with data=20	Node(10)	newNode → Node(data:20, next:∅)	┌────────┐ │ data:10│ │ next:∅ │ └────────┘ head
5	Check if head is nil (not empty)	Node(10)	head → Node(10)	List not empty
6	Start traversal at head	Node(10)	current → head	current points to Node(10)
7	Check current.next (nil?)	Node(10)	current.next = nil	At last node
8	Set current.next = newNode (insert at end)	Node(10) → Node(20)	current.next → newNode	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ head new tail
9	Create new node with data=30	Node(10) → Node(20)	newNode → Node(data:30, next:∅)	List with two nodes
10	Start traversal at head	Node(10) → Node(20)	current → head	current points to Node(10)
11	Check current.next (not nil)	Node(10) → Node(20)	current.next → Node(20)	Move current to next
12	Move current to next node	Node(10) → Node(20)	current → Node(20)	current points to Node(20)
13	Check current.next (nil?)	Node(10) → Node(20)	current.next = nil	At last node
14	Set current.next = newNode (insert at end)	Node(10) → Node(20) → Node(30)	current.next → newNode	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│───→│ data:20│───→│ data:30│ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ head new tail
15	End of insertions	Node(10) → Node(20) → Node(30)	No pointer changes	Final list state

💡 Traversal stops when current.next is nil, meaning current is last node.

Variable Tracker

Variable	Start	After Step 3	After Step 8	After Step 14	Final
head	nil	Node(10)	Node(10)	Node(10)	Node(10)
newNode	nil	nil	Node(20)	Node(30)	Node(30)
current	nil	nil	Node(10)	Node(20)	Node(20)

Key Moments - 3 Insights

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

Because we want to stop at the last node, not after it. current.next == nil means current is last node where we insert new node. See execution_table step 7 and 13.

What happens if the list is empty when inserting?

If head is nil, we set head to newNode directly, making the new node the first and only node. See execution_table step 3.

How does the pointer change when inserting at the end?

The last node's next pointer changes from nil to point to the new node. See execution_table steps 8 and 14 with pointer updates.

Visual Quiz - 3 Questions

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

A nil

B Node with data 10

C Node with data 20

D Node with data 30

💡 Hint

Check variable_tracker and execution_table rows 12 and 13 for current pointer updates.

At which step does the list first have two nodes linked?

A Step 3

B Step 8

C Step 14

D Step 6

💡 Hint

Look at execution_table step 8 where current.next is set to newNode for the first time.

If the initial list is empty, what will be the head after inserting the first node?

A Points to new node with data

B nil

C Points to nil

D Points to old head

💡 Hint

See execution_table step 3 where head is assigned newNode when list is empty.

Concept Snapshot

Insert at End (Tail Insert) in singly linked list:
- Create new node with data
- If list empty (head == nil), set head = new node
- Else traverse from head until last node (current.next == nil)
- Set last node's next pointer to new node
- New node's next is nil (tail)
- List size increases by one

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 (head is nil), the new node becomes the head. Otherwise, we start from the head and move through nodes until we find the last node, identified by its next pointer being nil. Then, we set the last node's next pointer to the new node, effectively adding it at the end. The new node's next pointer is nil, marking it as the new tail. This process increases the list size by one. The execution table traces each step, showing pointer changes and the visual state of the list after each insertion.

Practice

1. What does the "Insert at End (Tail Insert)" operation do in a singly linked list?

easy

A. Deletes the last node of the list

B. Adds a new node at the beginning of the list

C. Adds a new node at the end of the list

D. Deletes the first node of the list

Solution

1. Step 1: Understand the operation name

   "Insert at End" means adding a new element at the tail or last position of the list.

2. Step 2: Compare with other options

   Adding at the beginning is different, and deleting nodes is not insertion.

3. Final Answer:

   Adds a new node at the end of the list -> Option C

4. Quick Check:

   Insert at End = Add node at tail [OK]

Hint: Tail insert means add new node after last node [OK]

Common Mistakes:

• Confusing insert at end with insert at beginning
• Thinking it deletes nodes
• Assuming it inserts in the middle

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

easy

A. newNode := Node{value, nil}

B. newNode := &Node{data: value, next: nil}

C. newNode := &Node{value}

D. newNode := Node{data: value}

Solution

1. Step 1: Understand Go struct initialization

   In Go, to create a pointer to a struct with named fields, use &Node{field: value, ...}.

2. Step 2: Check each option

   newNode := &Node{data: value, next: nil} correctly uses &Node with named fields and sets next to nil for tail node.

3. Final Answer:

   newNode := &Node{data: value, next: nil} -> Option B

4. Quick Check:

   Pointer to struct with named fields = newNode := &Node{data: value, next: nil} [OK]

Hint: Use &Node{field: val, next: nil} to create tail node [OK]

Common Mistakes:

• Missing & to create pointer
• Not setting next to nil for tail
• Using unnamed fields incorrectly

3. What will be the printed linked list after inserting 4 at the end of the list 1 -> 2 -> 3 -> nil using tail insert?

medium

A. 1 -> 2 -> 3 -> 4 -> nil

B. 4 -> 1 -> 2 -> 3 -> nil

C. 1 -> 2 -> 4 -> 3 -> nil

D. 1 -> 2 -> 3 -> nil

Solution

1. Step 1: Understand tail insert effect

   Inserting 4 at the end adds it after 3, so list becomes 1 -> 2 -> 3 -> 4 -> nil.

2. Step 2: Compare options

   Only 1 -> 2 -> 3 -> 4 -> nil shows 4 at the end; others show wrong order or no change.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> nil -> Option A

4. Quick Check:

   Tail insert adds node at end [OK]

Hint: Tail insert appends new node after last node [OK]

Common Mistakes:

• Inserting at beginning instead of end
• Inserting in the middle
• Not updating last node's next pointer

4. Given the following Go code snippet for tail insertion, what is the error?

func InsertAtEnd(head *Node, value int) *Node {
    newNode := &Node{data: value, next: nil}
    if head == nil {
        head = newNode
    } else {
        temp := head
        for temp.next != nil {
            temp = temp.next
        }
        temp = newNode
    }
    return head
}

medium

A. temp = newNode does not link newNode to the list

B. head is not updated when list is empty

C. newNode is not created properly

D. Loop condition should be temp != nil

Solution

1. Step 1: Analyze the loop and insertion

   The loop finds the last node (temp.next == nil). Then temp = newNode only changes temp pointer, not the last node's next.

2. Step 2: Identify correct linking

   To insert, we must set temp.next = newNode, not temp = newNode.

3. Final Answer:

   temp = newNode does not link newNode to the list -> Option A

4. Quick Check:

   Link last node's next to newNode [OK]

Hint: Set lastNode.next = newNode, not lastNode = newNode [OK]

Common Mistakes:

• Assigning newNode to temp instead of temp.next
• Not handling empty list correctly
• Wrong loop condition

5. You have a singly linked list and want to insert multiple values [5, 10, 15] at the end one by one using tail insert. Which approach is most efficient?

hard

A. Traverse from head to end for each insertion

B. Create a new list for each value and merge later

C. Insert each new node at the beginning

D. Keep a tail pointer to last node and update it on each insert

Solution

1. Step 1: Understand repeated tail insert cost

   Traversing from head to end for each insert is costly (O(n) per insert), total O(n^2).

2. Step 2: Use tail pointer optimization

   Keeping a tail pointer allows direct access to last node, so insertion is O(1) each, total O(n).

3. Final Answer:

   Keep a tail pointer to last node and update it on each insert -> Option D

4. Quick Check:

   Tail pointer reduces insertion time [OK]

Hint: Use tail pointer to avoid full traversal each insert [OK]

Common Mistakes:

• Traversing full list every time
• Inserting at beginning instead of end
• Creating multiple lists unnecessarily