Traversal of Circular Linked List in DSA Go

Mental Model

A circular linked list loops back to the start, so traversal visits each node once by stopping when we return to the first node.

Analogy: Imagine walking around a circular track; you start at one point and keep walking until you come back to where you began, then you stop.

head -> 1 -> 2 -> 3 ->
↑                   ↓
← ← ← ← ← ← ← ← ← ← ←

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> back to 1 (circular), traverse all nodes

Goal: Print all nodes exactly once by traversing the circular linked list

Step 1: start at head node with value 1

head -> [curr->1] -> 2 -> 3 -> back to 1

Why: We begin traversal from the first node

Step 2: print current node value 1, move curr to next node

head -> 1 -> [curr->2] -> 3 -> back to 1

Why: Visit node 1 and move forward to node 2

Step 3: print current node value 2, move curr to next node

head -> 1 -> 2 -> [curr->3] -> back to 1

Why: Visit node 2 and move forward to node 3

Step 4: print current node value 3, move curr to next node

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

Why: Visit node 3 and move forward to head again

Step 5: curr equals head again, stop traversal

head -> 1 -> 2 -> 3 -> back to 1 (stop)

Why: We have completed one full circle, so stop

Result:

1 -> 2 -> 3 -> null

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

func traverseCircularList(head *Node) {
	if head == nil {
		return // empty list, nothing to traverse
	}
	curr := head
	for {
		fmt.Print(curr.value)
		if curr.next == head {
			break // completed full circle
		}
		fmt.Print(" -> ")
		curr = curr.next // move to next node
	}
	fmt.Print(" -> null\n")
}

func main() {
	// create circular linked list: 1 -> 2 -> 3 -> back to 1
	n1 := &Node{value: 1}
	n2 := &Node{value: 2}
	n3 := &Node{value: 3}
	n1.next = n2
	n2.next = n3
	n3.next = n1

	traverseCircularList(n1)
}

if head == nil { return }

handle empty list by stopping traversal immediately

curr := head

start traversal from head node

for {

loop until we complete one full circle

fmt.Print(curr.value)

print current node's value

if curr.next == head { break }

stop when next node is head, meaning full circle done

fmt.Print(" -> ")

print arrow between nodes

curr = curr.next

advance to next node

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 use only a few pointers regardless of list size

vs Alternative: Compared to linear linked list traversal, circular traversal requires a stopping condition to avoid infinite loops

Edge Cases

empty list (head is nil)

function returns immediately without printing

DSA Go

if head == nil { return }

single node circular list (node points to itself)

prints the single node once and stops

DSA Go

if curr.next == head { break }

When to Use This Pattern

When you see a linked list where the last node points back to the first, use circular traversal stopping when you return to the start to avoid infinite loops.

Common Mistakes

Mistake: Not checking if next node is head, causing infinite loop
Fix: Add condition to break loop when next node equals head

Mistake: Not handling empty list, causing nil pointer errors
Fix: Check if head is nil before traversal and return early

Summary

It visits each node in a circular linked list exactly once by stopping when it loops back to the start.

Use it when you need to process or print all nodes in a circular linked list without infinite looping.

The key is to stop traversal when you reach the starting node again, completing one full circle.

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