Linked List Stack vs Array Stack

Implementing a stack with a singly linked list eliminates fixed array size boundaries. Memory is dynamically allocated for each pushed element and deallocated on pop operations.

---

C Implementation

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

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

typedef struct {
    StackNode *top;
    int size;
} LinkedStack;

void initStack(LinkedStack *s) {
    s->top = NULL;
    s->size = 0;
}

bool isEmpty(const LinkedStack *s) {
    return s->top == NULL;
}

void push(LinkedStack *s, int value) {
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    if (!newNode) {
        fprintf(stderr, "Stack Overflow (Heap exhausted).\n");
        return;
    }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
    s->size++;
    printf("Pushed %d to linked stack.\n", value);
}

int pop(LinkedStack *s) {
    if (isEmpty(s)) {
        printf("Stack Underflow! Stack is empty.\n");
        return -1;
    }
    StackNode *temp = s->top;
    int poppedValue = temp->data;
    s->top = s->top->next;
    free(temp);
    s->size--;
    return poppedValue;
}

int peek(const LinkedStack *s) {
    if (isEmpty(s)) return -1;
    return s->top->data;
}

int main() {
    LinkedStack s;
    initStack(&s);

    push(&s, 100);
    push(&s, 200);
    push(&s, 300);

    printf("Top element: %d\n", peek(&s));
    printf("Popped: %d\n", pop(&s));
    printf("Popped: %d\n", pop(&s));

    return 0;
}

Sample Output

text (ISO Standard)
Copy
Pushed 100 to linked stack.
Pushed 200 to linked stack.
Pushed 300 to linked stack.
Top element: 300
Popped: 300
Popped: 200

---

Complexity Analysis

• Push / Pop / Peek: O(1) constant time operations.
• Space Complexity: O(n) dynamically grows and shrinks with item count.

---

Related Data Structures

• Compare with static buffer stack in Stack Implementation in C Using Array.
• Master dynamic node links in Singly Linked List in C.