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.