Create a Circular Singly Linked List in DSA Go - Execution Trace

Concept Flow - Create a Circular Singly Linked List

Create new node

↓

Is list empty?

No→Traverse to last node

↓

Set last.next = new node

↓

Set head = new node

↓

Set new node.next = head

↓

Done

Start by creating a new node. If the list is empty, set head to new node and point new node to itself. Otherwise, find the last node and link it to the new node, then link new node back to head.

Execution Sample

DSA Go

type Node struct {
    data int
    next *Node
}

func Insert(head *Node, val int) *Node {
    newNode := &Node{data: val}
    if head == nil {
        newNode.next = newNode
        return newNode
    }
    curr := head
    for curr.next != head {
        curr = curr.next
    }
    curr.next = newNode
    newNode.next = head
    return head
}

This code inserts a new node into a circular singly linked list, handling empty and non-empty cases.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with value 10	None	newNode created	null
2	Check if list is empty (head == nil)	None	head is nil	null
3	Set newNode.next = newNode (self-loop)	10	newNode.next -> newNode	10 -> 10 (circular)
4	Return newNode as head	10	head = newNode	10 -> 10 (circular)
5	Create new node with value 20	10	newNode created	10 -> 10 (circular)
6	Check if list is empty (head != nil)	10	head not nil	10 -> 10 (circular)
7	Traverse to last node (curr.next != head)	10	curr moves from 10 to 10 (loop ends)	10 -> 10 (circular)
8	Set last node's next to newNode	10, 20	10.next -> newNode	10 -> 20
9	Set newNode.next to head	10, 20	20.next -> 10	10 -> 20 -> 10 (circular)
10	Return head	10, 20	head unchanged	10 -> 20 -> 10 (circular)
11	Create new node with value 30	10, 20	newNode created	10 -> 20 -> 10 (circular)
12	Traverse to last node	10, 20	curr moves 10 -> 20	10 -> 20 -> 10 (circular)
13	Set last node's next to newNode	10, 20, 30	20.next -> newNode	10 -> 20 -> 30
14	Set newNode.next to head	10, 20, 30	30.next -> 10	10 -> 20 -> 30 -> 10 (circular)
15	Return head	10, 20, 30	head unchanged	10 -> 20 -> 30 -> 10 (circular)
16	Stop	10, 20, 30	Insertion complete	10 -> 20 -> 30 -> 10 (circular)

💡 Insertion stops after adding all nodes; list is circular with last node pointing to head.

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
head	nil	Node(10)	Node(10)	Node(10)	Node(10)
newNode	nil	Node(10)	Node(20)	Node(30)	Node(30)
curr	nil	nil	Node(10)	Node(20)	Node(20)

Key Moments - 3 Insights

Why do we set newNode.next = newNode when the list is empty?

Because in a circular list with one node, the node points to itself. See execution_table step 3 where newNode.next points to newNode, making the list circular.

Why do we traverse until curr.next == head instead of curr == nil?

In a circular list, there is no nil at the end. The last node points back to head. So we stop when curr.next == head to find the last node. See execution_table step 7 and 12.

How does the list remain circular after inserting new nodes?

After inserting, we set the new node's next pointer to head, and the previous last node's next pointer to the new node. This keeps the circle intact. See execution_table steps 9 and 14.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does newNode.next point to?

A head

B newNode itself

C nil

D previous node

💡 Hint

Check the Pointer Changes and Visual State columns at step 3.

At which step does the list first become circular?

A Step 3

B Step 1

C Step 9

D Step 15

💡 Hint

Look for when newNode.next points to itself or head in the Visual State column.

If we skip setting newNode.next = head in step 9, what happens to the list?

A Head becomes nil

B List remains circular

C List becomes linear ending at newNode

D Last node points to itself

💡 Hint

Refer to Pointer Changes in step 9 and the importance of linking newNode back to head.

Concept Snapshot

Create Circular Singly Linked List:
- Create new node
- If empty, point newNode.next to itself and set head
- Else, find last node (curr.next == head)
- Set last.next = newNode
- Set newNode.next = head
- List remains circular after each insertion

Full Transcript

To create a circular singly linked list, start by making a new node. If the list is empty, point this new node to itself and make it the head. If not empty, find the last node by moving until the next node is the head. Then, link the last node's next to the new node, and the new node's next back to the head. This keeps the list circular. Each insertion updates pointers carefully to maintain the circle.

Practice

1. What is a key characteristic of a circular singly linked list compared to a regular singly linked list?

easy

A. The last node points back to the first node, forming a circle.

B. Each node has two pointers, one to the next and one to the previous node.

C. It uses an array internally to store nodes.

D. Nodes are stored in sorted order automatically.

Solution

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

   In a circular singly linked list, the last node's next pointer points back to the first node, creating a loop.

2. Step 2: Compare with other linked lists

   Unlike doubly linked lists, nodes have only one pointer. Unlike arrays, nodes are linked by pointers, not indices.

3. Final Answer:

   The last node points back to the first node, forming a circle. -> Option A

4. Quick Check:

   Circular list last node points to head = D [OK]

Hint: Last node points to head in circular singly linked list [OK]

Common Mistakes:

• Confusing circular singly linked list with doubly linked list
• Thinking nodes have two pointers
• Assuming nodes are stored in arrays

2. Which of the following Go code snippets correctly initializes a circular singly linked list with one node containing value 10?

easy

A. node := &Node{data: 10}; node.next = node

B. node := Node{data: 10}; node.next = nil

C. node := &Node{data: 10, next: nil}

D. node := &Node{data: 10}; node.next = nil

Solution

1. Step 1: Create a node pointer and assign data

   Using &Node creates a pointer to a Node struct with data 10.

2. Step 2: Make the node point to itself

   Setting node.next = node creates a circular link for a single node list.

3. Final Answer:

   node := &Node{data: 10}; node.next = node -> Option A

4. Quick Check:

   Single node points to itself = C [OK]

Hint: Single node's next points to itself for circular list [OK]

Common Mistakes:

• Setting next to nil breaks circular property
• Not using pointer for node
• Confusing struct initialization syntax

3. Given the following Go code, what will be printed?

package main
import "fmt"

type Node struct {
    data int
    next *Node
}

func main() {
    head := &Node{data: 1}
    second := &Node{data: 2}
    third := &Node{data: 3}

    head.next = second
    second.next = third
    third.next = head

    current := head
    for i := 0; i < 5; i++ {
        fmt.Print(current.data, " ")
        current = current.next
    }
}

medium

A. 1 2 3 1 1

B. 1 2 3 3 3

C. 1 2 3 1 2

D. 1 2 3 2 3

Solution

1. Step 1: Understand the circular list structure

   Nodes 1 -> 2 -> 3 -> back to 1, forming a circle.

2. Step 2: Trace the loop printing 5 nodes

   Prints: 1, then 2, then 3, then back to 1, then 2.

3. Final Answer:

   1 2 3 1 2 -> Option C

4. Quick Check:

   Loop prints nodes in circle = A [OK]

Hint: Follow next pointers in circle for 5 steps [OK]

Common Mistakes:

• Assuming list ends after 3 nodes
• Not looping back to head
• Miscounting loop iterations

4. Identify the error in this Go code that tries to create a circular singly linked list with two nodes:

package main

type Node struct {
    data int
    next *Node
}

func main() {
    first := &Node{data: 1}
    second := &Node{data: 2}

    first.next = second
    second.next = nil

    // Make it circular
    second.next = first
}

medium

A. No error, code correctly creates circular list

B. second.next is set to nil then overwritten, unnecessary step

C. second.next is set to nil before setting to first, redundant but no error

D. Missing initialization of first.next before assigning second

Solution

1. Step 1: Analyze the assignments to second.next

   Initially second.next is set to nil, then immediately overwritten to first.

2. Step 2: Identify redundancy

   Setting second.next to nil is unnecessary since it is overwritten right after.

3. Final Answer:

   second.next is set to nil then overwritten, unnecessary step -> Option B

4. Quick Check:

   Redundant assignment detected = B [OK]

Hint: Avoid redundant pointer assignments in circular list [OK]

Common Mistakes:

• Thinking nil assignment causes error
• Ignoring redundant code
• Confusing order of pointer assignments

5. You want to insert a new node with value 4 at the end of an existing circular singly linked list with nodes 1 -> 2 -> 3 -> back to 1. Which of the following Go code snippets correctly performs this insertion?

hard

A. newNode := &Node{data: 4}
current := head
for current.next != nil {
current = current.next
}
current.next = newNode
newNode.next = head

B. newNode := &Node{data: 4, next: head}
head.next = newNode

C. newNode := &Node{data: 4}
newNode.next = head
head.next = newNode

D. newNode := &Node{data: 4}
current := head
for current.next != head {
current = current.next
}
current.next = newNode
newNode.next = head

Solution

1. Step 1: Traverse to last node before head

   Loop until current.next == head to find last node in circular list.

2. Step 2: Insert new node after last node and link back to head

   Set current.next = newNode and newNode.next = head to maintain circularity.

3. Final Answer:

   Traverse to last node, link new node, then link new node back to head -> Option D

4. Quick Check:

   Proper insertion at end keeps circle intact = A [OK]

Hint: Find last node where next is head, insert new node there [OK]

Common Mistakes:

• Using nil instead of head to find last node
• Not linking new node back to head
• Incorrectly changing head pointer