Traversal of Circular Linked List in DSA Go - Execution Trace

Concept Flow - Traversal of Circular Linked List

Start at head node

↓

Visit current node and process data

↓

Move to next node

↓

Is current node head again?

Yes→Stop traversal

↩Back to Visit current node

Start at the head node, visit each node, move to the next, and stop when you return to the head.

Execution Sample

DSA Go

head := node1
current := head
for {
  fmt.Println(current.data)
  current = current.next
  if current == head {
    break
  }
}

Traverse the circular linked list starting from head, printing each node's data once.

Execution Table

Step	Operation	Current Node Data	Pointer Changes	Visual State
1	Start traversal at head	1	current = head (node1)	1 -> 2 -> 3 -> 4 -> (back to 1)
2	Print current node data	1	none	1 -> 2 -> 3 -> 4 -> (back to 1)
3	Move to next node	2	current = current.next (node2)	1 -> 2 -> 3 -> 4 -> (back to 1)
4	Print current node data	2	none	1 -> 2 -> 3 -> 4 -> (back to 1)
5	Move to next node	3	current = current.next (node3)	1 -> 2 -> 3 -> 4 -> (back to 1)
6	Print current node data	3	none	1 -> 2 -> 3 -> 4 -> (back to 1)
7	Move to next node	4	current = current.next (node4)	1 -> 2 -> 3 -> 4 -> (back to 1)
8	Print current node data	4	none	1 -> 2 -> 3 -> 4 -> (back to 1)
9	Move to next node	1	current = current.next (node1)	1 -> 2 -> 3 -> 4 -> (back to 1)
10	Check if current == head	1	Yes, stop traversal	Traversal complete

💡 Traversal stops when current node returns to head node.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	Final
current	node1 (data=1)	node2 (data=2)	node3 (data=3)	node4 (data=4)	node1 (data=1)	Traversal ends

Key Moments - 3 Insights

Why do we stop traversal when current equals head again?

Because in a circular linked list, nodes loop back to head. Stopping when current == head prevents infinite looping. See execution_table step 10.

What if the list has only one node?

Traversal visits that single node once and stops immediately after moving back to head, same as steps 1 to 10 but with one node only.

Why do we print before moving to next node?

Printing before moving ensures we process each node exactly once. If we moved first, we might skip the head node's data.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node data at step 6?

A 4

B 2

C 3

D 1

💡 Hint

Check the 'Current Node Data' column at step 6 in execution_table.

At which step does the traversal stop because current equals head again?

A Step 8

B Step 10

C Step 9

D Step 7

💡 Hint

Look for the step where 'Check if current == head' is Yes in execution_table.

If the circular linked list had only one node, how many times would the loop run?

A Once

B Twice

C Zero times

D Infinite times

💡 Hint

Refer to key_moments about single node traversal and execution_table logic.

Concept Snapshot

Traversal of Circular Linked List:
- Start at head node
- Visit and process current node
- Move to next node
- Stop when current node is head again
- Ensures each node is visited once
- Prevents infinite loop in circular structure

Full Transcript

Traversal of a circular linked list starts at the head node. We visit the current node, process its data, then move to the next node. This repeats until we return to the head node, which signals the end of traversal. This prevents infinite loops because the list loops back to the start. If the list has only one node, we visit it once and stop. Printing happens before moving to the next node to ensure no node is skipped. The execution table shows each step with current node data and pointer changes, confirming the traversal order and stopping condition.

Practice

1. What is the main difference between a circular linked list and a regular singly linked list?

easy

A. In a circular linked list, the last node points back to the first node.

B. In a circular linked list, nodes have two pointers instead of one.

C. In a circular linked list, nodes are stored in an array.

D. In a circular linked list, the first node points to null.

Solution

1. Step 1: Understand the structure of a circular linked list

   A circular linked list connects the last node back to the first node, forming a circle.

2. Step 2: Compare with a regular singly linked list

   A regular singly linked list ends with a node pointing to null, not back to the first node.

3. Final Answer:

   In a circular linked list, the last node points back to the first node. -> Option A

4. Quick Check:

   Circular list loops back = D [OK]

Hint: Last node points to first node in circular list [OK]

Common Mistakes:

• Thinking circular list nodes have two pointers
• Confusing circular list with doubly linked list
• Assuming last node points to null

2. Which of the following Go code snippets correctly starts traversal of a circular linked list from the head node?

easy

A. current := head
for current != head {
fmt.Println(current.data)
current = current.next
}

B. current := head
for current.next != nil {
fmt.Println(current.data)
current = current.next
}

C. current := head
for current != nil {
fmt.Println(current.data)
current = current.next
if current == head {
break
}
}

D. current := head
for current != nil {
fmt.Println(current.data)
current = current.next
}

Solution

1. Step 1: Identify correct loop condition for circular list

   Traversal must stop when current returns to head to avoid infinite loop.

2. Step 2: Check code options

   current := head for current != nil { fmt.Println(current.data) current = current.next if current == head { break } } uses a break when current equals head, correctly stopping traversal.

3. Final Answer:

   current := head for current != nil { fmt.Println(current.data) current = current.next if current == head { break } } -> Option C

4. Quick Check:

   Stop when current == head = A [OK]

Hint: Stop traversal when current node equals head [OK]

Common Mistakes:

• Using nil as stop condition in circular list
• Not breaking loop causing infinite traversal
• Incorrect loop condition skipping nodes

3. What will be the output of the following Go code snippet that traverses a circular linked list with nodes containing values 10, 20, 30?

type Node struct {
    data int
    next *Node
}

func main() {
    n1 := &Node{data: 10}
    n2 := &Node{data: 20}
    n3 := &Node{data: 30}
    n1.next = n2
    n2.next = n3
    n3.next = n1

    current := n1
    for {
        fmt.Print(current.data, " ")
        current = current.next
        if current == n1 {
            break
        }
    }
}

medium

A. 20 30 10

B. 10 20 30

C. 10 20 30 10

D. Runtime error

Solution

1. Step 1: Understand the circular linked list setup

   Nodes 10 -> 20 -> 30 -> back to 10 form a circle.

2. Step 2: Trace the loop output

   Loop prints current.data then moves to next. Stops when current == n1 again, so prints 10, 20, 30 once.

3. Final Answer:

   10 20 30 -> Option B

4. Quick Check:

   Print nodes once before loop breaks = C [OK]

Hint: Print until current equals start node again [OK]

Common Mistakes:

• Printing extra node after loop break
• Starting traversal from wrong node
• Confusing output order

4. The following Go code attempts to traverse a circular linked list but causes an infinite loop. What is the error?

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

medium

A. The code should use a for-range loop instead.

B. The code should print after updating current.

C. The list is not circular, so nil check is correct.

D. The loop condition should check if current equals head to stop.

Solution

1. Step 1: Analyze loop condition for circular list

   Checking current != nil never becomes false in circular list, causing infinite loop.

2. Step 2: Correct stopping condition

   Loop should stop when current returns to head node to avoid infinite traversal.

3. Final Answer:

   The loop condition should check if current equals head to stop. -> Option D

4. Quick Check:

   Stop when current == head to avoid infinite loop [OK]

Hint: Use current == head to break loop in circular list [OK]

Common Mistakes:

• Using nil as loop end in circular list
• Not breaking loop causing infinite print
• Misplacing print statement

5. Given a circular linked list where each node contains an integer, write a Go function to find the sum of all node values. Which approach correctly handles traversal without infinite looping?

hard

A. Start from head, add node data, move to next, stop when current equals head again.

B. Start from head, add node data, move to next, stop when current is nil.

C. Use recursion without base case to sum nodes.

D. Traverse nodes twice to ensure all are counted.

Solution

1. Step 1: Understand traversal in circular linked list

   Traversal must stop when current node equals head again to avoid infinite loop.

2. Step 2: Summation logic

   Start at head, add each node's data to sum, move to next node, stop when back at head.

3. Final Answer:

   Start from head, add node data, move to next, stop when current equals head again. -> Option A

4. Quick Check:

   Stop at head to sum all nodes once [OK]

Hint: Stop traversal when current equals head to sum nodes [OK]

Common Mistakes:

• Stopping at nil causing infinite loop
• Using recursion without base case
• Traversing nodes multiple times