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 text editor that needs to keep track of undo actions. You want to use a stack to store these actions. You will explore two ways to build this stack: using an array and using a linked list. This will help you understand the trade-offs between these two methods.

🎯 Goal: You will create two stacks: one using an array and one using a linked list. You will push and pop some actions and see how the stacks behave differently.

📋 What You'll Learn

Create an array-based stack with fixed size

Create a linked list-based stack

Push three actions onto each stack

Pop one action from each stack

Print the remaining stack contents

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, expression evaluation, and backtracking algorithms. Understanding different implementations helps choose the right one for your app.

💼 Career

Knowing stack implementations and their trade-offs is important for software developers, especially when optimizing for memory or speed.

1

Create an array-based stack

Create an integer array called arrayStack with size 5 and an integer variable arrayTop initialized to -1 to track the top of the stack.

DSA C

# Create an integer array called arrayStack with size 5
# Create an integer variable arrayTop initialized to -1

Hint

Think of arrayTop as the index where the last item was placed. Starting at -1 means the stack is empty.

2

Create a linked list-based stack

Define a struct called Node with an integer data and a pointer next to another Node. Then create a pointer linkedTop initialized to NULL to represent the top of the linked list stack.

DSA C

int arrayStack[5];
int arrayTop = -1;

// Define struct Node and create linkedTop pointer

Hint

The linked list stack uses nodes that point to the next node. linkedTop points to the top node.

3

Push three actions onto both stacks

Push the integers 10, 20, and 30 onto arrayStack by incrementing arrayTop and assigning the value. For the linked list stack, create new nodes with these values and link them at the top by updating linkedTop.

DSA C

int arrayStack[5];
int arrayTop = -1;

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

Node* linkedTop = NULL;

// Push 10, 20, 30 onto arrayStack
// Push 10, 20, 30 onto linked list stack

Hint

For the array stack, increase arrayTop before assigning. For the linked list, create new nodes and link them at the front.

4

Pop one action from each stack and print remaining contents

Pop one item from arrayStack by decreasing arrayTop. For the linked list stack, remove the top node by moving linkedTop to the next node and freeing the old top. Then print the remaining items in arrayStack from index 0 to arrayTop, and print the linked list stack items from linkedTop to the end.

DSA C

int arrayStack[5];
int arrayTop = -1;

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

Node* linkedTop = NULL;

// Push 10, 20, 30 onto arrayStack
arrayStack[++arrayTop] = 10;
arrayStack[++arrayTop] = 20;
arrayStack[++arrayTop] = 30;

// Push 10, 20, 30 onto linked list stack
Node* newNode;
newNode = (Node*)malloc(sizeof(Node));
newNode->data = 10;
newNode->next = linkedTop;
linkedTop = newNode;

newNode = (Node*)malloc(sizeof(Node));
newNode->data = 20;
newNode->next = linkedTop;
linkedTop = newNode;

newNode = (Node*)malloc(sizeof(Node));
newNode->data = 30;
newNode->next = linkedTop;
linkedTop = newNode;

// Pop one item from arrayStack
// Pop one item from linked list stack
// Print remaining items in arrayStack
// Print remaining items in linked list stack

Hint

Remember to decrease arrayTop to pop from the array stack. For the linked list, remove the top node and free its memory. Then print all remaining items.