Creating a Singly Linked List from Scratch in DSA Go - Debugging & Practice

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inserting Nodes at the End

What is the printed state of the singly linked list after inserting nodes with values 10, 20, and 30 at the end?

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type LinkedList struct {
    head *Node
}

func (l *LinkedList) InsertEnd(val int) {
    newNode := &Node{value: val}
    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.value)
        current = current.next
    }
    fmt.Println("null")
}

func main() {
    list := LinkedList{}
    list.InsertEnd(10)
    list.InsertEnd(20)
    list.InsertEnd(30)
    list.PrintList()
}

A 10 -> 20 -> 30 -> null

B 30 -> 20 -> 10 -> null

C 10 -> 30 -> 20 -> null

D null

💡 Hint

Think about how nodes are added at the end and how the list is printed from head to tail.

Nodes are inserted at the end, so the order is the same as insertion: 10, then 20, then 30. The print starts from head and moves forward.

❓ Predict Output

intermediate

Output After Deleting the Head Node

What is the printed state of the singly linked list after deleting the head node from the list 5 -> 15 -> 25 -> null?

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type LinkedList struct {
    head *Node
}

func (l *LinkedList) DeleteHead() {
    if l.head != nil {
        l.head = l.head.next
    }
}

func (l *LinkedList) PrintList() {
    current := l.head
    for current != nil {
        fmt.Printf("%d -> ", current.value)
        current = current.next
    }
    fmt.Println("null")
}

func main() {
    list := LinkedList{
        head: &Node{value: 5, next: &Node{value: 15, next: &Node{value: 25}}},
    }
    list.DeleteHead()
    list.PrintList()
}

A 25 -> null

B 5 -> 15 -> 25 -> null

C 15 -> 25 -> null

D null

💡 Hint

Deleting the head means the second node becomes the new head.

After deleting the head (5), the new head is 15, so the list is 15 -> 25 -> null.

🔧 Debug

advanced

Identify the Bug in Node Insertion at Beginning

What error will occur when running this code that tries to insert a node at the beginning of the singly linked list?

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type LinkedList struct {
    head *Node
}

func (l *LinkedList) InsertBeginning(val int) {
    newNode := &Node{value: val}
    newNode.next = l.head
    l.head = newNode
}

func (l *LinkedList) PrintList() {
    current := l.head
    for current != nil {
        fmt.Printf("%d -> ", current.value)
        current = current.next
    }
    fmt.Println("null")
}

func main() {
    var list *LinkedList
    list.InsertBeginning(100)
    list.PrintList()
}

A runtime error: invalid memory address or nil pointer dereference

B Output: 100 -> null

C Compilation error: cannot call method on nil pointer

D Output: null

💡 Hint

Check how the list variable is initialized before calling methods.

The list variable is nil, so calling InsertBeginning on it causes a runtime nil pointer dereference error.

❓ Predict Output

advanced

Output After Reversing a Singly Linked List

What is the printed state of the singly linked list after reversing the list 1 -> 2 -> 3 -> 4 -> null?

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type LinkedList struct {
    head *Node
}

func (l *LinkedList) Reverse() {
    var prev *Node
    current := l.head
    for current != nil {
        nextNode := current.next
        current.next = prev
        prev = current
        current = nextNode
    }
    l.head = prev
}

func (l *LinkedList) PrintList() {
    current := l.head
    for current != nil {
        fmt.Printf("%d -> ", current.value)
        current = current.next
    }
    fmt.Println("null")
}

func main() {
    list := LinkedList{
        head: &Node{value: 1, next: &Node{value: 2, next: &Node{value: 3, next: &Node{value: 4}}}},
    }
    list.Reverse()
    list.PrintList()
}

A 1 -> 2 -> 3 -> 4 -> null

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

C null

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

💡 Hint

Reversing flips the order of nodes from head to tail.

The reverse function changes the links so the last node becomes the head, reversing the list order.

🧠 Conceptual

expert

Number of Nodes After Multiple Insertions and Deletions

Starting with an empty singly linked list, the following operations are performed in order: 1. Insert 5 nodes at the beginning 2. Insert 3 nodes at the end 3. Delete 4 nodes from the beginning 4. Insert 2 nodes at the beginning How many nodes remain in the list after these operations?

A 3

B 5

C 4

D 6

💡 Hint

Count nodes after each step carefully.

After step 1: 5 nodes After step 2: 8 nodes After step 3: 4 nodes (8 - 4) After step 4: 6 nodes (4 + 2)

Practice

1. What is the main purpose of a singly linked list in data structures?

easy

A. To store elements in a hash table for fast lookup

B. To store elements in a tree-like structure with multiple branches

C. To store elements in a fixed-size array for quick access

D. To store elements in a linear order where each element points to the next

Solution

1. Step 1: Understand singly linked list structure

   A singly linked list stores elements in nodes where each node points to the next node, forming a chain.

2. Step 2: Compare with other data structures

   Unlike trees or arrays, singly linked lists have a linear sequence with pointers only to the next element.

3. Final Answer:

   To store elements in a linear order where each element points to the next -> Option D

4. Quick Check:

   Singly linked list = linear chain with next pointers [OK]

Hint: Remember: singly linked list nodes point only forward [OK]

Common Mistakes:

• Confusing singly linked list with trees or arrays
• Thinking nodes have pointers to previous nodes
• Assuming fixed size storage like arrays

2. Which of the following is the correct way to define a node struct for a singly linked list in Go?

easy

A. type Node struct { value int; next *Node }

B. type Node struct { value int; prev *Node }

C. type Node struct { value int; next Node }

D. type Node struct { value int; next interface{} }

Solution

1. Step 1: Identify correct pointer usage

   In Go, the next node must be a pointer to Node, so *Node is correct.

2. Step 2: Check struct fields

   Field 'value' stores data, 'next' points to the next node. 'prev' is for doubly linked lists, and 'interface{}' is too generic.

3. Final Answer:

   type Node struct { value int; next *Node } -> Option A

4. Quick Check:

   Node next pointer = *Node [OK]

Hint: Use *Node for next pointer in Go struct [OK]

Common Mistakes:

• Using value type instead of pointer for next
• Confusing singly linked list with doubly linked list (prev pointer)
• Using interface{} instead of *Node for next

3. What will be the output of the following Go code that creates a singly linked list with nodes 1 -> 2 -> 3?

package main
import "fmt"
type Node struct {
  value int
  next  *Node
}
func main() {
  head := &Node{value: 1}
  second := &Node{value: 2}
  third := &Node{value: 3}
  head.next = second
  second.next = third
  current := head
  for current != nil {
    fmt.Print(current.value)
    if current.next != nil {
      fmt.Print(" -> ")
    }
    current = current.next
  }
  fmt.Println(" -> null")
}

medium

A. 1 -> 2 -> null

B. 3 -> 2 -> 1 -> null

C. 1 -> 2 -> 3 -> null

D. Compilation error

Solution

1. Step 1: Trace node creation and linking

   Nodes with values 1, 2, 3 are created and linked in order: head.next = second, second.next = third.

2. Step 2: Trace printing loop

   Loop prints current.value, then ' -> ' if next exists, moving from head to third, then prints ' -> null'.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option C

4. Quick Check:

   Print nodes in order 1,2,3 with arrows [OK]

Hint: Follow next pointers from head to end [OK]

Common Mistakes:

• Printing nodes in reverse order
• Missing last node in output
• Confusing pointer assignments causing nil errors

4. Identify the error in this Go code snippet that tries to append a new node with value 4 to the end of a singly linked list:

func appendNode(head *Node, val int) {
  newNode := &Node{value: val}
  current := head
  for current.next != nil {
    current = current.next
  }
  current = newNode
}

medium

A. The loop condition should be current != nil instead of current.next != nil

B. The new node is not linked to the list; current pointer is reassigned incorrectly

C. The new node should be created with next pointing to head

D. The function should return the new head pointer

Solution

1. Step 1: Analyze the loop and pointer update

   The loop correctly finds the last node where current.next is nil.

2. Step 2: Check how new node is linked

   Assigning current = newNode only changes the local variable, not the last node's next pointer. It should be current.next = newNode.

3. Final Answer:

   The new node is not linked to the list; current pointer is reassigned incorrectly -> Option B

4. Quick Check:

   Link new node by current.next = newNode [OK]

Hint: Assign new node to current.next, not current [OK]

Common Mistakes:

• Reassigning current instead of current.next
• Wrong loop condition causing nil pointer dereference
• Not returning updated head when needed

5. You want to create a function in Go that reverses a singly linked list. Which approach correctly reverses the list by changing the next pointers?

func reverseList(head *Node) *Node {
  var prev *Node = nil
  current := head
  for current != nil {
    nextTemp := current.next
    current.next = prev
    prev = current
    current = nextTemp
  }
  return prev
}

What will be the output if the original list is 1 -> 2 -> 3 -> null and you print the reversed list?

hard

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. null

D. Runtime error due to nil pointer

Solution

1. Step 1: Understand reversal logic

   The function iterates through the list, reversing each node's next pointer to point to the previous node.

2. Step 2: Trace reversal on list 1 -> 2 -> 3

   After reversal, the list becomes 3 -> 2 -> 1 -> null, and prev points to new head.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option A

4. Quick Check:

   Reversed list head = prev = 3 [OK]

Hint: Reverse pointers by tracking prev, current, next [OK]

Common Mistakes:

• Not updating current.next correctly
• Losing track of next node causing infinite loop
• Returning old head instead of new head