Implementing Stack using Linked List in C

Implementing a stack using a link list in C is a foundational concept in computer science, especially in the world of data structure and algorithms. A stack is a linear data structure that follows the last in first out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. In this article we will go through the process of implementing a stack using a linked list in C., covering the basics of both stacks and linked lists, and providing a step-by-step guide to building stack data structure.

Understanding Stack and Linked List

Before diving into the implementation, let’s clarify what stack and linked list are-

Stack

A stack is a collection of elements with two principle operations: push, which adds an element, and pop, which removes the most recently added element. stacks are used in various applications, such as parsing expressions, backtracking paths in search problems, and maintaining function calls.

Linked List

A linked list is a linear collection of data elements, called nodes, each pointing to the next node using a pointer it is a dynamic data structure, which means that it can grow and shrink at run time.

Why use a Linked List to Implement a Stack?

Using the Linked list to implement a stack offers several advantages:

Dynamic Size: Unlike arrays, linked lists do not have a fixed size. This feature makes a linked list ideal for implementing stacks, as the size of the stack can grow a shrink according to the needs of the application.
Efficiency: Operations like push and pop are more efficient because they do not need shifting elements, as would be necessary for an array-based implementation.
Flexibility: Linked lists provide the flexibility to implement various types of stacks (e.g., generic stack for different data types).

Step-by-Step Implementation

1. Define the Node Structure

First, define a structure for the nodes of the linked list. Each node will store an integer value and a pointer to the next node.

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

2. Stack Structure

Define a structure for the stack that holds a pointer to the top of the stack (which will be a linked list node).

typedef struct Stack {
    Node* top;
} Stack;

3. Initializing the Stack

Create a function to initialize the stack. This function sets the top pointer to NULL, indicating that the stack is empty.

void initStack(Stack* stack) {
    stack->top = NULL;
}

4. Push Operation

To add an element to the stack, create a new node, set its data field, and insert it at the beginning of the linked list (at the top of the stack).

void push(Stack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Heap Overflow\n");
        return;
    }
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}

5. Pop Operation

To remove an element from the stack, remove the node at the beginning of the linked list (the top of the stack), and return its value.

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

6. Utility Functions

isEmpty: Checks if the stack is empty.
peek: Returns the value of the top element without removing it.

int isEmpty(Stack* stack) {
    return stack->top == NULL;
}

int peek(Stack* stack) {
    if (!isEmpty(stack)) return stack->top->data;
    printf("Stack is empty\n");
    return -1;
}

Implementing a stack using a linked list in C is an excellent way to understand both data structures deeply. This approach offers the flexibility of dynamic memory allocation, Efficiency in stack operations, and a deeper understanding of pointer manipulation in C.

Happy Coding & Learning