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

Traversal of Circular Linked List

📖 Scenario: Imagine you have a group of friends sitting around a round table. You want to greet each friend one by one, starting from a specific friend and going around the table until you come back to the same friend.

🎯 Goal: You will create a circular linked list representing friends sitting in a circle. Then, you will write code to visit each friend exactly once, starting from the first friend, and print their names.

📋 What You'll Learn

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

Use a variable to keep track of the starting node.

Write a loop to traverse the circular linked list starting from the first node and print each friend's name once.

Print the names in the order they are visited.

💡 Why This Matters

🌍 Real World

Circular linked lists are used in real life to model situations where items repeat in a cycle, like players taking turns in a game or songs playing in a loop.

💼 Career

Understanding circular linked lists helps in software development roles that involve designing efficient data structures for scheduling, buffering, and cyclic processes.

1

Create nodes for the circular linked list

Create a class called Node with an __init__ method that takes name and sets self.name = name and self.next = None. Then create four nodes named node1, node2, node3, and node4 with names 'Alice', 'Bob', 'Charlie', and 'Diana' respectively.

DSA Python

# Define Node class and create four nodes named node1, node2, node3, node4
# Your code here

Hint

Start by defining a simple Node class with name and next attributes. Then create four nodes with the exact names given.

2

Link nodes to form a circular linked list

Link the nodes to form a circular linked list by setting node1.next = node2, node2.next = node3, node3.next = node4, and node4.next = node1. Also, create a variable called start and set it to node1.

DSA Python

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

node1 = Node('Alice')
node2 = Node('Bob')
node3 = Node('Charlie')
node4 = Node('Diana')

# Link nodes to form a circle and set start to node1
# Your code here

Hint

Connect each node's next to the following node, and the last node back to the first to make a circle. Remember to set the start variable.

3

Traverse the circular linked list

Write a while loop to traverse the circular linked list starting from start. Use a variable current initialized to start. Inside the loop, print current.name, then move current to current.next. Stop the loop when current is equal to start again after the first iteration.

DSA Python

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

node1 = Node('Alice')
node2 = Node('Bob')
node3 = Node('Charlie')
node4 = Node('Diana')

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

start = node1

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

Hint

Use a loop that runs at least once and stops when you come back to the start node. Use a flag variable to track the first iteration.

4

Print the traversal result

Run the program to print the names of the friends in the order they are visited. The output should be:
Alice
Bob
Charlie
Diana

DSA Python

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

node1 = Node('Alice')
node2 = Node('Bob')
node3 = Node('Charlie')
node4 = Node('Diana')

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

start = node1

current = start
first_pass = True
while first_pass or current != start:
    print(current.name)
    current = current.next
    first_pass = False

# Run the program to see the output

Hint

Run the full program to see the names printed in order. Each name should appear 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 linked list last node points to first node [OK]

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

Common Mistakes:

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

2. Which of the following is the correct way to start traversing a circular linked list in Python?

easy

A. current = head
while current is not None:
print(current.data)
current = current.next

B. current = head
while True:
print(current.data)
current = current.next
if current == head:
break

C. current = head
for i in range(len(list)):
print(current.data)
current = current.next

D. current = head
while current.next is not None:
print(current.data)
current = current.next

Solution

1. Step 1: Understand traversal stopping condition for circular list

   Traversal must stop when current node comes back to head to avoid infinite loop.

2. Step 2: Check code options for correct loop and break condition

   current = head while True: print(current.data) current = current.next if current == head: break uses while True with break when current equals head, correctly handling circular traversal.

3. Final Answer:

   Use while True loop and break when current equals head. -> Option B

4. Quick Check:

   Stop traversal when current == head [OK]

Hint: Use break when current node equals head to stop [OK]

Common Mistakes:

• Using None as stopping condition in circular list
• Forgetting to break loop causing infinite traversal
• Using length which is not defined for linked list

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(10)
second = Node(20)
third = Node(30)

head.next = second
second.next = third
third.next = head  # circular link

current = head
count = 0
while True:
    print(current.data, end=' ')
    current = current.next
    count += 1
    if count == 4:
        break

medium

A. 10 20 30 30

B. 10 20 30

C. 10 20 30 10

D. 10 20 20 10

Solution

1. Step 1: Trace the nodes and their links

   Nodes are 10 -> 20 -> 30 -> back to 10 forming a circle.

2. Step 2: Follow the loop for 4 iterations

   Prints: 10 (count=1), 20 (2), 30 (3), 10 (4) then breaks.

3. Final Answer:

   10 20 30 10 -> Option C

4. Quick Check:

   4 prints following circular links [OK]

Hint: Count iterations to avoid infinite loop in circular list [OK]

Common Mistakes:

• Stopping after 3 prints assuming no repetition
• Printing wrong node data due to pointer confusion
• Ignoring circular link causing infinite loop

4. The following code is intended to traverse a circular linked list and print all node data once. What is the error?

current = head
while current != head:
    print(current.data)
    current = current.next

medium

A. The code will raise an AttributeError.

B. The loop will run infinitely because no break condition.

C. The code will print only the head node data once.

D. The loop never starts because current == head initially.

Solution

1. Step 1: Analyze the loop condition at start

   current is initialized to head, so current != head is False initially.

2. Step 2: Understand loop execution

   Since condition is False, loop body never executes, so no data is printed.

3. Final Answer:

   The loop never starts because current == head initially. -> Option D

4. Quick Check:

   Loop condition false at start stops loop [OK]

Hint: Check initial loop condition carefully in circular traversal [OK]

Common Mistakes:

• Assuming loop runs at least once
• Using != head as loop condition without special handling
• Not using do-while style logic for circular lists

5. You have a circular linked list with nodes containing values [5, 15, 25, 35]. Write a Python function to traverse and collect all node values in a list without infinite looping. What is the correct output of your function?

hard

A. [5, 15, 25, 35]

B. [5, 15, 25, 35, 5]

C. [15, 25, 35, 5]

D. [5, 15, 25]

Solution

1. Step 1: Traverse circular list starting at head

   Start at head node with value 5 and move to next nodes collecting values.

2. Step 2: Stop traversal when current node returns to head

   Collect values 5, 15, 25, 35 and stop before repeating 5 again.

3. Final Answer:

   [5, 15, 25, 35] -> Option A

4. Quick Check:

   Collect all unique nodes once [OK]

Hint: Stop when current node equals head to avoid repeats [OK]

Common Mistakes:

• Including head node twice causing extra element
• Stopping too early missing last node
• Infinite loop by not checking for head again