Stack Implementation Using Linked List in DSA C

Mental Model

A stack is a collection where you add and remove items only from the top. Using a linked list means each item points to the next, so we can easily add or remove the top item.

Analogy: Imagine a stack of plates where you always put a new plate on top and take the top plate off. Each plate has a small stick pointing to the plate below it.

Top -> [Node1] -> [Node2] -> [Node3] -> null
↑
stack pointer

Dry Run Walkthrough

Input: Push 10, Push 20, Pop, Push 30 on an empty stack

Goal: Show how the stack changes step-by-step with push and pop operations using linked list nodes

Step 1: Push 10: create new node with value 10 and point it to null

Top -> [10] -> null
↑
stack pointer

Why: We start the stack with one item, so it points to null as there is nothing below

Step 2: Push 20: create new node with value 20 and point it to current top (10), then update top

Top -> [20] -> [10] -> null
↑
stack pointer

Why: New item goes on top, so it points to the old top

Step 3: Pop: remove top node (20) and update top to next node (10)

Top -> [10] -> null
↑
stack pointer

Why: Removing top means top moves down to next node

Step 4: Push 30: create new node with value 30 and point it to current top (10), then update top

Top -> [30] -> [10] -> null
↑
stack pointer

Why: Add new item on top pointing to previous top

Result:

Top -> [30] -> [10] -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Stack structure with pointer to top node
typedef struct Stack {
    Node* top;
} Stack;

// Initialize stack
void initStack(Stack* s) {
    s->top = NULL;
}

// Push operation: add new node on top
void push(Stack* s, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = s->top; // new node points to old top
    s->top = newNode;       // update top to new node
}

// Pop operation: remove top node and return its value
int pop(Stack* s) {
    if (s->top == NULL) {
        printf("Stack is empty\n");
        return -1; // indicate empty stack
    }
    Node* temp = s->top;
    int poppedValue = temp->data;
    s->top = s->top->next; // move top down
    free(temp);            // free removed node
    return poppedValue;
}

// Print stack from top to bottom
void printStack(Stack* s) {
    Node* curr = s->top;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("null\n");
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    printStack(&s); // Expected: 20 -> 10 -> null

    int val = pop(&s);
    printf("Popped: %d\n", val);
    printStack(&s); // Expected: 10 -> null

    push(&s, 30);
    printStack(&s); // Expected: 30 -> 10 -> null

    return 0;
}

newNode->next = s->top; // new node points to old top

link new node to current top to maintain stack order

s->top = newNode; // update top to new node

update stack top pointer to new node

if (s->top == NULL) { ... }

check if stack is empty before pop

s->top = s->top->next; // move top down

remove top node by moving top pointer to next node

Output

20 -> 10 -> null

Popped: 20

10 -> null

30 -> 10 -> null

Complexity Analysis

Time: O(1) for push and pop because we only add or remove the top node without traversing

Space: O(n) where n is number of elements because each element uses one node in memory

vs Alternative: Compared to array-based stack, linked list stack avoids fixed size limits and shifting elements, making push/pop always O(1)

Edge Cases

Pop from empty stack

Prints 'Stack is empty' and returns -1 without crashing

DSA C

if (s->top == NULL) { printf("Stack is empty\n"); return -1; }

Push on empty stack

Creates first node and sets top to it correctly

DSA C

newNode->next = s->top; s->top = newNode;

When to Use This Pattern

When you need a last-in-first-out (LIFO) structure with dynamic size, use a stack with linked list to efficiently add and remove from the top.

Common Mistakes

Mistake: Not updating the top pointer after push or pop
Fix: Always assign s->top to the new node after push and to next node after pop

Mistake: Not handling empty stack in pop leading to null pointer errors
Fix: Check if s->top is NULL before popping and handle gracefully

Summary

Implements a stack using a linked list where push and pop happen at the head node.

Use when you want a flexible stack without size limits and fast push/pop operations.

The key is always adding or removing nodes at the top pointer to keep operations simple and fast.