How to Implement Stack Using Linked List in C: Simple Guide

To implement a stack using a linked list in C, create a node structure with data and a pointer to the next node. Use the linked list's head as the top of the stack, and implement push by adding nodes at the head and pop by removing nodes from the head.

Syntax

A stack using a linked list requires a struct Node with two parts: data to store the value and next to point to the next node. The stack top is a pointer to the first node. push adds a new node at the front, and pop removes the front node.

c

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

Node* top = NULL; // Stack top pointer

void push(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

int pop() {
    if (top == NULL) {
        printf("Stack is empty\n");
        return -1; // or error code
    }
    int value = top->data;
    Node* temp = top;
    top = top->next;
    free(temp);
    return value;
}

Example

This example shows how to push three values onto the stack and then pop them all, printing each popped value. It demonstrates the Last-In-First-Out (LIFO) behavior of the stack implemented with a linked list.

c

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

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

Node* top = NULL;

void push(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

int pop() {
    if (top == NULL) {
        printf("Stack is empty\n");
        return -1;
    }
    int value = top->data;
    Node* temp = top;
    top = top->next;
    free(temp);
    return value;
}

int main() {
    push(10);
    push(20);
    push(30);

    printf("Pop: %d\n", pop());
    printf("Pop: %d\n", pop());
    printf("Pop: %d\n", pop());
    printf("Pop: %d\n", pop()); // stack empty

    return 0;
}

Output

Pop: 30
Pop: 20
Pop: 10
Stack is empty
Pop: -1

Common Pitfalls

• Not checking if malloc returns NULL can cause crashes if memory is full.
• Forgetting to update the top pointer after pop leads to invalid memory access.
• Not freeing memory after pop causes memory leaks.
• Trying to pop from an empty stack without checking leads to errors.

c

/* Wrong: Not checking malloc and not freeing memory */
void push_wrong(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

int pop_wrong() {
    if (top == NULL) {
        return -1; // no message
    }
    int value = top->data;
    // forgot to free memory
    top = top->next;
    return value;
}

/* Right: Check malloc and free memory */
void push_right(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

int pop_right() {
    if (top == NULL) {
        printf("Stack is empty\n");
        return -1;
    }
    int value = top->data;
    Node* temp = top;
    top = top->next;
    free(temp);
    return value;
}

Quick Reference

• push(value): Create a new node, set its data, point it to current top, update top.
• pop(): Check if stack is empty, save top data, move top to next node, free old top, return data.
• top pointer: Always points to the stack's top node or NULL if empty.
• Memory management: Always free nodes after popping to avoid leaks.

Key Takeaways

Use a linked list node with data and next pointer to represent stack elements.

Push adds nodes at the head; pop removes nodes from the head to maintain LIFO order.

Always check for empty stack before popping to avoid errors.

Free memory of popped nodes to prevent memory leaks.

Check malloc return to handle memory allocation failures safely.