Stack Implementation Using Linked List in DSA Go

Mental Model

A stack is like a pile where you add and remove items only from the top. Using a linked list means each item points to the one below it.

Analogy: Imagine stacking plates: you put a new plate on top and take the top plate off first. Each plate holds a pointer to the plate below it.

Top -> [Node1] -> [Node2] -> [Node3] -> null
          ↑

Dry Run Walkthrough

Input: Push values 10, 20, 30 onto an empty stack, then pop one value

Goal: Show how the stack grows with pushes and shrinks with a pop using linked list nodes

Step 1: Push 10: create node with value 10, point it to null, set top to this node

Top -> [10] -> null
          ↑

Why: First item becomes the top of the stack

Step 2: Push 20: create node with value 20, point it to current top (10), update top to new node

Top -> [20] -> [10] -> null
          ↑

Why: New item goes on top, previous top moves down

Step 3: Push 30: create node with value 30, point it to current top (20), update top to new node

Top -> [30] -> [20] -> [10] -> null
          ↑

Why: Stack grows by adding new top node

Step 4: Pop: remove top node (30), update top to next node (20)

Top -> [20] -> [10] -> null
          ↑

Why: Removing top item reveals the next item below

Result:

Top -> [20] -> [10] -> null
          ↑
Popped value: 30

Annotated Code

DSA Go

package main

import "fmt"

// Node represents an element in the linked list stack
type Node struct {
    value int
    next  *Node
}

// Stack using linked list
type Stack struct {
    top *Node
}

// Push adds a value on top of the stack
func (s *Stack) Push(val int) {
    newNode := &Node{value: val, next: s.top} // create new node pointing to current top
    s.top = newNode                          // update top to new node
}

// Pop removes and returns the top value from the stack
func (s *Stack) Pop() (int, bool) {
    if s.top == nil { // stack empty check
        return 0, false
    }
    val := s.top.value       // get top value
    s.top = s.top.next      // move top pointer down
    return val, true
}

// PrintStack prints the stack from top to bottom
func (s *Stack) PrintStack() {
    curr := s.top
    for curr != nil {
        fmt.Printf("%d -> ", curr.value)
        curr = curr.next
    }
    fmt.Println("null")
}

func main() {
    stack := &Stack{}

    // Push 10
    stack.Push(10)
    // Push 20
    stack.Push(20)
    // Push 30
    stack.Push(30)

    stack.PrintStack() // print after pushes

    // Pop one value
    val, ok := stack.Pop()
    if ok {
        fmt.Printf("Popped value: %d\n", val)
    }

    stack.PrintStack() // print after pop
}

newNode := &Node{value: val, next: s.top} // create new node pointing to current top

create new node with value and link to current top to add on stack

s.top = newNode // update top to new node

update top pointer to new node to reflect new stack top

if s.top == nil { // stack empty check

check if stack is empty before popping

val := s.top.value // get top value

store value from top node to return

s.top = s.top.next // move top pointer down

remove top node by moving top pointer to next node

for curr != nil { fmt.Printf("%d -> ", curr.value) curr = curr.next }

traverse from top to bottom printing each node value

Output

30 -> 20 -> 10 -> null

Popped value: 30

20 -> 10 -> null

Complexity Analysis

Time: O(1) for both push and pop because we only add or remove the top node without traversal

Space: O(n) because each pushed element creates a new node stored in memory

vs Alternative: Compared to array-based stack, linked list avoids resizing but uses extra memory for pointers

Edge Cases

Pop from empty stack

Returns false and zero value without error

DSA Go

if s.top == nil { // stack empty check

When to Use This Pattern

When you need a stack with dynamic size and fast push/pop without resizing, use linked list stack implementation.

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 s.top.next after pop

Summary

Implements a stack using linked list nodes where each node points to the next below it.

Use when you want a stack that grows and shrinks dynamically without fixed size limits.

The key is to always add and remove nodes only at the top pointer for O(1) operations.

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