Insert at End Tail Insert in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tail Insert in a Linked List

What is the printed state of the linked list after inserting 4 and 5 at the end?

DSA Go

package main
import "fmt"
type Node struct {
    data int
    next *Node
}
type LinkedList struct {
    head *Node
}
func (l *LinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    if l.head == nil {
        l.head = newNode
        return
    }
    current := l.head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
}
func (l *LinkedList) PrintList() {
    current := l.head
    for current != nil {
        fmt.Printf("%d -> ", current.data)
        current = current.next
    }
    fmt.Println("null")
}
func main() {
    list := LinkedList{}
    list.InsertAtEnd(1)
    list.InsertAtEnd(2)
    list.InsertAtEnd(3)
    list.InsertAtEnd(4)
    list.InsertAtEnd(5)
    list.PrintList()
}

A null

B 5 -> 4 -> 3 -> 2 -> 1 -> null

C 1 -> 2 -> 3 -> null

D 1 -> 2 -> 3 -> 4 -> 5 -> null

💡 Hint

Think about how nodes are added at the end and how the list is printed.

The InsertAtEnd method adds new nodes at the tail. After inserting 1,2,3,4,5 in order, the list prints from head to tail showing 1 -> 2 -> 3 -> 4 -> 5 -> null.

❓ Predict Output

intermediate

Resulting List After Multiple Tail Inserts

What is the linked list state after these insertions at the end: 10, 20, 30?

DSA Go

package main
import "fmt"
type Node struct {
    data int
    next *Node
}
type LinkedList struct {
    head *Node
}
func (l *LinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    if l.head == nil {
        l.head = newNode
        return
    }
    current := l.head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
}
func (l *LinkedList) PrintList() {
    current := l.head
    for current != nil {
        fmt.Printf("%d -> ", current.data)
        current = current.next
    }
    fmt.Println("null")
}
func main() {
    list := LinkedList{}
    list.InsertAtEnd(10)
    list.InsertAtEnd(20)
    list.InsertAtEnd(30)
    list.PrintList()
}

A null

B 10 -> 20 -> 30 -> null

C 10 -> 30 -> 20 -> null

D 30 -> 20 -> 10 -> null

💡 Hint

Nodes are added at the end, so order is preserved.

Inserting 10, then 20, then 30 at the end results in the list 10 -> 20 -> 30 -> null.

🔧 Debug

advanced

Identify the Bug in Tail Insert Method

What error will occur when running this code that inserts at the end of a linked list?

DSA Go

package main
import "fmt"
type Node struct {
    data int
    next *Node
}
type LinkedList struct {
    head *Node
}
func (l *LinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    current := l.head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
}
func (l *LinkedList) PrintList() {
    current := l.head
    for current != nil {
        fmt.Printf("%d -> ", current.data)
        current = current.next
    }
    fmt.Println("null")
}
func main() {
    list := LinkedList{}
    list.InsertAtEnd(1)
    list.PrintList()
}

A runtime error: invalid memory address or nil pointer dereference

B Compilation error: missing return statement

C Output: 1 -> null

D Output: null

💡 Hint

Check what happens if the list is empty when InsertAtEnd is called.

The InsertAtEnd method does not handle the case when the list is empty (head is nil). Accessing current.next causes a nil pointer dereference runtime error.

❓ Predict Output

advanced

Linked List State After Tail Insertions and One Removal

What is the printed linked list after inserting 7, 8, 9 at the end and then removing the head node?

DSA Go

package main
import "fmt"
type Node struct {
    data int
    next *Node
}
type LinkedList struct {
    head *Node
}
func (l *LinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    if l.head == nil {
        l.head = newNode
        return
    }
    current := l.head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
}
func (l *LinkedList) RemoveHead() {
    if l.head != nil {
        l.head = l.head.next
    }
}
func (l *LinkedList) PrintList() {
    current := l.head
    for current != nil {
        fmt.Printf("%d -> ", current.data)
        current = current.next
    }
    fmt.Println("null")
}
func main() {
    list := LinkedList{}
    list.InsertAtEnd(7)
    list.InsertAtEnd(8)
    list.InsertAtEnd(9)
    list.RemoveHead()
    list.PrintList()
}

A 8 -> 9 -> null

B 7 -> 8 -> 9 -> null

C null

D 9 -> 8 -> null

💡 Hint

Removing the head means the first inserted node is gone.

After inserting 7,8,9, the list is 7 -> 8 -> 9 -> null. Removing the head removes 7, so the list becomes 8 -> 9 -> null.

🧠 Conceptual

expert

Time Complexity of Tail Insert in Singly Linked List

What is the time complexity of inserting a node at the end (tail) of a singly linked list without a tail pointer?

A O(log n), because of binary search to find the tail

B O(1), because insertion at the end is direct

C O(n), because you must traverse the entire list to find the end

D O(n^2), because each insertion requires traversing the list multiple times

💡 Hint

Think about how you find the last node in a singly linked list without extra pointers.

Without a tail pointer, you must start at the head and move through each node to reach the end, which takes O(n) time.

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