Traversal of Circular Linked List in DSA Go - Build from Scratch

Traversal of Circular Linked List

📖 Scenario: Imagine you have a round table where people sit in a circle. You want to greet each person once by going around the table starting from a specific person.

🎯 Goal: You will create a circular linked list of people sitting around the table and write code to visit each person exactly once, printing their names in order.

📋 What You'll Learn

Create a circular linked list with exactly 4 nodes named Alice, Bob, Charlie, and Diana in that order.

Create a variable called head that points to the first node (Alice).

Write a traversal loop that visits each node starting from head and prints the name field of each node exactly once.

Print each name on its own line.

💡 Why This Matters

🌍 Real World

Circular linked lists are used in real-world applications like music playlists, round-robin scheduling, and multiplayer games where the turn passes in a circle.

💼 Career

Understanding circular linked lists helps in roles involving system design, game development, and any software that requires cyclic data processing or scheduling.

1

Create Circular Linked List Nodes

Create a struct type called Node with a name field of type string and a next field of type *Node. Then create four variables alice, bob, charlie, and diana of type Node with names "Alice", "Bob", "Charlie", and "Diana" respectively.

DSA Go

package main

import "fmt"

type Node struct {
    name string
    next *Node
}

func main() {
    // Create nodes alice, bob, charlie, diana with names
    // Your code here
}

Hint

Define the Node struct first. Then create each node variable with the exact name values.

2

Link Nodes to Form Circular List

Link the nodes so that alice.next points to bob, bob.next points to charlie, charlie.next points to diana, and diana.next points back to alice. Then create a variable called head that points to &alice.

DSA Go

package main

import "fmt"

type Node struct {
    name string
    next *Node
}

func main() {
    alice := Node{name: "Alice"}
    bob := Node{name: "Bob"}
    charlie := Node{name: "Charlie"}
    diana := Node{name: "Diana"}

    // Link nodes to form circular linked list
    // Your code here
}

Hint

Set each node's next pointer to the next node to form a circle. Then set head to point to alice.

3

Traverse the Circular Linked List

Write a for loop that starts with a variable current set to head. In the loop, print current.name. Then move current to current.next. Stop the loop when current is equal to head again after the first iteration. Use a for loop with a break statement to stop.

DSA Go

package main

import "fmt"

type Node struct {
    name string
    next *Node
}

func main() {
    alice := Node{name: "Alice"}
    bob := Node{name: "Bob"}
    charlie := Node{name: "Charlie"}
    diana := Node{name: "Diana"}

    alice.next = &bob
    bob.next = &charlie
    charlie.next = &diana
    diana.next = &alice

    head := &alice

    // Traverse the circular linked list and print each name
    // Your code here
}

Hint

Use an infinite for loop and break when you come back to head. Print the name of each node inside the loop.

4

Print the Traversal Output

Run the program to print the names of all nodes in the circular linked list in order, each on its own line.

DSA Go

package main

import "fmt"

type Node struct {
    name string
    next *Node
}

func main() {
    alice := Node{name: "Alice"}
    bob := Node{name: "Bob"}
    charlie := Node{name: "Charlie"}
    diana := Node{name: "Diana"}

    alice.next = &bob
    bob.next = &charlie
    charlie.next = &diana
    diana.next = &alice

    head := &alice

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

    // Program output is the printed names
    // No additional code needed
}

Hint

Run the program and check that the names print in order, each on its own line.

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