Stack Using Linked List vs Array Stack Trade-offs in DSA Go - Build Both Approaches

Stack Using Linked List vs Array Stack Trade-offs

📖 Scenario: Imagine you are building a simple program to manage a stack of books. You want to try two ways to store the books: using a linked list and using an array. Each book is represented by a number (its ID).This project will help you see how these two ways work and what are their differences.

🎯 Goal: You will create two stacks: one using a linked list and one using an array. You will add some books to each stack and then remove one book from each. Finally, you will print the current books in each stack to compare.

📋 What You'll Learn

Create a linked list stack with push and pop operations

Create an array stack with push and pop operations

Add three books with IDs 101, 102, 103 to each stack

Pop one book from each stack

Print the remaining books in each stack

💡 Why This Matters

🌍 Real World

Stacks are used in many programs like undo features, expression evaluation, and backtracking. Knowing different ways to build stacks helps choose the best one for your needs.

💼 Career

Understanding stack implementations and their trade-offs is important for software developers, especially when optimizing memory and performance.

1

Create a linked list stack and push books

Create a linked list stack type called LinkedListStack with a push method. Then create a variable called llStack of this type. Use llStack.push(101), llStack.push(102), and llStack.push(103) to add these book IDs to the stack.

DSA Go

// Define LinkedListStack type and push method
// Create llStack variable
// Push 101, 102, 103 to llStack
// Your code here

Hint

Think of the linked list stack as a chain of nodes. Each push adds a new node at the front.

2

Create an array stack and push books

Create an array stack type called ArrayStack with a push method. Then create a variable called arrStack of this type. Use arrStack.push(101), arrStack.push(102), and arrStack.push(103) to add these book IDs to the stack.

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type LinkedListStack struct {
    head *Node
}

func (s *LinkedListStack) push(val int) {
    newNode := &Node{value: val, next: s.head}
    s.head = newNode
}

type ArrayStack struct {
    items []int
}

// Your code here

Hint

Think of the array stack as a list where you add new items at the end.

3

Pop one book from each stack

Add a pop method to both LinkedListStack and ArrayStack that removes and returns the top book ID. Then use llStack.pop() and arrStack.pop() to remove one book from each stack.

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type LinkedListStack struct {
    head *Node
}

func (s *LinkedListStack) push(val int) {
    newNode := &Node{value: val, next: s.head}
    s.head = newNode
}

func (s *LinkedListStack) pop() int {
    // Your code here
    return 0
}

type ArrayStack struct {
    items []int
}

func (s *ArrayStack) push(val int) {
    s.items = append(s.items, val)
}

func (s *ArrayStack) pop() int {
    // Your code here
    return 0
}

func main() {
    llStack := LinkedListStack{}
    llStack.push(101)
    llStack.push(102)
    llStack.push(103)

    arrStack := ArrayStack{}
    arrStack.push(101)
    arrStack.push(102)
    arrStack.push(103)

    llStack.pop()
    arrStack.pop()
}

Hint

Pop removes the top item and returns it. For linked list, move head to next. For array, remove last item.

4

Print remaining books in each stack

Add a printStack method to both LinkedListStack and ArrayStack that prints the book IDs from top to bottom separated by -> . Then print the stacks using llStack.printStack() and arrStack.printStack().

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type LinkedListStack struct {
    head *Node
}

func (s *LinkedListStack) push(val int) {
    newNode := &Node{value: val, next: s.head}
    s.head = newNode
}

func (s *LinkedListStack) pop() int {
    if s.head == nil {
        return -1
    }
    val := s.head.value
    s.head = s.head.next
    return val
}

func (s *LinkedListStack) printStack() {
    // Your code here
}

type ArrayStack struct {
    items []int
}

func (s *ArrayStack) push(val int) {
    s.items = append(s.items, val)
}

func (s *ArrayStack) pop() int {
    if len(s.items) == 0 {
        return -1
    }
    val := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return val
}

func (s *ArrayStack) printStack() {
    // Your code here
}

func main() {
    llStack := LinkedListStack{}
    llStack.push(101)
    llStack.push(102)
    llStack.push(103)

    arrStack := ArrayStack{}
    arrStack.push(101)
    arrStack.push(102)
    arrStack.push(103)

    llStack.pop()
    arrStack.pop()

    llStack.printStack()
    arrStack.printStack()
}

Hint

Print from top to bottom. For linked list, start at head. For array, print from last to first.

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