Stack Using Linked List vs Array Stack Trade-offs in DSA Go - Trade-offs & Analysis

Mental Model

A stack stores items in order, last in first out. It can be built using a linked list or an array, each with different strengths and weaknesses.

Analogy: Think of a stack like a stack of plates. Using an array is like having a fixed-size tray where plates are stacked, while a linked list is like stacking plates one by one without a fixed tray size.

Array Stack: [bottom] 1 [2] 2 [3] 3 [top]
Linked List Stack: 3 -> 2 -> 1 -> null
(top is left side in linked list)

Dry Run Walkthrough

Input: Push 1, Push 2, Push 3, Pop, Push 4 on both Array Stack and Linked List Stack

Goal: Show how stack changes step-by-step and highlight trade-offs in resizing and memory

Step 1: Push 1 on Array Stack and Linked List Stack

Array Stack: [1] null null null
Linked List Stack: 1 -> null

Why: Start with empty stacks, add first element

Step 2: Push 2 on both stacks

Array Stack: [1] [2] null null
Linked List Stack: 2 -> 1 -> null

Why: Add second element on top

Step 3: Push 3 on both stacks

Array Stack: [1] [2] [3] null
Linked List Stack: 3 -> 2 -> 1 -> null

Why: Add third element on top

Step 4: Pop top element from both stacks

Array Stack: [1] [2] null null
Linked List Stack: 2 -> 1 -> null

Why: Remove top element, stack shrinks logically

Step 5: Push 4 on both stacks

Array Stack: [1] [2] [4] null
Linked List Stack: 4 -> 2 -> 1 -> null

Why: Add new element on top again

Result:

Array Stack final: [1] [2] [4] null
Linked List Stack final: 4 -> 2 -> 1 -> null

Annotated Code

DSA Go

package main

import "fmt"

// Node for linked list stack
type Node struct {
	value int
	next  *Node
}

// LinkedListStack struct
type LinkedListStack struct {
	top *Node
}

func (s *LinkedListStack) 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
}

func (s *LinkedListStack) Pop() (int, bool) {
	if s.top == nil {
		return 0, false // empty stack
	}
	val := s.top.value
	s.top = s.top.next // move top down
	return val, true
}

func (s *LinkedListStack) String() string {
	res := ""
	curr := s.top
	for curr != nil {
		res += fmt.Sprintf("%d -> ", curr.value)
		curr = curr.next
	}
	return res + "null"
}

// ArrayStack struct
type ArrayStack struct {
	data []int
	top  int
}

func NewArrayStack(capacity int) *ArrayStack {
	return &ArrayStack{data: make([]int, capacity), top: -1}
}

func (s *ArrayStack) Push(val int) {
	if s.top+1 == len(s.data) {
		// resize array by doubling capacity
		newData := make([]int, len(s.data)*2)
		copy(newData, s.data)
		s.data = newData
	}
	s.top++
	s.data[s.top] = val
}

func (s *ArrayStack) Pop() (int, bool) {
	if s.top == -1 {
		return 0, false // empty stack
	}
	val := s.data[s.top]
	s.top--
	return val, true
}

func (s *ArrayStack) String() string {
	res := ""
	for i := 0; i <= s.top; i++ {
		res += fmt.Sprintf("[%d] ", s.data[i])
	}
	for i := s.top + 1; i < len(s.data); i++ {
		res += "null "
	}
	return res
}

func main() {
	// Linked List Stack
	llStack := &LinkedListStack{}
	llStack.Push(1) // push 1
	llStack.Push(2) // push 2
	llStack.Push(3) // push 3
	llStack.Pop()   // pop top (3)
	llStack.Push(4) // push 4

	// Array Stack
	arrStack := NewArrayStack(4) // initial capacity 4
	arrStack.Push(1) // push 1
	arrStack.Push(2) // push 2
	arrStack.Push(3) // push 3
	arrStack.Pop()   // pop top (3)
	arrStack.Push(4) // push 4

	fmt.Println("Linked List Stack final:", llStack.String())
	fmt.Println("Array Stack final:", arrStack.String())
}

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

push new element on top of linked list stack

val := s.top.value s.top = s.top.next

pop top element by moving top pointer down

if s.top+1 == len(s.data) { newData := make([]int, len(s.data)*2) copy(newData, s.data) s.data = newData }

resize array stack when full by doubling capacity

s.top++ s.data[s.top] = val

push element on top of array stack

val := s.data[s.top] s.top--

pop element from array stack by decreasing top index

Output

Linked List Stack final: 4 -> 2 -> 1 -> null

Array Stack final: [1] [2] [4] null 

Complexity Analysis

Time: O(1) average for push/pop on both stacks; array stack may have O(n) on push when resizing

Space: O(n) for both; linked list uses extra memory per node for pointers, array uses contiguous block

vs Alternative: Linked list stack grows dynamically without resizing but uses extra memory per element; array stack is faster for access but needs resizing which can be costly

Edge Cases

Pop from empty stack

Returns false or error indicating empty stack without crashing

DSA Go

if s.top == nil { return 0, false } // linked list pop guard

Push beyond initial array capacity

Array stack resizes by doubling capacity to accommodate new elements

DSA Go

if s.top+1 == len(s.data) { newData := make([]int, len(s.data)*2); copy(newData, s.data); s.data = newData }

Single element push and pop

Stack correctly handles push and pop leaving empty state

DSA Go

top pointer updates correctly in both push and pop

When to Use This Pattern

When a problem needs last-in-first-out order with dynamic size, consider stack implementations; choose linked list for unknown size or frequent resizing, array stack for speed and memory locality.

Common Mistakes

Mistake: Not resizing array stack when full causing index out of range error
Fix: Add resizing logic before pushing when array is full

Mistake: Forgetting to update top pointer after pop in linked list causing stale top
Fix: Always move top pointer to next node after pop

Summary

Stack can be implemented using linked list or array with different trade-offs.

Use linked list stack when size is unknown or changes frequently; use array stack for faster access and better memory use if size is predictable.

Linked list stack grows dynamically without resizing but uses extra memory; array stack needs resizing but offers faster access.

Practice

1. Which of the following is a key advantage of using a linked list to implement a stack compared to using an array?

easy

A. Dynamic size without needing to resize

B. Faster access to elements by index

C. Uses less memory per element

D. Simpler syntax in Go

Solution

1. Step 1: Understand stack size behavior

   Array stacks have fixed size or need resizing, linked lists grow dynamically.

2. Step 2: Compare advantages

   Linked list stacks do not require resizing, so they handle dynamic size better.

3. Final Answer:

   Dynamic size without needing to resize -> Option A

4. Quick Check:

   Linked list stacks grow dynamically = B [OK]

Hint: Linked lists grow dynamically, arrays need resizing [OK]

Common Mistakes:

• Thinking arrays always use less memory
• Confusing access speed advantage
• Assuming syntax is simpler for linked lists

2. Which Go syntax correctly declares an array-based stack with capacity 5?

easy

A. stack := make([]int, 5)

B. stack := [5]int{}

C. var stack []int

D. var stack []int = [5]int{}

Solution

1. Step 1: Identify array declaration syntax

   In Go, arrays are declared as [size]type{}, e.g., [5]int{}.

2. Step 2: Check options

   stack := [5]int{} uses correct syntax for array with size 5 and int type.

3. Final Answer:

   stack := [5]int{} -> Option B

4. Quick Check:

   Array declaration = [5]int{} [OK]

Hint: Arrays use [size]type{}, slices use make() [OK]

Common Mistakes:

• Confusing slices with arrays
• Using make() for arrays
• Incorrect variable declaration syntax

3. Consider this Go code implementing a stack using an array:

type Stack struct {
  items [3]int
  top int
}

func (s *Stack) Push(val int) bool {
  if s.top == len(s.items) {
    return false
  }
  s.items[s.top] = val
  s.top++
  return true
}

func (s *Stack) Pop() (int, bool) {
  if s.top == 0 {
    return 0, false
  }
  s.top--
  return s.items[s.top], true
}

func main() {
  s := Stack{}
  s.Push(10)
  s.Push(20)
  s.Push(30)
  s.Push(40) // extra push
  val, ok := s.Pop()
  fmt.Println(val, ok)
}

What is the output?

medium

A. 20 true

B. 40 true

C. 30 true

D. 0 false

Solution

1. Step 1: Trace Push operations

   Push 10, 20, 30 succeed; Push 40 fails because stack is full (size 3).

2. Step 2: Trace Pop operation

   Pop returns last pushed value 30 and true.

3. Final Answer:

   30 true -> Option C

4. Quick Check:

   Last pushed valid value = 30 [OK]

Hint: Stack size limits extra pushes; pop returns last valid push [OK]

Common Mistakes:

• Assuming push always succeeds
• Thinking pop returns failed push value
• Confusing top index after push/pop

4. This Go code attempts to implement a linked list stack but has a bug:

type Node struct {
  value int
  next *Node
}

type Stack struct {
  head *Node
}

func (s *Stack) Push(val int) {
  newNode := &Node{value: val}
  newNode.next = s.head
  s.head = newNode
}

func (s *Stack) Pop() (int, bool) {
  if s.head == nil {
    return 0, false
  }
  val := s.head.value
  s.head = s.head.next
  return val, true
}

func main() {
  s := Stack{}
  s.Push(1)
  s.Push(2)
  s.Pop()
  s.Pop()
  s.Pop() // extra pop
}

What is the bug in this code?

medium

A. Extra pop returns false but is ignored, no bug

B. Push does not update the head pointer

C. Pop does not check for empty stack before accessing value

D. Node struct missing initialization of next pointer

Solution

1. Step 1: Analyze Pop safety check

   Pop checks if head is nil before accessing value, so no crash.

2. Step 2: Check extra pop behavior

   Extra pop returns (0, false), which is safe but ignored in main.

3. Final Answer:

   Extra pop returns false but is ignored, no bug -> Option A

4. Quick Check:

   Pop safe on empty stack = A [OK]

Hint: Check nil before pop; ignoring false return is not a bug [OK]

Common Mistakes:

• Assuming pop crashes on empty stack
• Thinking push forgets to update head
• Believing next pointer needs explicit nil init

5. You need to implement a stack in Go that can handle an unknown number of elements efficiently and minimize memory waste. Which implementation is best and why? Options: A) Array stack with large fixed size B) Linked list stack C) Array stack with dynamic resizing D) Slice-based stack without capacity checks

hard

A. Array stack with large fixed size

B. Linked list stack

C. Slice-based stack without capacity checks

D. Array stack with dynamic resizing

Solution

1. Step 1: Consider unknown size and memory use

   Large fixed arrays waste memory; linked lists have overhead per node.

2. Step 2: Evaluate dynamic resizing arrays

   Dynamic resizing arrays grow as needed, balancing memory and speed efficiently.

3. Step 3: Assess slice without capacity checks

   Slice without checks risks runtime errors or inefficient growth.

4. Final Answer:

   Array stack with dynamic resizing -> Option D

5. Quick Check:

   Dynamic resizing balances size and memory = C [OK]

Hint: Dynamic arrays grow as needed, saving memory and time [OK]

Common Mistakes:

• Choosing fixed size wastes memory
• Ignoring overhead of linked lists
• Using slices without capacity checks causes errors