Stack Using Linked List vs Array Stack Trade-offs in DSA C++ - 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 an array and using a linked list. This will help you see how each way works and what is easier or harder about them.

🎯 Goal: You will create two stacks: one using an array and one using a linked list. You will add and remove books from both stacks and then print their contents. This will help you understand the differences between these two stack types.

📋 What You'll Learn

Create an array-based stack with a fixed size of 5

Create a linked list-based stack

Push three book names onto 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 method for each case.

💼 Career

Understanding stack implementations is important for software developers, especially when optimizing memory and performance or working with low-level data structures.

1

Create an array-based stack

Create an array called arrayStack of size 5 to hold std::string values. Also create an integer variable called arrayTop and set it to -1 to track the top of the stack.

DSA C++

# Create an array called arrayStack of size 5 and an int variable arrayTop set to -1
# Your code here

Hint

Use std::string arrayStack[5]; to create the array and int arrayTop = -1; to track the top.

2

Create a linked list-based stack

Create a struct called Node with a std::string field called data and a pointer to Node called next. Then create a pointer called linkedTop of type Node* and set it to nullptr.

DSA C++

#include 
#include 

std::string arrayStack[5];
int arrayTop = -1;

// Create struct Node and pointer linkedTop
# Your code here

Hint

Define struct Node with data and next. Then set Node* linkedTop = nullptr;.

3

Push three books onto both stacks and pop one

Push the books "Book1", "Book2", and "Book3" onto arrayStack by increasing arrayTop and assigning the book name. For the linked list stack, create new Node objects for each book, set their data, and link them by updating linkedTop. Then pop one book from each stack by decreasing arrayTop and moving linkedTop to the next node.

DSA C++

#include 
#include 

std::string arrayStack[5];
int arrayTop = -1;

struct Node {
    std::string data;
    Node* next;
};

Node* linkedTop = nullptr;

// Push "Book1", "Book2", "Book3" onto arrayStack and linked list stack
// Pop one book from each stack
# Your code here

Hint

Use arrayStack[++arrayTop] = "Book1"; style for array stack push. For linked list, create nodes and link them. To pop, decrease arrayTop and move linkedTop to next node, deleting the old top.

4

Print the remaining books in both stacks

Print the books left in arrayStack from index 0 to arrayTop using a for loop. Then print the books in the linked list stack by traversing from linkedTop until nullptr. Print each book name on its own line with the prefix "ArrayStack: " or "LinkedListStack: ".

DSA C++

#include 
#include 

std::string arrayStack[5];
int arrayTop = -1;

struct Node {
    std::string data;
    Node* next;
};

Node* linkedTop = nullptr;

// Push onto arrayStack
arrayStack[++arrayTop] = "Book1";
arrayStack[++arrayTop] = "Book2";
arrayStack[++arrayTop] = "Book3";

// Push onto linked list stack
Node* node1 = new Node{"Book1", nullptr};
Node* node2 = new Node{"Book2", node1};
Node* node3 = new Node{"Book3", node2};
linkedTop = node3;

// Pop one from arrayStack
arrayTop--;

// Pop one from linked list stack
Node* temp = linkedTop;
linkedTop = linkedTop->next;
delete temp;

// Print remaining books in arrayStack and linked list stack
# Your code here

Hint

Use a for loop to print arrayStack from 0 to arrayTop. Use a while loop to traverse the linked list from linkedTop to nullptr.

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. Accessing elements by index is faster.

B. The stack size can grow dynamically without a fixed limit.

C. Memory usage is always less than an array.

D. It uses less pointer memory.

Solution

1. Step 1: Understand stack size behavior in linked list

   A linked list stack can grow dynamically because nodes are created as needed without a fixed size.

2. Step 2: Compare with array stack size limits

   An array stack has a fixed size or requires resizing, which is costly. Linked list avoids this limitation.

3. Final Answer:

   The stack size can grow dynamically without a fixed limit. -> Option B

4. Quick Check:

   Dynamic size = Linked list advantage [OK]

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

Common Mistakes:

• Thinking arrays always use less memory
• Confusing access speed advantages
• Assuming linked lists use less pointer memory

2. Which of the following is the correct way to declare a stack using an array in C++?

easy

A. int stack[10]; int top = -1;

B. int stack; int top = 0;

C. int stack[]; int top = -1;

D. int stack(10); int top = -1;

Solution

1. Step 1: Check array declaration syntax

   In C++, arrays are declared with size inside square brackets, e.g., int stack[10];

2. Step 2: Check top initialization

   Top is initialized to -1 to indicate empty stack.

3. Final Answer:

   int stack[10]; int top = -1; -> Option A

4. Quick Check:

   Correct array syntax and top init = C [OK]

Hint: Array size in [] brackets; top starts at -1 [OK]

Common Mistakes:

• Using parentheses instead of brackets for array
• Not initializing top correctly
• Declaring array without size

3. Consider the following code snippet implementing a stack push operation using a linked list:

struct Node {
  int data;
  Node* next;
};

Node* top = nullptr;

void push(int x) {
  Node* newNode = new Node();
  newNode->data = x;
  newNode->next = top;
  top = newNode;
}

push(10);
push(20);
push(30);

What will be the order of elements from top to bottom after these pushes?

medium

A. 10 -> 20 -> 30 -> null

B. 20 -> 30 -> 10 -> null

C. 30 -> 20 -> 10 -> null

D. 30 -> 10 -> 20 -> null

Solution

1. Step 1: Trace push operations on linked list stack

   Each push adds new node at the top, so last pushed is on top.

2. Step 2: Order after pushes

   push(10) -> top=10; push(20) -> top=20->10; push(30) -> top=30->20->10

3. Final Answer:

   30 -> 20 -> 10 -> null -> Option C

4. Quick Check:

   Last in first out = 30 on top [OK]

Hint: Last pushed is always on top in linked list stack [OK]

Common Mistakes:

• Assuming order is 10->20->30
• Confusing push with append at end
• Ignoring pointer update order

4. The following code attempts to pop an element from an array-based stack but has a bug:

int stack[5];
int top = -1;

void pop() {
  if (top == 0) {
    cout << "Stack Underflow" << endl;
    return;
  }
  top--;
}

What is the bug in this pop function?

medium

A. It should print "Stack Overflow" instead of "Stack Underflow".

B. It should increment top instead of decrementing.

C. The stack array size is too small.

D. It should check if top == -1 for underflow, not top == 0.

Solution

1. Step 1: Understand stack underflow condition

   Underflow occurs when stack is empty, which is when top == -1.

2. Step 2: Check condition in code

   Code checks top == 0, which is wrong; top == 0 means one element is present.

3. Final Answer:

   It should check if top == -1 for underflow, not top == 0. -> Option D

4. Quick Check:

   Empty stack top = -1, check must match [OK]

Hint: Empty stack top is -1, check underflow with top == -1 [OK]

Common Mistakes:

• Checking top == 0 instead of -1
• Confusing overflow and underflow messages
• Incorrectly incrementing top on pop

5. You want to implement a stack that can handle millions of push and pop operations without worrying about maximum size. Which implementation is better and why?

1. Array-based stack with dynamic resizing
2. Linked list-based stack

hard

A. Linked list stack is better because it grows dynamically without resizing overhead.

B. Array stack is better because it uses less memory per element.

C. Array stack is better because dynamic resizing is always faster than linked list allocation.

D. Linked list stack is worse because it cannot grow beyond initial size.

Solution

1. Step 1: Consider dynamic resizing cost in array stack

   Array stack needs to resize and copy elements when full, which is costly for millions of operations.

2. Step 2: Consider linked list stack growth

   Linked list stack allocates nodes on demand, no resizing needed, so it handles large operations smoothly.

3. Final Answer:

   Linked list stack is better because it grows dynamically without resizing overhead. -> Option A

4. Quick Check:

   Dynamic growth without resizing = Linked list advantage [OK]

Hint: Linked list avoids resizing overhead for large stacks [OK]

Common Mistakes:

• Assuming array resizing is always faster
• Ignoring memory overhead of pointers
• Thinking linked list has fixed size