Traversal and Printing a Linked List in DSA Go

Mental Model

Go through each item in the list one by one from start to end and show its value.

Analogy: Like reading a line of people holding hands, looking at each person's face in order until the last person.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, print all values

Goal: Visit each node from the start to the end and print its value in order

Step 1: start at head node with value 1

[curr->1] -> 2 -> 3 -> null

Why: We begin traversal from the first node to print its value

Step 2: print value 1 and move to next node

1 -> [curr->2] -> 3 -> null

Why: After printing current node, move to next to continue traversal

Step 3: print value 2 and move to next node

1 -> 2 -> [curr->3] -> null

Why: Continue printing each node until the end

Step 4: print value 3 and move to next which is null

1 -> 2 -> 3 -> [curr->null]

Why: Reached end of list, stop traversal

Result:

1 -> 2 -> 3 -> null

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

func printList(head *Node) {
	curr := head
	for curr != nil {
		fmt.Print(curr.value)
		if curr.next != nil {
			fmt.Print(" -> ")
		}
		curr = curr.next
	}
	fmt.Print(" -> null\n")
}

func main() {
	// Create linked list 1 -> 2 -> 3 -> null
	node3 := &Node{value: 3, next: nil}
	node2 := &Node{value: 2, next: node3}
	node1 := &Node{value: 1, next: node2}

	printList(node1)
}

curr := head

start traversal from the head node

for curr != nil {

continue until we reach the end of the list

fmt.Print(curr.value)

print current node's value

if curr.next != nil { fmt.Print(" -> ") }

print arrow if there is a next node

curr = curr.next

move to next node to continue traversal

Output

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) because we visit each of the n nodes exactly once

Space: O(1) because we only use a pointer variable regardless of list size

vs Alternative: Compared to recursive printing which uses O(n) space on call stack, this iterative approach is more space efficient

Edge Cases

empty list (head is nil)

prints only ' -> null' indicating no nodes

DSA Go

for curr != nil {

single node list

prints the single value followed by ' -> null'

DSA Go

if curr.next != nil { fmt.Print(" -> ") }

When to Use This Pattern

When you need to visit every element in a linked list in order, use traversal with a pointer moving from head to null to process each node.

Common Mistakes

Mistake: Not checking for nil before accessing next node causing runtime error
Fix: Always check if current node is not nil before accessing its next pointer

Mistake: Printing arrow after last node causing extra arrow at end
Fix: Print arrow only if current node's next is not nil

Summary

It visits each node in the linked list from start to end and prints their values.

Use it when you want to see or process all elements in a linked list in order.

The key is to move a pointer step-by-step from the head until you reach the end (null).

Practice

1. What is the main purpose of traversing a linked list?

easy

A. To create a new linked list from scratch

B. To delete all nodes at once

C. To visit each node in the list one by one

D. To reverse the list without visiting nodes

Solution

1. Step 1: Understand traversal meaning

   Traversal means going through each node in order, starting from the head.

2. Step 2: Purpose of traversal

   Visiting each node allows us to read or process data stored in the list.

3. Final Answer:

   To visit each node in the list one by one -> Option C

4. Quick Check:

   Traversal = visiting nodes [OK]

Hint: Traversal means visiting nodes one by one [OK]

Common Mistakes:

• Confusing traversal with deletion
• Thinking traversal creates a new list
• Assuming traversal reverses the list

2. Which of the following is the correct way to start traversing a singly linked list in Go?

easy

A. for node := head; node != nil; node = node.next {}

B. for node := head; node == nil; node = node.next {}

C. for node := nil; node != head; node = node.next {}

D. for node := head.next; node != nil; node = node.prev {}

Solution

1. Step 1: Identify correct loop start and condition

   Traversal starts at head and continues while node is not nil.

2. Step 2: Correct pointer update

   Move to next node by node = node.next each iteration.

3. Final Answer:

   for node := head; node != nil; node = node.next {} -> Option A

4. Quick Check:

   Start at head, loop until nil, move next [OK]

Hint: Start at head, loop until nil, move to next [OK]

Common Mistakes:

• Using node == nil as loop condition (wrong)
• Starting from nil instead of head
• Using node.prev in singly linked list

3. What will be the output of the following Go code snippet that traverses and prints a linked list?

type Node struct {
  value int
  next  *Node
}

func main() {
  n3 := &Node{3, nil}
  n2 := &Node{2, n3}
  n1 := &Node{1, n2}
  for node := n1; node != nil; node = node.next {
    fmt.Print(node.value, " -> ")
  }
  fmt.Print("nil")
}

medium

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

B. 1 2 3 nil

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

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

Solution

1. Step 1: Understand list structure

   n1 points to n2, n2 points to n3, n3 points to nil. Values are 1, 2, 3 in order.

2. Step 2: Trace the loop output

   Loop prints node.value followed by ' -> ' for each node: 1 -> 2 -> 3 -> then prints 'nil'.

3. Final Answer:

   1 -> 2 -> 3 -> nil -> Option D

4. Quick Check:

   Print order matches list order [OK]

Hint: Print nodes in order, end with nil [OK]

Common Mistakes:

• Printing values in reverse order
• Missing '->' arrows
• Printing nil at start instead of end

4. Identify the error in this Go code snippet that tries to print a linked list:

type Node struct {
  value int
  next  *Node
}

func printList(head *Node) {
  node := head
  for node != nil {
    fmt.Println(node.value)
    node = node.prev
  }
}

medium

A. Using 'node.prev' which doesn't exist in singly linked list

B. Missing initialization of 'node' variable

C. Incorrect loop condition 'node != nil' causes infinite loop

D. fmt.Println cannot print integers directly

Solution

1. Step 1: Check struct fields

   Node struct has 'next' pointer but no 'prev' pointer.

2. Step 2: Identify incorrect pointer usage

   Code uses 'node = node.prev' which is invalid and causes compile error.

3. Final Answer:

   Using 'node.prev' which doesn't exist in singly linked list -> Option A

4. Quick Check:

   prev pointer missing in singly linked list [OK]

Hint: Singly linked list has only 'next', not 'prev' [OK]

Common Mistakes:

• Using prev pointer in singly linked list
• Assuming fmt.Println can't print ints
• Thinking loop condition is wrong

5. Given a singly linked list, how would you modify the traversal code to print only the nodes with even values?

func printEven(head *Node) {
  for node := head; node != nil; node = node.next {
    // Your code here
  }
}

hard

A. Use 'if node.value == 0 { fmt.Print(node.value) }' inside the loop

B. Add 'if node.value%2 == 0 { fmt.Print(node.value, " -> ") }' inside the loop

C. Change loop to 'for node := head; node.value%2 == 0; node = node.next {}'

D. Print all nodes and then filter even values after traversal

Solution

1. Step 1: Use conditional inside traversal

   Check if node.value is even using modulo operator inside the loop.

2. Step 2: Print only even values

   Print node.value with arrow only if condition is true.

3. Final Answer:

   Add 'if node.value%2 == 0 { fmt.Print(node.value, " -> ") }' inside the loop -> Option B

4. Quick Check:

   Condition inside loop filters even nodes [OK]

Hint: Use if condition inside loop to filter even values [OK]

Common Mistakes:

• Changing loop condition incorrectly
• Checking equality to zero instead of evenness
• Printing all nodes then filtering later