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.