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

Time Complexity: Insert at Beginning of Circular Linked List

O(n)

Understanding Time Complexity

We want to understand how long it takes to add a new node at the start of a circular linked list.

How does the time needed change as the list grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

void insertAtBeginning(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 adds a new node at the start of a circular linked list, updating links to keep the circle intact.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that finds the last node in the list.
• How many times: It runs once for each node until it reaches the last node, so it runs n times if the list has n nodes.

How Execution Grows With Input

As the list gets bigger, the loop runs more times to find the last node.

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

Pattern observation: The number of steps grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the beginning grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Inserting at the beginning is always O(1) because we just change the head pointer."

[OK] Correct: In a circular linked list, we must also update the last node's next pointer, which requires finding the last node by traversing the list, taking O(n) time.

Interview Connect

Understanding this helps you explain how linked list operations can vary in cost depending on the structure, showing your grasp of data structure details.

Self-Check

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