Stack implementation using Linked List in C++

In this tutorial, we are going to see how to implement a stack using a linked list in C++.

A stack is an ordered collection of the items where addition of new items and the removal of existing items always takes place at the same end. This end is called “top”. Stack follows the last-in-first-out (LIFO) principle.

Whereas, a linked list is a linear collection of data elements. It is a data structure consisting of a collection of nodes that together represent a sequence.

 

C++ implementation of Stack using Linked List

In a linked list, elements can be inserted at any position and can be deleted from any position while in a stack insertion and deletion happens from one end only which is known as the top of the stack.

To make our linked list act like a stack we have to restrict some functions of the linked list that cannot be implemented on a stack. And we also have to make sure that insertion and deletion in the linked list happen from one end only.

For insertion/deletion there are two options:

  1. Insertion/Deletion on the end:
    Like when we implemented stack using an array the insertion and deletion happened at the end of an array. If we tried to do the same with the linked list, every time a new element is inserted or deleted we have to iterate to the end of the linked list (because in a linked list we only have access to head pointer) so that we can access the last element and perform insertion/deletion.
    If we go with this process the complexity of insertion and deletion will be O(n), where ‘n’ is the number of nodes in the linked list.
  2. Insertion/Deletion on the front:
    We can insert/delete elements from the front of in constant time (that is O(1)).
    For insertion, we just have to make the new node point to the address head is pointing and then making the head point to the new node.
    For deletion, we just have to make the head pointer point to the address of the next node.

From the above explanation, we can see that the most optimized way is to insert and delete elements from the front.

Now let’s see the implementation.

 

IMPLEMENTATION

Let’s see the functions used in the code:

  1. push():
    creates a new node, inserts its value, and then inserts the new node in the front of the linked list.
  2. pop():
    deletes the fist node present in the linked list.
  3. topStack():
    shows the value of the first node present in the linked list.

Code:

#include<bits/stdc++.h>
using namespace std;

//structure of each node of the linked list
struct node
{
    int data;
    struct node *next;
};

//inserts a new element in the linked list
node *push(node *head)
{
    node *newnode;

    //allocating memory for the new node
    newnode = (node *)malloc(sizeof(node));

    //it checks whether the memory is allocated or not
    if (!newnode)
        return head;
    
    //assiging value to the new node
    cout<<"Enter the element to be pushed: ";
    cin>>newnode->data;
    newnode->next=NULL;

    //when the linked list is empty
    /*we just have to make the head to point to the new node*/
    if (head==NULL)
        head=newnode;

    //when the linked list is not empty 
    /*we first have to make the new node to point the 
    current address head is pointing and after that making 
    the head pointer to point to the newnode*/
    else
    {
        newnode->next=head;
        head=newnode;
    }

    return head;
}

//deletes the most recently inserted node from the linked list
node *pop(node *head)
{
    //when linked list is empty
    if (head==NULL)
    {
        cout<<"Stack is empty";
        return head;
    }

    /*to delete an element we just have to make the head pointer to 
    point to the next memory location in this way we lose our access
    to the previous element*/
    /*here we store the node to be deleted in temp so that we can free 
    up the memory, because after deletion the node is
    of no use to us*/
    node *temp=head;
    head=head->next;
    free(temp);
    cout<<"Element deleted";
    return head;
}

//displays the value of most recently inserted node
void topStack(node *head)
{
    //when linked list in empty
    if (head==NULL)
    {
        cout<<"Stack is empty";
        return;
    }

    //displaying the value of the first node
    cout<<"Element at the top of the stack: ";
    cout<<head->data;
}

int main()
{

    /*unlike array when implementing stack using the linked list 
    we don't have to pre-allocate space as a linked list is a 
    dynamic data structure*/

    //initially head will be at NULL which signifies linked list is empty
    node *head=NULL;
    
    while (1)
    {
        cout << "\n\n1-Push an element";
        cout << "\n2-Pop an element";
        cout << "\n3-Top of the stack";
        cout << "\n4-Exit";
        cout << "\nChoose the option: ";
        int num;
        cin >> num;
        cout << "\n";
        if (num == 1)
            head=push(head);
        else if (num == 2)
            head=pop(head);
        else if (num == 3)
            topStack(head);
        else if (num == 4)
            break;
        else
            cout << "Invalid entry";
    }
    return 0;
}

Input/Output:

1-Push an element  
2-Pop an element   
3-Top of the stack 
4-Exit
Choose the option: 1

Enter the element to be pushed: 1


1-Push an element  
2-Pop an element   
3-Top of the stack 
4-Exit
Choose the option: 1

Enter the element to be pushed: 2


1-Push an element  
2-Pop an element   
3-Top of the stack 
4-Exit
Choose the option: 1

Enter the element to be pushed: 3


1-Push an element  
2-Pop an element   
3-Top of the stack 
4-Exit
Choose the option: 3

Element at the top of the stack: 3

1-Push an element
2-Pop an element
3-Top of the stack
4-Exit
Choose the option: 2 

Element deleted

1-Push an element
2-Pop an element
3-Top of the stack
4-Exit
Choose the option: 2

Element deleted

1-Push an element
2-Pop an element
3-Top of the stack
4-Exit
Choose the option: 3

Element at the top of the stack: 1

1-Push an element
2-Pop an element
3-Top of the stack
4-Exit
Choose the option: 4

Time Complexity:
push() = O(1)
pop() = O(1)
topStack() = O(1)

Space Complexity:
Space Complexity = O(n)
where
n -> number of nodes in the linked list

Leave a Reply