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

Concept Flow - Create a Circular Singly Linked List

Create new node with value

↓

Is list empty?

Yes→Set head and tail to new node

↓

Point new_node.next to head

↓

Set tail.next to new node

↓

Update tail to new node

↓

Done

Start by creating a new node. If the list is empty, set head and tail to this node and link it to itself. Otherwise, link the current tail to the new node, link new node back to head, and update tail.

Execution Sample

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularSinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            new_node.next = new_node
        else:
            self.tail.next = new_node
            new_node.next = self.head
            self.tail = new_node

This code creates a circular singly linked list and appends nodes, linking the last node back to the head.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create node with data=10	None	None	List is empty
2	List empty? Yes	None	None	No nodes yet
3	Set head and tail to new node	10	head -> 10, tail -> 10	10 -> ...
4	Point new_node.next to itself	10	10.next -> 10	10 -> 10 (circular)
5	Create node with data=20	10	None	10 -> 10 (circular)
6	List empty? No	10	None	10 -> 10 (circular)
7	Set tail.next to new node	10, 20	10.next -> 20	10 -> 20 -> ...
8	Set new_node.next to head	10, 20	20.next -> 10	10 -> 20 -> 10 (circular)
9	Update tail to new node	10, 20	tail -> 20	10 -> 20 -> 10 (circular)
10	Create node with data=30	10, 20	None	10 -> 20 -> 10 (circular)
11	List empty? No	10, 20	None	10 -> 20 -> 10 (circular)
12	Set tail.next to new node	10, 20, 30	20.next -> 30	10 -> 20 -> 30 -> ...
13	Set new_node.next to head	10, 20, 30	30.next -> 10	10 -> 20 -> 30 -> 10 (circular)
14	Update tail to new node	10, 20, 30	tail -> 30	10 -> 20 -> 30 -> 10 (circular)
15	End of append operations	10, 20, 30	tail -> 30	Final circular list: 10 -> 20 -> 30 -> 10

💡 All nodes appended; tail points to last node; last node points back to head forming circular list.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 9	After Step 12	After Step 14	Final
head	None	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
tail	None	Node(10)	Node(10)	Node(20)	Node(20)	Node(30)	Node(30)
new_node	None	Node(10)	Node(20)	Node(20)	Node(30)	Node(30)	Node(30)
tail.next	None	Node(10).next=Node(10)	Node(10).next=Node(20)	Node(20).next=Node(10)	Node(20).next=Node(30)	Node(30).next=Node(10)	Node(30).next=Node(10)

Key Moments - 3 Insights

Why does the new node's next point to head instead of None?

Because it's a circular list, the last node must link back to the head to keep the circle. See execution_table rows 8 and 13 where new_node.next is set to head.

What happens when the list is empty and we add the first node?

The head and tail both point to the new node, and its next points to itself to form a single-node circle. See execution_table rows 3 and 4.

Why do we update tail after linking the new node?

We update tail to keep track of the last node for future appends. This happens after linking to maintain the circle. See execution_table rows 9 and 14.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what does the node's next pointer point to?

A It points to itself

B It points to None

C It points to head

D It points to tail

💡 Hint

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

At which step does the tail pointer first update to a new node?

A Step 3

B Step 9

C Step 14

D Step 7

💡 Hint

Look at the Pointer Changes column for tail updates.

If we skip setting new_node.next to head, what would happen to the list?

A The list would no longer be circular

B The tail would point to head anyway

C The list would have two heads

D The new node would point to tail

💡 Hint

Refer to the importance of new_node.next pointing to head in the key moments and execution_table steps 8 and 13.

Concept Snapshot

Create a circular singly linked list by:
- Creating a new node
- If empty, set head and tail to new node, point next to itself
- Else, link tail.next to new node
- Link new node.next to head
- Update tail to new node
This keeps the list circular with tail linking back to head.

Full Transcript

To create a circular singly linked list, we start by making a new node. If the list is empty, we set both head and tail to this new node and make its next point to itself, forming a circle of one node. If the list already has nodes, we link the current tail's next to the new node, then link the new node's next back to the head to keep the circle intact. Finally, we update the tail pointer to the new node. This process repeats for each new node appended, maintaining the circular structure where the last node always points back to the head.

Practice

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

easy

A. It uses an array internally instead of nodes.

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

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

D. The list has a fixed size and cannot grow.

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 list types

   Unlike doubly linked lists, nodes have only one pointer. Unlike arrays, nodes are linked dynamically. The circular nature is unique to this structure where the last node points back to the first node, forming a circle.

3. Final Answer:

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

4. Quick Check:

   Circular list loops back = C [OK]

Hint: Remember: circular means last node links to first [OK]

Common Mistakes:

• Confusing circular with doubly linked list
• Thinking nodes have two pointers
• Assuming fixed size like arrays

2. Which of the following is the correct way to initialize an empty circular singly linked list in Python?

easy

A. head = None

B. head = Node(0); head.next = None

C. head = Node(0); head.next = head

D. head = []

Solution

1. Step 1: Understand empty list initialization

   An empty circular singly linked list has no nodes, so head should be None.

2. Step 2: Analyze other options

   head = Node(0); head.next = None sets next to None, which is not circular. head = Node(0); head.next = head creates a node pointing to itself, which is a single-node circular list, not empty. head = [] uses a list, not a linked list.

3. Final Answer:

   head = None -> Option A

4. Quick Check:

   Empty list head = None [OK]

Hint: Empty list means head points to nothing (None) [OK]

Common Mistakes:

• Setting head.next to None in empty list
• Creating a node when list is empty
• Using Python list [] instead of nodes

3. What will be the output of the following code snippet?

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
second = Node(2)
third = Node(3)

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

current = head
result = []
for _ in range(4):
    result.append(current.data)
    current = current.next
print(result)

medium

A. [1, 2, 3, 3]

B. [1, 2, 3, None]

C. [1, 2, 3, 1]

D. RuntimeError due to infinite loop

Solution

1. Step 1: Understand the circular link setup

   Nodes 1, 2, 3 are linked in a circle: 1->2->3->1.

2. Step 2: Trace the loop for 4 iterations

   Starting at head (1), the loop collects data: 1, then moves to 2, then 3, then back to 1.

3. Final Answer:

   [1, 2, 3, 1] -> Option C

4. Quick Check:

   Loop of 3 nodes repeated once = [1,2,3,1] [OK]

Hint: Follow next pointers carefully for given loop count [OK]

Common Mistakes:

• Assuming last node points to None
• Stopping after 3 elements instead of 4
• Confusing data values with node references

4. Identify the error in the following code that tries to create a circular singly linked list with one node:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(10)
head.next = None  # Intended to point to head for circular list

medium

A. Data value 10 is invalid for circular lists

B. Node class is missing a previous pointer

C. head should be initialized as None

D. head.next should point to head, not None

Solution

1. Step 1: Check the pointer assignment for circularity

   For a circular singly linked list with one node, the node's next must point to itself (head), not None.

2. Step 2: Analyze the given code

   The code sets head.next = None, breaking the circular link.

3. Final Answer:

   head.next should point to head, not None -> Option D

4. Quick Check:

   Single node circular list loops to itself [OK]

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

Common Mistakes:

• Setting next to None instead of head
• Confusing singly with doubly linked list
• Thinking data value affects circularity

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 code snippets correctly performs this insertion?

hard

A. new_node = Node(4)
current = head
while current.next != head:
current = current.next
current.next = new_node
new_node.next = head

B. new_node = Node(4)
new_node.next = head
head.next = new_node

C. new_node = Node(4)
head.next = new_node
new_node.next = None

D. new_node = Node(4)
current = head
while current.next != None:
current = current.next
current.next = new_node
new_node.next = head

Solution

1. Step 1: Locate the last node in the circular list

   Traverse nodes until current.next points back to head, identifying the last node.

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

   Set last node's next to new_node, then new_node's next to head to maintain circularity.

3. Final Answer:

   Traverse until current.next != head, then set current.next = new_node and new_node.next = head -> Option A

4. Quick Check:

   Traverse till last node, link new node, maintain circle [OK]

Hint: Find last node by checking next != head, then insert [OK]

Common Mistakes:

• Setting new_node.next to None breaking circularity
• Not traversing to last node correctly
• Assuming head.next is always last node