Implement Stack using Singly linked list

Stack can be implemented by both array and linked list. There is some limitation or you can say that drawback in stack implementation using an array is that the array must be declared with some fixed size. In case if the size of the array becomes small to perform the required operation so this is a problem or if we declare the too larger size of an array in advance then it is also a wastage of memory. So if the array size cannot be determined in advance, then we have an alternative solution that is linked list representation.
The storage requirement of linked representation of the stack with n elements is O(n), and the typical time required for the operations is O(1).

Example

In the above image a linked stack, every node has two parts—one that stores data and another that stores the address of the next node. The linked list allocates the memory dynamically. However, time complexity in both the scenario is the same for all the operations i.e. push, pop, and peek. The START pointer of the linked list is used as TOP. All insertions and deletions are done at the node pointed by TOP. If TOP = NULL, then it indicates that the stack is empty.

OPERATIONS ON A LINKED STACK

A linked stack supports all the four stack operations, that is, push, pop, peek and display.

1. Push Operation

The push operation is used to insert an element into the stack. The new element is added at the topmost position of the stack.

Push Operation algorithm

Step 1 – Allocate memory to create a newNode with given value and name it as NEW_NODE.
Step 2 – Check whether TOP == NULL of Stack
Step 3 – If TOP == NULL means empty, then set newNode → next = NULL and TOP = NEW_NODE.
Step 4 – If TOP != NULL, then set newNode → next = top and TOP = NEW_NODE.
Step 5 – END

2. POP Operation

POP operation is performed on stack to remove item from the stack.

POP Operation algorithm

Step 1 – Check whether TOP == NULL of Stack.
Step 2 – If TOP == NULL then print “Stack is Empty” and terminate the function
Step 3 – If TOP != NULL, then define a Node pointer ‘temp’ and set it to ‘top’.
Step 4 – Then set ‘top = top → next’.
Step 5 – Finally, delete ‘temp’. (free(temp)).

3. PEEK Operation

Using peek operation topmost element of the stack will be retrieved without deleting it from the stack. 

PEEK Operation Algorithm

Step 1 – Check whether TOP == NULL of Stack.
Step 2 – If TOP == NULL then print “Stack is Empty” and terminate the function
Step 3 – If TOP != NULL, then display top->data.
Step 4 – END

4. Display Operation

Display operation is used to print all the elements of stack.

Display Operation Algorithm

Step 1 – Check whether TOP == NULL of Stack.
Step 2 – If TOP == NULL then print “Stack is Empty” and terminate the function
Step 3 – If TOP != NULL, then define a Node pointer ‘ptr’ and initialize with top.
Step 4 – Display ‘temp → data’ util temp → next != NULL.
Step 5 – Finally Display ‘temp → data’.

C Program for Stack implementation using linked list

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

// Define Node structure
struct Node {
    int data;
    struct Node* next;
};

// Top pointer
struct Node* top = NULL;

// Push operation
void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = top;
    top = newNode;
    printf("%d pushed to stack\n", value);
}

// Pop operation
void pop() {
    if (top == NULL) {
        printf("Stack is Empty\n");
        return;
    }
    struct Node* temp = top;
    top = top->next;
    printf("%d popped from stack\n", temp->data);
    free(temp);
}

// Peek operation
void peek() {
    if (top == NULL) {
        printf("Stack is Empty\n");
        return;
    }
    printf("Top element is %d\n", top->data);
}

// Display operation
void display() {
    if (top == NULL) {
        printf("Stack is Empty\n");
        return;
    }
    struct Node* temp = top;
    printf("Stack elements: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// Main function to demonstrate stack operations
int main() {
    push(10);
    push(20);
    push(30);
    display();
    
    peek();
    
    pop();
    display();
    
    peek();
    
    return 0;
}

Output

10 pushed to stack
20 pushed to stack
30 pushed to stack
Stack elements: 30 20 10 
Top element is 30
30 popped from stack
Stack elements: 20 10
Top element is 20

Explanation of the code

Include Headers

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

In the above code, stdio.h is a header file that is used for input and output functions, like printf to display output on the screen. stdlib.h is another header file that is used for tasks like allocating memory using malloc and freeing memory using free. These header files help the program perform important basic operations easily.

Define Node Structure

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

In the above code defines a structure called Node, which is used to create elements of a linked list. Each Node contains two parts: an integer data to store the value, and a pointer next that points to the next node in the list. This allows nodes to be linked together to form a chain-like structure.

Top Pointer

struct Node* top = NULL;

the above code means that we are creating a pointer named top which will always point to the top element of a stack (implemented using a linked list). Initially, it is set to NULL, which means the stack is empty and no node is present yet.

Push Operation

void push(int value) { ... }

The above code help to add a new element to the top of the stack. To do this, first a new node is created using malloc and given the required value. Then, the new node’s next pointer is set to point to the current top, linking it with the previous stack elements. After that, the top pointer is updated to this new node, making it the new top of the stack. Finally, a message is displayed to show that the value has been successfully pushed.

Pop Operation

void pop() { ... }

The above code help to remove the top element from the stack. First, the program checks if the stack is empty by verifying if top == NULL; if it is empty, a message is displayed. Otherwise, the current top node is stored in a temporary pointer called temp. Then, the top pointer is moved to the next node (top = top->next) so that the top element changes. After that, the memory of temp is freed to completely remove the node from the stack. Finally, a message is printed to show the value that has been popped.

Peek Operation

void peek() { ... }

The above code help to see the top element of the stack without removing it. First, the program checks if the stack is empty; if it is, a message is shown to indicate that the stack has no elements. Otherwise, the value stored in top->data is displayed, which represents the current top element of the stack.

Display Operation

void display() { ... }

The above code help to print all the elements of the stack starting from the top and going down to the bottom. First, it checks if the stack is empty by verifying if the pointer top is NULL. If the stack is empty, it simply displays a message saying that the stack is empty. If it is not empty, a temporary pointer temp is created and set to point at top. Then, using a loop, the pointer temp moves through the stack one node at a time while printing the value stored in each node’s data. This process continues until temp becomes NULL, which means the end of the stack has been reached. In this way, the elements are printed in the correct order from the top to the bottom of the stack.

Time & Space Complexity

Time Complexity

Space Complexity