Insert at End of Circular Linked List in DSA C - Time & Space Complexity

Time Complexity: Insert at End of Circular Linked List

O(n)

Understanding Time Complexity

We want to understand how the time to insert a node at the end of a circular linked list changes as the list grows.

How does the number of steps needed grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

void insertEnd(struct Node** head, int value) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = value;
    if (*head == NULL) {
        newNode->next = newNode;
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
    *head = newNode;
}
    

This code inserts a new node at the end of a circular linked list by traversing to the last node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through the list to find the last node.
• How many times: It runs once for each node until it reaches the last node, so roughly n times for a list of size n.

How Execution Grows With Input

As the list grows, the number of steps to find the last node grows linearly.

Input Size (n)	Approx. Operations
10	About 10 steps to reach the end
100	About 100 steps to reach the end
1000	About 1000 steps to reach the end

Pattern observation: The steps increase directly with the number of nodes; doubling nodes doubles the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the end grows in direct proportion to the list size.

Common Mistake

[X] Wrong: "Inserting at the end is always quick and takes constant time."

[OK] Correct: Because we must find the last node by moving through the list, which takes longer as the list grows.

Interview Connect

Understanding this helps you explain how linked list operations scale and shows you can analyze code beyond just writing it.

Self-Check

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