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

Mental Model

A stack stores items in order, last in first out. Using an array or linked list changes how we add or remove items and how much space we use.

Analogy: Imagine a stack of plates: an array stack is like a fixed shelf with limited spots, while a linked list stack is like a chain of plates you can add or remove only at the top without fixed size.

Array Stack:
[0] 10
[1] 20
[2] 30
 ↑ top

Linked List Stack:
30 -> 20 -> 10 -> null
 ↑ top

Dry Run Walkthrough

Input: Push 10, then 20, then 30 onto both array stack and linked list stack; then pop one item from each.

Goal: Show how pushing and popping works differently and how space is managed in array vs linked list stacks.

Step 1: Push 10 onto array stack and linked list stack

Array Stack:
[0] 10
 ↑ top

Linked List Stack:
10 -> null
 ↑ top

Why: Add first item to both stacks; array uses index 0, linked list creates first node.

Step 2: Push 20 onto array stack and linked list stack

Array Stack:
[0] 10
[1] 20
 ↑ top

Linked List Stack:
20 -> 10 -> null
 ↑ top

Why: Add second item; array increments index, linked list adds new node at front.

Step 3: Push 30 onto array stack and linked list stack

Array Stack:
[0] 10
[1] 20
[2] 30
 ↑ top

Linked List Stack:
30 -> 20 -> 10 -> null
 ↑ top

Why: Add third item; array uses next index, linked list adds new node at front.

Step 4: Pop one item from array stack and linked list stack

Array Stack:
[0] 10
[1] 20
 ↑ top

Linked List Stack:
20 -> 10 -> null
 ↑ top

Why: Remove top item; array moves top index down, linked list removes front node.

Result:

Array Stack:
[0] 10
[1] 20
 ↑ top

Linked List Stack:
20 -> 10 -> null
 ↑ top

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node for linked list stack
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Linked list stack push
void pushLinkedList(Node** top, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = *top; // link new node to current top
    *top = newNode; // update top to new node
}

// Linked list stack pop
int popLinkedList(Node** top) {
    if (*top == NULL) return -1; // empty stack
    Node* temp = *top;
    int val = temp->data;
    *top = temp->next; // move top down
    free(temp);
    return val;
}

// Array stack structure
typedef struct {
    int* arr;
    int capacity;
    int top;
} ArrayStack;

// Initialize array stack
ArrayStack* createArrayStack(int capacity) {
    ArrayStack* stack = (ArrayStack*)malloc(sizeof(ArrayStack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->arr = (int*)malloc(capacity * sizeof(int));
    return stack;
}

// Array stack push
int pushArray(ArrayStack* stack, int value) {
    if (stack->top == stack->capacity - 1) return -1; // full
    stack->arr[++stack->top] = value; // increment top and add
    return 0;
}

// Array stack pop
int popArray(ArrayStack* stack) {
    if (stack->top == -1) return -1; // empty
    return stack->arr[stack->top--]; // return top and decrement
}

// Print array stack
void printArrayStack(ArrayStack* stack) {
    for (int i = 0; i <= stack->top; i++) {
        printf("[%d] %d\n", i, stack->arr[i]);
    }
    printf(" ↑ top\n");
}

// Print linked list stack
void printLinkedListStack(Node* top) {
    Node* curr = top;
    while (curr) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("null\n ↑ top\n");
}

int main() {
    // Create array stack with capacity 5
    ArrayStack* arrayStack = createArrayStack(5);
    Node* linkedListStack = NULL;

    // Push 10, 20, 30
    pushArray(arrayStack, 10);
    pushArray(arrayStack, 20);
    pushArray(arrayStack, 30);

    pushLinkedList(&linkedListStack, 10);
    pushLinkedList(&linkedListStack, 20);
    pushLinkedList(&linkedListStack, 30);

    // Print both stacks
    printf("Array Stack:\n");
    printArrayStack(arrayStack);
    printf("Linked List Stack:\n");
    printLinkedListStack(linkedListStack);

    // Pop one item from each
    popArray(arrayStack);
    popLinkedList(&linkedListStack);

    // Print after pop
    printf("\nAfter one pop:\n");
    printf("Array Stack:\n");
    printArrayStack(arrayStack);
    printf("Linked List Stack:\n");
    printLinkedListStack(linkedListStack);

    // Free linked list
    while (linkedListStack) {
        Node* temp = linkedListStack;
        linkedListStack = linkedListStack->next;
        free(temp);
    }
    free(arrayStack->arr);
    free(arrayStack);

    return 0;
}

newNode->next = *top; // link new node to current top *top = newNode; // update top to new node

add new node at front to push onto linked list stack

*top = temp->next; // move top down free(temp);

remove front node to pop from linked list stack

stack->arr[++stack->top] = value; // increment top and add

increment top index and add value to array stack

return stack->arr[stack->top--]; // return top and decrement

return top value and decrement top index to pop from array stack

Output

Array Stack:

[0] 10

[1] 20

[2] 30

 ↑ top

Linked List Stack:

30 -> 20 -> 10 -> null

 ↑ top



After one pop:

Array Stack:

[0] 10

[1] 20

 ↑ top

Linked List Stack:

20 -> 10 -> null

 ↑ top

Complexity Analysis

Time: O(1) for push and pop in both array and linked list stacks because operations happen at one end only

Space: O(n) for both; array stack uses fixed capacity which may waste space, linked list stack uses exact space but with extra pointer per node

vs Alternative: Array stack is faster with better cache but fixed size; linked list stack is flexible size but uses more memory and slower due to pointers

Edge Cases

Pushing to full array stack

Push fails gracefully returning error code -1

DSA C

if (stack->top == stack->capacity - 1) return -1; // full

Popping from empty array stack

Pop returns -1 indicating empty stack

DSA C

if (stack->top == -1) return -1; // empty

Popping from empty linked list stack

Pop returns -1 indicating empty stack

DSA C

if (*top == NULL) return -1; // empty stack

When to Use This Pattern

When you see a problem asking for last-in-first-out order with dynamic size or fixed size constraints, consider stack implementations using linked list or array to balance flexibility and speed.

Common Mistakes

Mistake: Forgetting to check for stack overflow in array stack push
Fix: Add condition to check if top reached capacity - 1 before pushing

Mistake: Not updating top pointer correctly in linked list pop
Fix: Set top to next node before freeing current top node

Summary

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

Use array stack for fixed size and faster access; use linked list stack for flexible size.

Array stack uses index to track top; linked list stack uses pointer to front node.

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. It requires less pointer management

B. Accessing elements by index is faster

C. Memory usage is always less

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

Solution

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

   A linked list stack can grow or shrink dynamically because nodes are allocated as needed.

2. Step 2: Compare with array stack size limits

   An array stack has a fixed size or needs resizing, which is costly and limits capacity.

3. Final Answer:

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

4. Quick Check:

   Dynamic size = Linked list stack advantage [OK]

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

Common Mistakes:

• Thinking array stacks can grow without resizing
• Assuming linked lists use less memory always
• Confusing access speed advantages

2. Which syntax correctly declares a stack node for a linked list stack in C?

easy

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

B. struct Node { int data; int next; };

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

D. struct Node { int data; struct Node next; };

Solution

1. Step 1: Check correct pointer declaration

   The next pointer must be of type 'struct Node*' to point to the next node.

2. Step 2: Validate typedef usage

   typedef struct Node { int data; struct Node* next; } Node; correctly uses typedef and struct pointer syntax in C.

3. Final Answer:

   typedef struct Node { int data; struct Node* next; } Node; -> Option A

4. Quick Check:

   Correct pointer syntax = typedef struct Node { int data; struct Node* next; } Node; [OK]

Hint: Use 'struct Node* next;' for linked list pointers in C [OK]

Common Mistakes:

• Using 'Node* next;' without 'struct' in C
• Declaring next as int instead of pointer
• Missing typedef or incorrect struct syntax

3. What will be the output after pushing 10, 20, then 30 onto an empty linked list stack and then popping once?

medium

A. 20 -> 10 -> null

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

C. 10 -> null

D. 20 -> null

Solution

1. Step 1: Push 10, 20, 30 onto stack

   Stack after pushes: top = 30, then 20, then 10 at bottom.

2. Step 2: Pop once removes top (30)

   After pop, top is 20, next is 10, then null.

3. Final Answer:

   20 -> 10 -> null -> Option A

4. Quick Check:

   Pop removes top = 20 -> 10 [OK]

Hint: Pop removes last pushed item; list shows remaining stack [OK]

Common Mistakes:

• Confusing push order with pop order
• Listing stack bottom first
• Forgetting pop removes top element

4. Given this array stack code snippet, what is the error?

int stack[3];
int top = -1;
void push(int x) {
  if(top == 3) {
    printf("Stack Overflow\n");
    return;
  }
  stack[++top] = x;
}

medium

A. The push function does not increment top

B. The stack array size is too large

C. The overflow condition should be 'top == 2' instead of 'top == 3'

D. The stack should be declared as a pointer

Solution

1. Step 1: Check array size and top index limits

   Array size is 3, so valid indices are 0,1,2; top max should be 2.

2. Step 2: Analyze overflow condition

   Condition 'top == 3' allows top to go out of bounds; should be 'top == 2'.

3. Final Answer:

   The overflow condition should be 'top == 2' instead of 'top == 3' -> Option C

4. Quick Check:

   Array max index = 2, overflow check must match [OK]

Hint: Array index max = size-1; check overflow accordingly [OK]

Common Mistakes:

• Checking overflow with wrong index
• Assuming top starts at 0
• Confusing array size with max index

5. Which of the following is a disadvantage of using an array-based stack compared to a linked list stack in a system with limited memory fragmentation?

hard

A. Linked list stack has slower push and pop operations

B. Array stack requires contiguous memory, which may be unavailable

C. Array stack uses more memory per element due to pointers

D. Linked list stack cannot be resized dynamically

Solution

1. Step 1: Understand memory allocation for array stacks

   Array stacks need a continuous block of memory, which can be hard to find if memory is fragmented.

2. Step 2: Compare with linked list memory allocation

   Linked lists allocate nodes separately, so they handle fragmentation better.

3. Final Answer:

   Array stack requires contiguous memory, which may be unavailable -> Option B

4. Quick Check:

   Contiguous memory need = array stack disadvantage [OK]

Hint: Arrays need continuous memory; linked lists do not [OK]

Common Mistakes:

• Thinking linked lists are slower always
• Assuming arrays use more memory per element
• Believing linked lists cannot resize dynamically