Stack Implementation Using Linked List in DSA C - Execution Trace

Concept Flow - Stack Implementation Using Linked List

Create new node

↓

Push operation: new_node->next = top

↓

Update top = new_node

↓

Stack grows with new top

↓

Pop operation: if top != NULL

↓

Save top node data

↓

Update top = top->next

↓

Return saved data

↓

Stack shrinks from top

The stack grows by adding new nodes at the top and shrinks by removing the top node, updating the top pointer each time.

Execution Sample

DSA C

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

struct Node* top = NULL;

void push(int x) {
  struct Node* new_node = malloc(sizeof(struct Node));
  new_node->data = x;
  new_node->next = top;
  top = new_node;
}

This code adds a new element to the top of the stack by creating a new node and updating the top pointer.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize stack	Empty	top = NULL	top -> NULL
2	Push 10	10	new_node->data=10; new_node->next=NULL; top=new_node	top -> [10] -> NULL
3	Push 20	20 -> 10	new_node->data=20; new_node->next=top; top=new_node	top -> [20] -> [10] -> NULL
4	Push 30	30 -> 20 -> 10	new_node->data=30; new_node->next=top; top=new_node	top -> [30] -> [20] -> [10] -> NULL
5	Pop	30 -> 20 -> 10	temp=top; top=top->next; free(temp)	top -> [20] -> [10] -> NULL
6	Pop	20 -> 10	temp=top; top=top->next; free(temp)	top -> [10] -> NULL
7	Pop	10	temp=top; top=top->next; free(temp)	top -> NULL
8	Pop on empty	Empty	top=NULL; cannot pop	top -> NULL

💡 Stack is empty, no more elements to pop

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8
top	NULL	[10]->NULL	[20]->[10]->NULL	[30]->[20]->[10]->NULL	[20]->[10]->NULL	[10]->NULL	NULL	NULL
new_node	N/A	[10]->NULL	[20]->[10]->NULL	[30]->[20]->[10]->NULL	N/A	N/A	N/A	N/A
temp	N/A	N/A	N/A	N/A	[30]->[20]->[10]->NULL	[20]->[10]->NULL	[10]->NULL	N/A

Key Moments - 3 Insights

Why do we update new_node->next to top before changing top?

Because new_node->next must point to the current top to keep the stack linked correctly. See step 3 where new_node->next=top before top=new_node.

What happens if we pop when the stack is empty?

The pop operation checks if top is NULL. If yes, it cannot pop and the stack remains empty as shown in step 8.

Why do we free the popped node after updating top?

We save the current top in temp, update top to top->next, then free temp to avoid memory leaks. This is shown in steps 5-7.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after step 4?

A top -> [30] -> [20] -> [10] -> NULL

B top -> [20] -> [10] -> NULL

C top -> [10] -> NULL

D top -> NULL

💡 Hint

Check the Visual State column at step 4 in the execution table.

At which step does the stack become empty again after popping all elements?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the Visual State column and see when top points to NULL after popping.

If we push 40 after step 4, what will be the new top node's data?

A 10

B 20

C 30

D 40

💡 Hint

Pushing adds a new node at the top with the pushed value, see steps 2-4 for pattern.

Concept Snapshot

Stack using linked list:
- Push: create new node, new_node->next = top, top = new_node
- Pop: save top data, top = top->next, free old top
- top points to the stack's top node
- Stack grows/shrinks at top only
- Empty stack when top == NULL

Full Transcript

This visualization shows how a stack is implemented using a linked list. We start with an empty stack where top is NULL. When we push a value, we create a new node, set its next pointer to the current top, then update top to this new node. This adds the new value at the top of the stack. When popping, we save the current top node's data, move top to the next node, and free the old top node to avoid memory leaks. The stack grows and shrinks only at the top. If we try to pop when the stack is empty (top is NULL), the operation does nothing. The execution table tracks each step, showing the nodes in the list, pointer changes, and the visual state of the stack. The variable tracker shows how the top pointer and temporary pointers change after each operation. Key moments clarify why we update pointers in a certain order and how popping works safely. The quiz questions test understanding of the stack's state at different steps and the effect of push/pop operations.

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