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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Memory Usage Comparison

Which statement correctly describes the memory usage difference between a stack implemented using a linked list and one using an array?

A Linked list stack uses less memory overall because it stores only data without pointers.

B Array stack uses extra memory for pointers, while linked list stack uses contiguous memory without extra pointers.

C Both linked list and array stacks use the same amount of memory per element.

D Linked list stack uses extra memory for pointers, while array stack uses contiguous memory without extra pointers.

💡 Hint

Think about how linked lists store each element compared to arrays.

A linked list stack stores each element in a node that contains the data and a pointer to the next node, which uses extra memory. An array stack stores elements in contiguous memory without pointers.

❓ Predict Output

intermediate

Stack Push Operation Output

What is the printed output after pushing elements 10, 20, and 30 onto a linked list stack and then printing the stack?

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type Stack struct {
    top *Node
}

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

func (s *Stack) Print() {
    current := s.top
    for current != nil {
        fmt.Printf("%d -> ", current.value)
        current = current.next
    }
    fmt.Println("null")
}

func main() {
    s := &Stack{}
    s.Push(10)
    s.Push(20)
    s.Push(30)
    s.Print()
}

A 10 -> 20 -> 30 -> null

B 30 -> 20 -> 10 -> null

C null -> 10 -> 20 -> 30

D 30 -> 10 -> 20 -> null

💡 Hint

Remember that new elements are added to the top of the stack.

Each push adds a new node at the top, so the last pushed element (30) is printed first, followed by 20 and then 10.

🧠 Conceptual

advanced

Performance Trade-offs in Stack Operations

Which statement best describes the time complexity trade-offs between array-based and linked list-based stacks for push and pop operations?

A Array stacks always have O(n) time for push and pop due to resizing, while linked list stacks have O(1) time.

B Both array and linked list stacks have O(n) time for push and pop operations.

C Both array and linked list stacks have O(1) average time for push and pop, but array stacks may require resizing which can cause occasional O(n) time.

D Linked list stacks have O(n) time for push and pop because of pointer updates, while array stacks have O(1) time.

💡 Hint

Consider what happens when an array stack runs out of space.

Linked list stacks always push and pop in O(1) time. Array stacks usually do too, but resizing the array when full takes O(n) time occasionally.

❓ Predict Output

advanced

Stack Capacity Behavior

Given an array stack with initial capacity 2, what is the output after pushing elements 1, 2, 3, and then printing the stack elements in order from bottom to top?

DSA Go

package main

import "fmt"

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

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

func (s *ArrayStack) Push(val int) {
    if s.top+1 == s.capacity {
        newCap := s.capacity * 2
        newData := make([]int, newCap)
        copy(newData, s.data)
        s.data = newData
        s.capacity = newCap
    }
    s.top++
    s.data[s.top] = val
}

func (s *ArrayStack) Print() {
    for i := 0; i <= s.top; i++ {
        fmt.Printf("%d ", s.data[i])
    }
    fmt.Println()
}

func main() {
    s := NewArrayStack(2)
    s.Push(1)
    s.Push(2)
    s.Push(3)
    s.Print()
}

A 1 2 3

B 3 2 1

C 1 2

D 3

💡 Hint

Array stack stores elements from bottom at index 0 to top at index top.

The stack grows by doubling capacity when full. After pushing 3 elements, the stack contains 1, 2, 3 in order from bottom to top.

🧠 Conceptual

expert

Choosing Stack Implementation for Real-Time Systems

For a real-time system requiring guaranteed constant-time push and pop operations without pauses, which stack implementation is best and why?

A Linked list stack, because it always performs push and pop in O(1) time without resizing delays.

B Array stack, because it uses contiguous memory which is faster despite resizing delays.

C Array stack, because resizing can be avoided by preallocating a large enough array.

D Linked list stack, because it uses less memory and is cache-friendly.

💡 Hint

Consider the impact of resizing delays on real-time guarantees.

Linked list stacks have consistent O(1) push/pop without resizing pauses, making them suitable for real-time systems. Array stacks may have unpredictable delays due to resizing.

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