Stack Implementation Using Linked List in DSA C - Build from Scratch

Stack Implementation Using Linked List

📖 Scenario: Imagine you are building a simple program to manage a stack of books. You want to add and remove books in a last-in, first-out order. To do this efficiently, you will use a linked list to implement the stack.

🎯 Goal: Build a stack using a linked list in C. You will create the linked list nodes, add a configuration variable for the stack top, implement push and pop operations, and finally print the stack contents.

📋 What You'll Learn

Define a struct for the linked list node with an integer data and a pointer to the next node

Create a pointer variable called top to track the top of the stack

Implement a push function to add an element to the stack

Implement a pop function to remove the top element from the stack

Print the stack elements from top to bottom

💡 Why This Matters

🌍 Real World

Stacks are used in many real-world applications like undo features in text editors, browser history, and expression evaluation.

💼 Career

Understanding stack implementation helps in software development roles that require knowledge of data structures and memory management.

1

Define the Node Structure

Define a struct called Node with an integer data and a pointer next to another Node.

DSA C

// Define the Node struct
// Your code here

Hint

Use typedef struct Node to define the node. It should have int data and struct Node* next.

2

Create the Stack Top Pointer

Create a pointer variable called top of type Node* and initialize it to NULL.

DSA C

#include 
#include 

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

// Create the top pointer for the stack
// Your code here

Hint

Declare Node* top = NULL; to mark the stack as empty initially.

3

Implement Push and Pop Functions

Write a function void push(int value) that creates a new Node with data = value, sets its next to top, and updates top to this new node. Also write a function int pop() that removes the top node, returns its data, and updates top to the next node. If the stack is empty, return -1.

DSA C

#include 
#include 

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

Node* top = NULL;

// Implement push and pop functions
// Your code here

Hint

In push, create a new node, set its data and next, then update top. In pop, check if top is NULL, else remove the top node and return its data.

4

Print Stack Contents

Write a function void printStack() that prints the stack elements from top to bottom separated by -> and ending with NULL. Then push the values 10, 20, and 30 onto the stack and call printStack().

DSA C

#include 
#include 

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

Node* top = NULL;

void push(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

int pop() {
    if (top == NULL) {
        return -1;
    }
    int value = top->data;
    Node* temp = top;
    top = top->next;
    free(temp);
    return value;
}

// Write printStack function and push 10, 20, 30, then print
// Your code here

Hint

Traverse from top to NULL, printing each data followed by ->. After pushing 10, 20, 30, the print should show 30 -> 20 -> 10 -> NULL.

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