Create a Circular Singly Linked List in DSA Python - Time & Space Complexity

Time Complexity: Create a Circular Singly Linked List

O(n)

Understanding Time Complexity

When creating a circular singly linked list, it is important to understand how the time needed grows as we add more nodes.

We want to know how long it takes to build the list as its size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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

This code creates a circular singly linked list by adding nodes one by one, linking the last node back to the head.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that finds the last node before the head.
• How many times: It runs once for each node already in the list when appending a new node.

How Execution Grows With Input

Each time we add a new node, we walk through the list to find the last node.

Input Size (n)	Approx. Operations
10	About 10 steps to add the last node
100	About 100 steps to add the last node
1000	About 1000 steps to add the last node

Pattern observation: The number of steps grows roughly in a straight line with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means adding a new node takes longer as the list grows, because we must find the last node each time.

Common Mistake

[X] Wrong: "Appending a node always takes the same time, no matter how big the list is."

[OK] Correct: Because we must walk through all existing nodes to find the last one, the time grows with the list size.

Interview Connect

Understanding how adding nodes scales helps you explain trade-offs in linked list operations clearly and confidently.

Self-Check

"What if we kept a reference to the last node? How would the time complexity of appending change?"