Stack Implementation Using Linked List in DSA C - Time & Space Complexity

Time Complexity: Stack Implementation Using Linked List

O(1)

Understanding Time Complexity

We want to understand how fast stack operations run when using a linked list.

Specifically, how does the time to push or pop items change as the stack grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Push operation in stack using linked list
void push(Node** top, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = *top;
    *top = newNode;
}

// Pop operation in stack using linked list
int pop(Node** top) {
    if (*top == NULL) return -1; // stack empty
    Node* temp = *top;
    int val = temp->data;
    *top = temp->next;
    free(temp);
    return val;
}
    

This code adds or removes items at the start of the linked list to simulate stack push and pop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing one node at the head of the linked list.
• How many times: Each push or pop does this once, no loops involved.

How Execution Grows With Input

Each push or pop takes the same steps no matter how many items are in the stack.

Input Size (n)	Approx. Operations
10	5 steps (allocate, assign, link, update pointer, free)
100	5 steps (same as above)
1000	5 steps (same as above)

Pattern observation: The number of steps stays the same regardless of stack size.

Final Time Complexity

Time Complexity: O(1)

This means push and pop operations take constant time no matter how big the stack is.

Common Mistake

[X] Wrong: "Push or pop takes longer as the stack grows because more nodes exist."

[OK] Correct: Push and pop only change the top node, so they do not need to look at other nodes.

Interview Connect

Knowing that stack operations with linked lists run in constant time shows you understand efficient data structure design.

Self-Check

"What if we implemented the stack using an array instead of a linked list? How would the time complexity change for push and pop?"