Stack Using Linked List in C

Preorder Tree Traversal of Binary Tree in C

Stack is a linear data structure that follows the Last-In-First-Out (LIFO) order of operations. This means the last element added to the stack will be the first one to be removed. There are different ways using which we can implement stack data structure in C.

In this article, we will learn how to implement a stack using a linked list in C, its basic operation along with their time and space complexity analysis.

Implementation of Stack using Linked List in C

Stack is generally implemented using an array but the limitation of this kind of stack is that the memory occupied by the array is fixed no matter what are the number of elements in the stack. In the stack implemented using linked list implementation, the size occupied by the linked list will be equal to the number of elements in the stack. Moreover, its size is dynamic. It means that the size is gonna change automatically according to the elements present.

Representation of Linked Stack in C

In C, the stack that is implemented using a linked list can be represented by the pointer to the head node of the linked list. Each node in that linked list represents the element of the stack. The type of linked list here is a singly linked list in which each node consists of a data field and the next pointer.

struct Node {
      type data;
      Node* next;
}

The type of data can be defined according to the requirement.

Note: Even being the better method of stack implementation, the linked list implementation only used when it is absolutely necessary because we have to implement the linked list also as there are no built in data structure for it in C Programming Language.

Basic Operations of Linked List Stack in C

Following are the basic operation of the stack data structure that helps us to manipulate the data structure as needed:

Operation	Description	Time Complexity	Space Complexity
isEmpty	Returns true if the stack is empty, false otherwise.	O(1)	O(1)
Push	This operation is used to add/insert/push data into the stack.	O(1)	O(1)
Pop	This operation is used to delete/remove/pop data into the stack.	O(1)	O(1)
Peek	This operation returns the top element in the stack.	O(1)	O(1)

Let’s see how these operations are implemented in the stack.

Push Function

The push function will add a new element to the stack. As the pop function require the time and space complexity to be O(1), we will insert the new element in the beginning of the linked list. In multiple push operations, the element at the head will be the element that is most recently inserted.

We need to check for stack overflow (when we try to push into stack when it is already full).

Algorithm for Push Function

Following is the algorithm for the push function:

Create a new node with the given data.
Insert the node before the head of the linked list.
Update the head of the linked list to the new node.

Here, the stack overflow will only occur if there is some error allocating the memory in the heap so the check will be done in the creation of the new node.

Pop Function

The pop function will remove the topmost element from the stack. As we know that for stack, we need to first remove the most recently inserted element. In this implementation, the most recently inserted element will be present at the head of the linked list.

We first need to check for the stack underflow (when we try to pop stack when it is already empty).

Algorithm for Pop Function

Following is the algorithm for the pop function:

Check if the stack is empty.
If not empty, store the top node in a temporary variable.
Update the head pointer to the next node.
Free the temporary node.

Peek Function

The peek function will return the topmost element of the stack if the stack is not empty. The topmost element means the element at the head.

Algorithm for Peek Function

The following is the algorithm for peek function:

Check if the stack is empty.
If its empty, return -1.
Else return the head->data.

IsEmpty Function

The isEmpty function will check if the stack is empty or not. This function returns true if the stack is empty otherwise, it returns false.

Algorithm of isEmpty Function

The following is the algorithm for isEmpty function:

Check if the top pointer of the stack is NULL.
If NULL, return true, indicating the stack is empty.
Otherwise return false indicating the stack is not empty.

C Program to Implement a Stack Using Linked List

The below example demonstrates how to implement a stack using a linked list in C.

// C program to implement a stack using linked list
#include <stdio.h>
#include <stdlib.h>

//  ________LINKED LIST UTILITY FUNCITON____________

// Define the structure for a node of the linked list
typedef struct Node {
    int data;
    struct Node* next;
} node;

// linked list utility function
node* createNode(int data)
{
    // allocating memory
    node* newNode = (node*)malloc(sizeof(node));

    // if memory allocation is failed
    if (newNode == NULL)
        return NULL;

    // putting data in the node
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// fuction to insert data before the head node
int insertBeforeHead(node** head, int data)
{
    // creating new node
    node* newNode = createNode(data);
    // if malloc fail, return error code
    if (!newNode)
        return -1;

    // if the linked list is empty
    if (*head == NULL) {
        *head = newNode;
        return 0;
    }

    newNode->next = *head;
    *head = newNode;
    return 0;
}

// deleting head node
int deleteHead(node** head)
{
    // no need to check for empty stack as it is already
    // being checked in the caller function
    node* temp = *head;
    *head = (*head)->next;
    free(temp);
    return 0;
}

// _________STACK IMPLEMENTATION STARTS HERE_________

// Function to check if the stack is empty or not
int isEmpty(node** stack) { return *stack == NULL; }

// Function to push elements to the stack
void push(node** stack, int data)
{
    // inserting the data at the beginning of the linked
    // list stack
    // if the insertion function returns the non - zero
    // value, it is the case of stack overflow
    if (insertBeforeHead(stack, data)) {
        printf("Stack Overflow!\n");
    }
}

// Function to pop an element from  the stack
int pop(node** stack)
{
    // checking underflow condition
    if (isEmpty(stack)) {
        printf("Stack Underflow\n");
        return -1;
    }

    // deleting the head.
    deleteHead(stack);
}

// Function to return the topmost element of the stack
int peek(node** stack)
{
    // check for empty stack
    if (!isEmpty(stack))
        return (*stack)->data;
    else
        return -1;
}

// Function to print the Stack
void printStack(node** stack)
{
    node* temp = *stack;
    while (temp != NULL) {
        printf("%d-> ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// driver code
int main()
{
    // Initialize a new stack top pointer
    node* stack = NULL;

    // Push elements into the stack
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    push(&stack, 40);
    push(&stack, 50);

    // Print the stack
    printf("Stack: ");
    printStack(&stack);
    // Pop elements from the stack
    pop(&stack);
    pop(&stack);
    // Print the stack after deletion of elements
    printf("\nStack: ");
    printStack(&stack);

    return 0;
}

Output

Stack: 50-> 40-> 30-> 20-> 10-> 

Stack: 30-> 20-> 10->

Benifits of Linked List Stack in C

The following are the major benifits of the linked list implementation over the array implementation:

The dynamic memory management of linked list provide dynamic size to the stack that changes with the change in the number of elements.
Rarely reaches the condition of the stack overflow.

Conclusion

The linked list implementation of the stack here shows that even while providing such benifits,it can only be used when we are ready to bear the cost of implementing the linked list also in our C program. Though if we already have linked list, we should prefer this implementation over the array one.

The following are some articles about the Stack data structure that can improve your understanding of the it:

Tags:

#C-DSA #C Language

Array of Linked Lists in C/C++