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.

Practice

1. What is the main advantage of implementing a stack using a linked list instead of an array?

easy

A. The stack can grow dynamically without a fixed size limit

B. It uses less memory than an array

C. It allows random access to elements

D. It is easier to sort the stack elements

Solution

1. Step 1: Understand stack size limitation in arrays

   Arrays have fixed size, so stack implemented with arrays has a maximum capacity.

2. Step 2: Linked list dynamic size

   Linked lists allocate memory dynamically, so the stack can grow as needed without fixed size.

3. Final Answer:

   The stack can grow dynamically without a fixed size limit -> Option A

4. Quick Check:

   Dynamic size = Advantage of linked list stack [OK]

Hint: Linked list stacks grow dynamically, arrays don't [OK]

Common Mistakes:

• Thinking linked list uses less memory always
• Confusing stack with queue behavior
• Assuming random access is possible in stack

2. Which of the following is the correct way to declare a node structure for a stack implemented using a linked list in C?

easy

A. struct Node { int data; struct Node next; };

B. struct Node { int data; int next; };

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

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

Solution

1. Step 1: Understand node structure for linked list

   A node must hold data and a pointer to the next node.

2. Step 2: Check pointer types

   Next must be a pointer to struct Node, not an int or struct Node itself.

3. Final Answer:

   struct Node { int data; struct Node* next; }; -> Option C

4. Quick Check:

   Node has data + pointer to next [OK]

Hint: Next pointer must be struct Node* not int or struct Node [OK]

Common Mistakes:

• Using int instead of pointer for next
• Declaring next as struct Node instead of pointer
• Using pointer for data unnecessarily

3. Consider the following C code snippet for pushing elements onto a stack implemented using a linked list:

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

// Initial stack is empty (top_ref = NULL)
push(&top, 10);
push(&top, 20);
push(&top, 30);

What will be the order of elements in the stack from top to bottom after these pushes?

medium

A. 10 -> 20 -> 30 -> NULL

B. 30 -> 20 -> 10 -> NULL

C. 20 -> 30 -> 10 -> NULL

D. NULL -> 10 -> 20 -> 30

Solution

1. Step 1: Trace first push(10)

   Stack top points to node with data 10, next is NULL.

2. Step 2: Trace second push(20) and third push(30)

   Each new node becomes top, so order is 30 (top) -> 20 -> 10 -> NULL.

3. Final Answer:

   30 -> 20 -> 10 -> NULL -> Option B

4. Quick Check:

   Last pushed is top = 30 [OK]

Hint: Last pushed is always on top in linked list stack [OK]

Common Mistakes:

• Assuming order is insertion order (FIFO)
• Confusing next pointer direction
• Forgetting top points to last pushed node

4. The following code snippet is intended to pop an element from a stack implemented using a linked list. Identify the error:

int pop(struct Node** top_ref) {
  struct Node* temp;
  int popped;
  if (*top_ref == NULL) {
    printf("Stack Underflow\n");
    return -1;
  }
  temp = *top_ref;
  popped = temp->data;
  *top_ref = temp->next;
  free(temp);
  return popped;
}

medium

A. Should update temp->next to NULL before freeing

B. Missing check for NULL before accessing temp->data

C. Should not free temp after popping

D. No error, code correctly pops the top element

Solution

1. Step 1: Check for empty stack

   Code correctly checks if *top_ref is NULL and returns underflow error.

2. Step 2: Pop operation correctness

   It saves top node, retrieves data, updates top to next node, frees old top, and returns data.

3. Final Answer:

   No error, code correctly pops the top element -> Option D

4. Quick Check:

   Pop code with free and update top is correct [OK]

Hint: Pop frees top node and updates pointer correctly [OK]

Common Mistakes:

• Forgetting to free popped node causing memory leak
• Not checking for empty stack before pop
• Incorrectly updating top pointer

5. You want to implement a function reverseStack that reverses the elements of a stack implemented using a linked list without using any extra stack or array. Which approach is correct?

hard

A. Use recursion to pop all elements, then push them back in reverse order

B. Traverse the linked list and swap data of first and last nodes repeatedly

C. Create a new linked list and copy elements in reverse order

D. Use a queue to dequeue and enqueue elements to reverse

Solution

1. Step 1: Understand constraints

   No extra stack or array allowed, so iterative copying or extra data structures are not allowed.

2. Step 2: Use recursion to reverse

   Recursion can pop all elements, then push them back in reverse order naturally using call stack.

3. Step 3: Other options use extra data or incorrect method

   Swapping data repeatedly is complex and error-prone; copying creates extra list; queue uses extra structure.

4. Final Answer:

   Use recursion to pop all elements, then push them back in reverse order -> Option A

5. Quick Check:

   Recursion reverses stack without extra data structures [OK]

Hint: Recursion uses call stack to reverse without extra structures [OK]

Common Mistakes:

• Trying to swap node data instead of rearranging nodes
• Using extra arrays or stacks against constraints
• Confusing queue usage for stack reversal