Traversal and Printing a Linked List in DSA Go - Execution Trace

Concept Flow - Traversal and Printing a Linked List

Start at head node

↓

Is current node null?

Yes→Stop traversal

No↓

Print current node data

↓

Move to next node

↩Back to check current node

Start from the head node, check if current node exists, print its data, then move to the next node until the end.

Execution Sample

DSA Go

package main

import "fmt"

type Node struct {
    data int
    next *Node
}

func printList(head *Node) {
    current := head
    for current != nil {
        fmt.Println(current.data)
        current = current.next
    }
}

func main() {
    // Example usage
    node3 := &Node{data: 3, next: nil}
    node2 := &Node{data: 2, next: node3}
    node1 := &Node{data: 1, next: node2}
    printList(node1)
}

This code traverses a linked list from head to end, printing each node's data.

Execution Table

Step	Operation	Current Node Data	Pointer Changes	Visual State
1	Start traversal at head	1	current = head	1 -> 2 -> 3 -> nil
2	Check current != nil	1	No change	1 -> 2 -> 3 -> nil
3	Print current.data	1	No change	1 -> 2 -> 3 -> nil
4	Move current to next	2	current = current.next	1 -> 2 -> 3 -> nil
5	Check current != nil	2	No change	1 -> 2 -> 3 -> nil
6	Print current.data	2	No change	1 -> 2 -> 3 -> nil
7	Move current to next	3	current = current.next	1 -> 2 -> 3 -> nil
8	Check current != nil	3	No change	1 -> 2 -> 3 -> nil
9	Print current.data	3	No change	1 -> 2 -> 3 -> nil
10	Move current to next	nil	current = current.next	1 -> 2 -> 3 -> nil
11	Check current != nil	nil	No change	1 -> 2 -> 3 -> nil
12	Traversal ends	nil	Stop	1 -> 2 -> 3 -> nil

💡 Traversal stops when current node is nil (end of list reached).

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 10	Final
current	head (node with data 1)	node with data 2	node with data 3	nil	nil

Key Moments - 3 Insights

Why do we check if current != nil before printing?

Because if current is nil, it means we reached the end of the list and there is no node to print. This is shown in execution_table rows 2, 5, 8, and 11 where the check prevents printing nil.

What happens if the list is empty (head is nil)?

The traversal stops immediately because current starts as nil. The check current != nil fails at step 2, so no printing or moving happens.

Why do we move current to current.next after printing?

To advance to the next node in the list. Without this, the loop would print the same node repeatedly. This is shown in steps 4, 7, and 10 where current pointer moves forward.

Visual Quiz - 3 Questions

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

A Node with data 3

B Node with data 2

C nil

D Node with data 1

💡 Hint

Check the 'Pointer Changes' and 'Current Node Data' columns at step 7.

At which step does the traversal stop because current is nil?

A Step 10

B Step 11

C Step 12

D Step 9

💡 Hint

Look at the 'Operation' column where traversal ends and current is nil.

If the list had only one node, how many times would the print operation occur?

A Twice

B Once

C Zero times

D Three times

💡 Hint

Refer to the execution_table steps where printing happens for each node.

Concept Snapshot

Traversal and Printing a Linked List:
- Start at head node
- While current node is not nil:
  - Print current node data
  - Move to next node
- Stop when current is nil (end of list)
This prints all nodes in order.

Full Transcript

To traverse and print a linked list, start at the head node. Check if the current node exists. If yes, print its data and move to the next node. Repeat this until the current node is nil, which means the end of the list. This process ensures all nodes are printed in order from head to tail.

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