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

Time Complexity: Create a Circular Singly Linked List

O(n)

Understanding Time Complexity

When creating a circular singly linked list, we want to know how the time to build it grows as we add more nodes.

We ask: How does the work increase when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Node {
    int data;
    struct Node* next;
};

struct Node* createCircularList(int arr[], int n) {
    if (n == 0) return NULL;
    struct Node* head = malloc(sizeof(struct Node));
    head->data = arr[0];
    struct Node* temp = head;
    for (int i = 1; i < n; i++) {
        temp->next = malloc(sizeof(struct Node));
        temp = temp->next;
        temp->data = arr[i];
    }
    temp->next = head; // Make it circular
    return head;
}
    

This code creates a circular singly linked list from an array of integers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that creates each new node and links it.
• How many times: It runs once for each element after the first, so (n - 1) times.

How Execution Grows With Input

As the number of elements increases, the loop runs more times, adding one node each time.

Input Size (n)	Approx. Operations
10	About 9 node creations and links
100	About 99 node creations and links
1000	About 999 node creations and links

Pattern observation: The work grows directly with the number of elements; doubling n roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the list grows linearly with the number of nodes.

Common Mistake

[X] Wrong: "Creating a circular list takes more time than a normal list because of the circular link."

[OK] Correct: Adding the final link to make the list circular is just one extra step, so it does not change the overall linear time.

Interview Connect

Understanding how list creation scales helps you explain your code clearly and shows you grasp fundamental data structure costs.

Self-Check

"What if we added a step to find the last node each time before linking a new node? How would the time complexity change?"