Stack Implementation Using Linked List in DSA Go - Execution Trace

Concept Flow - Stack Implementation Using Linked List

Create new node

↓

Push Operation

↓

Set new_node.next = top

↓

Update top = new_node

↓

Stack grows at top

↓

Pop Operation

↓

Check if top is not nil

Yes↓

Save top node data

↓

Update top = top.next

↓

Return saved data

↓

Stack shrinks from top

The stack grows and shrinks by adding or removing nodes at the top pointer of the linked list.

Execution Sample

DSA Go

type Node struct {
  data int
  next *Node
}

var top *Node = nil

func push(val int) {
  newNode := &Node{data: val, next: top}
  top = newNode
}

func pop() int {
  if top == nil {
    return -1
  }
  val := top.data
  top = top.next
  return val
}

This code pushes and pops integers on a stack implemented as a linked list by changing the top pointer.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initial state	None	top = nil	top -> nil
2	push(10)	Node(10)	newNode.next = nil; top = newNode	top -> [10] -> nil
3	push(20)	Node(20) -> Node(10)	newNode.next = top(10); top = newNode	top -> [20] -> [10] -> nil
4	push(30)	Node(30) -> Node(20) -> Node(10)	newNode.next = top(20); top = newNode	top -> [30] -> [20] -> [10] -> nil
5	pop()	Node(20) -> Node(10)	top = top.next (20)	top -> [20] -> [10] -> nil
6	pop()	Node(10)	top = top.next (10)	top -> [10] -> nil
7	pop()	None	top = top.next (nil)	top -> nil
8	pop() on empty	None	top = nil (no change)	top -> nil

💡 Execution stops after pop on empty stack returns -1 and top remains nil

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
top	nil	[10]->nil	[20]->[10]->nil	[30]->[20]->[10]->nil	[20]->[10]->nil	[10]->nil	nil	nil
stack size	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

Why do we set newNode.next = top when pushing?

Setting newNode.next = top links the new node to the current top node, so the stack keeps all previous elements connected. See step 3 in execution_table where newNode.next points to the old top.

What happens if we pop when the stack is empty?

If top is nil, pop returns -1 and does not change top. This prevents errors. See step 8 in execution_table where pop on empty stack keeps top nil.

Why does the stack grow and shrink only at the top pointer?

Because stack is LIFO, we add and remove nodes only at the top to keep order. The top pointer always points to the newest element. See how top changes in steps 2-7.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the visual state of the stack?

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

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

C top -> [10] -> nil

D top -> nil

💡 Hint

Check the Visual State column at step 4 in execution_table.

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

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the Nodes in List column and see when it shows None after popping.

If we push(40) after step 7, what will be the new visual state?

A top -> [40] -> nil

B top -> [10] -> nil

C top -> nil

D top -> [30] -> [20] -> [10] -> nil

💡 Hint

After step 7 top is nil, pushing 40 creates a new node pointing to nil.

Concept Snapshot

Stack using linked list:
- Push: create new node, set newNode.next = top, update top = newNode
- Pop: if top nil return error, else save data, update top = top.next
- Stack grows/shrinks at top pointer
- top points to newest element
- Empty stack when top is nil

Full Transcript

This visualization shows how a stack is implemented using a linked list. The stack uses a top pointer to track the newest element. When pushing, a new node is created and linked to the current top, then top is updated to this new node. When popping, the top node's data is saved, top moves to the next node, and the saved data is returned. The stack grows and shrinks only at the top. If pop is called on an empty stack (top nil), it returns -1 and does not change the stack. The execution table traces each push and pop step, showing the nodes in the list, pointer changes, and the visual state of the stack. The variable tracker shows how top and stack size change after each operation. Key moments clarify why newNode.next is set to top, what happens when popping empty, and why stack operations happen only at top. The quiz tests understanding of stack state at different steps and effects of operations. This helps beginners see exactly how the linked list changes as the stack operates.

Practice

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

easy

A. Faster access to middle elements

B. Uses less memory for small stacks

C. Dynamic size, no fixed limit on number of elements

D. Allows random access to elements

Solution

1. Step 1: Understand stack size limitation in arrays

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

2. Step 2: Linked list allows dynamic memory allocation

   Linked list nodes are created as needed, so stack size can grow or shrink dynamically without fixed limit.

3. Final Answer:

   Dynamic size, no fixed limit on number of elements -> Option C

4. Quick Check:

   Linked list stack size is dynamic = B [OK]

Hint: Linked list stacks grow dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking linked list allows random access
• Confusing memory usage for small stacks
• Assuming linked list is always faster

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

easy

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

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

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

D. type Node struct { data int; next interface{} }

Solution

1. Step 1: Understand pointer usage in linked list nodes

   Each node must point to the next node using a pointer type to avoid copying entire struct.

2. Step 2: Check each option for correct pointer declaration

   type Node struct { data int; next *Node } uses *Node pointer for next, which is correct. type Node struct { data int; next Node } uses Node (value), which causes copying. type Node struct { data *int; next *Node } uses *int for data which is unnecessary. type Node struct { data int; next interface{} } uses interface{} which is not type safe.

3. Final Answer:

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

4. Quick Check:

   Next pointer must be *Node = A [OK]

Hint: Next node must be a pointer to Node struct [OK]

Common Mistakes:

• Using value type instead of pointer for next
• Using pointer for data unnecessarily
• Using interface{} instead of concrete type

3. What will be the output of the following Go code snippet implementing a stack push and pop?

package main
import "fmt"

type Node struct {
  data int
  next *Node
}

var top *Node = nil

func push(val int) {
  newNode := &Node{data: val, next: top}
  top = newNode
}

func pop() int {
  if top == nil {
    return -1
  }
  val := top.data
  top = top.next
  return val
}

func main() {
  push(10)
  push(20)
  push(30)
  fmt.Println(pop())
  fmt.Println(pop())
}

medium

A. 30
20

B. 10
20

C. 20
30

D. 10
30

Solution

1. Step 1: Trace push operations

   push(10) makes top point to node with 10; push(20) makes top point to node with 20 -> 10; push(30) makes top point to node with 30 -> 20 -> 10.

2. Step 2: Trace pop operations

   First pop returns 30 and moves top to 20 -> 10; second pop returns 20 and moves top to 10.

3. Final Answer:

   30 20 -> Option A

4. Quick Check:

   Stack LIFO order = 30 then 20 [OK]

Hint: Stack pops last pushed value first (LIFO) [OK]

Common Mistakes:

• Confusing push order with pop order
• Returning wrong node data on pop
• Not updating top pointer after pop

4. Identify the error in this pop function for a stack implemented using linked list in Go:

func pop() int {
  if top.next == nil {
    return -1
  }
  val := top.data
  top = top.next
  return val
}

medium

A. It does not check if top is nil before accessing top.next

B. It returns -1 incorrectly when stack is empty

C. It does not update top pointer after pop

D. It returns the wrong value from the stack

Solution

1. Step 1: Analyze nil checks in pop function

   The function checks if top.next == nil but does not check if top itself is nil, which can cause runtime panic if stack is empty.

2. Step 2: Understand correct empty stack check

   Correct check is if top == nil to detect empty stack before accessing top.next.

3. Final Answer:

   It does not check if top is nil before accessing top.next -> Option A

4. Quick Check:

   Check top == nil before top.next [OK]

Hint: Always check top == nil before accessing top.next [OK]

Common Mistakes:

• Checking top.next before top
• Returning wrong error value
• Forgetting to update top pointer

5. Given a stack implemented using a linked list, how would you implement a function to reverse the stack using only stack operations (push and pop) and no extra data structures?

hard

A. Traverse linked list and swap data values pairwise

B. Use a temporary array to store elements, then push back

C. Create a new stack and push elements popped from original stack

D. Use recursion: pop all elements, then push them back in reverse order

Solution

1. Step 1: Understand constraints of no extra data structures

   Using only push and pop means no arrays or new stacks allowed; recursion uses call stack implicitly.

2. Step 2: Use recursion to pop all elements and then push back in reverse

   Recursively pop elements until stack is empty, then insert elements at bottom recursively to reverse order.

3. Final Answer:

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

4. Quick Check:

   Recursion reverses stack without extra data structures [OK]

Hint: Recursion can reverse stack using call stack only [OK]

Common Mistakes:

• Using extra arrays or stacks violating constraints
• Trying to swap node data directly
• Not handling empty stack base case in recursion