Push Using Linked List Node in DSA C - Time & Space Complexity

Time Complexity: Push Using Linked List Node

O(1)

Understanding Time Complexity

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

How does the time needed change as the list grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdlib.h>

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

void push(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}
    

This code adds a new node at the beginning of a linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Creating and linking one new node.
• How many times: Exactly once per push call, no loops or recursion.

How Execution Grows With Input

Adding a node always takes the same steps regardless of list size.

Input Size (n)	Approx. Operations
10	4 steps (allocate, assign data, link, update head)
100	4 steps (same as above)
1000	4 steps (same as above)

Pattern observation: The number of steps stays the same no matter how big the list is.

Final Time Complexity

Time Complexity: O(1)

This means adding a node at the start takes a fixed amount of time, no matter how long the list is.

Common Mistake

[X] Wrong: "Adding a node takes longer as the list grows because we have to move through the list."

[OK] Correct: We only change the head pointer and link the new node; we never traverse the list for push at the front.

Interview Connect

Knowing that push at the front is quick helps you choose the right data structure for fast insertions.

Self-Check

"What if we changed push to add a node at the end of the linked list? How would the time complexity change?"