Implement a stack using a singly linked list

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we have to implement a stack, with the help of a singly linked list.

Input:

Output:
If the input is 4 3 2 1, then our singly linked list, which will have all functionalities of a stack, will be:

where the head of the linked list is pointing to the 1.

Problem Statement Understanding

Let’s see how a stack works.

  • It follows the LIFO(last in first out) principle, i.e., the element inserted last in the stack will be the first one accessible to us if we access elements from the stack.
  • Suppose we inserted elements in the stack in order 4,3,2,1, and now if we want to access elements from the stack, the order in which the elements will be accessible to us will be 1,2,3,4.

Now, let recall what a Singly Linked List is.

  • A Singly Linked List is a linear data structure containing nodes, and each node have a data part and a next pointer that points to the next node in the linked list.
  • If we can amend the inserting new node operation in a singly linked list in such a way that the current inserted element is always at the head of the linked list and is the first element accessible to us if we want to access an element from the linked list, then we can see that our linked list is mimicking the behavior of stack.
  • Similarly, we will try to think of other stack operations and how we can implement these operations using a singly linked list.

Let us have a glance at the algorithm.

Approach and Algorithm

There are mainly 5 functions of a stack. We will learn each function’s approach and algorithm one by one.

push()

  • In the push function, we push the element into the stack and make it the top.
  • So, to do the same with a singly linked list, we will check if the list is Null or not.
    • If it is Null, then make the new node the head.
    • If the list is not empty, then make the next of the new node point to the head of the list. In the end, make the new node the head of the list. In this way, we are first adding the element at the head, and then making it our head.

pop()

  • In the pop function, we pop the topmost element of the stack.
  • So, to do the same with a singly linked list, first, we will check if the list is Null or not.
    • If it is Null, then return NULL.
    • If there is only one node in the list, then remove the head, and return NULL.
    • If both the above base cases fail:
    • We will create a new node temp and make it point to the head.
    • Now, we will do head = head → next to make the 2nd node our new head.
    • After this, we will do temp → next = NULL, and free (temp).
    • In this way, we are making deleting the 1st node of the list and making the 2nd node our new head.
    • Remember - We are using 1 based indexing in the above approach.

peek()

  • In the peek function, we have to return the top element of the stack without deleting it.
  • So, to do the same with a singly linked list, first, we will check if the list is empty or not.
    • If the list is empty, we will simply exit as there is no data in the list.
    • If the list is not empty, we will just return the head → data, as it is the top element of the stack.

isEmpty()

  • In the isEmpty function, we have to check whether the stack is empty or not.
  • So, to do the same with a singly linked list, we will just check if the head is NULL or not.
    • If the head is NULL, it means that the list is empty, so we will return true.
    • If the head is not NULL, it means that the list is not empty, so we will return false.

display()

  • In the display function, we have to print the stack.
  • So, to do the same with a singly linked list, we will do a list traversal and print the elements of list one by one.

Dry Run

Code Implementation

#include 
using namespace std;


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

struct Node* top;

// Using this function we will be pushing elements into the stack
void push(int data)
{

    struct Node* tem;
    tem = new Node();

    if (!tem)
    {
        cout << "\nHeap Overflow";
        exit(1);
    }

    tem->data = data;

    tem->link = top;

    top = tem;
}

// Using this function we will be checking whether the stack is empty or not
int isEmpty()
{
    return top == NULL;
}

// Using this function we will return the top element of the stack
int peek()
{

    if (!isEmpty())
        return top->data;
    else
        exit(1);
}

// Using this function we will pop the top element of the stack
void pop()
{
    struct Node* tem;

    if (top == NULL)
    {
        cout << "\nStack Underflow" << endl;
        exit(1);
    }
    else
    {
        tem = top;

        top = top->link;

        tem->link = NULL;

        free(tem);
    }
}

// this function will be used to display the items of the stack
void display()
{
    struct Node* tem;

    if (top == NULL)
    {
        cout << "\nStack Underflow";
        exit(1);
    }
    else
    {
        tem = top;
        while (tem != NULL)
        {

            cout << tem->data << "-> ";

            tem = tem->link;
        }
    }
}

int main()
{
    push(4);
    push(3);
    push(2);
    push(1);
    display();

    cout << "\nTop element is "<< peek() << endl;

    pop();
    pop();

    cout<<"Stack after popping 2 times \n";
    display();

    cout << "\nTop element is "<< peek() << endl;
        
    return 0;
}
import static java.lang.System.exit;

class StackUsingLinkedlist {

    private class Node {

        int data;
        Node link; 
    }

    Node top;

    StackUsingLinkedlist()
    {
        this.top = null;
    }

    // Using this function we will be pushing elements into the stack
    public void push(int x) 
    {

        Node temp = new Node();

        if (temp == null) {
            System.out.print("\nHeap Overflow");
            return;
        }

        temp.data = x;

        temp.link = top;

        top = temp;
    }

    // Using this function we will be checking whether the stack is empty or not
    public boolean isEmpty()
    {
        return top == null;
    }

    // using this function we will return the top element of the stack
    public int peek()
    {

        if (!isEmpty()) {
            return top.data;
        }
        else {
            System.out.println("Stack is empty");
            return -1;
        }
    }

    // Using this function we will pop the top element of the stack
    public void pop() 
    {

        if (top == null) {
            System.out.print("\nStack Underflow");
            return;
        }

        top = (top).link;
    }

    // this function will be used to display the items of the stack
    public void display()
    {

        if (top == null) {
            System.out.printf("\nStack Underflow");
            exit(1);
        }
        else {
            Node temp = top;
            while (temp != null) {

                System.out.printf("%d->", temp.data);

                temp = temp.link;
            }
        }
    }
}

public class PrepBytes {
    public static void main(String[] args)
    {

        StackUsingLinkedlist stk = new StackUsingLinkedlist();

        stk.push(4);
        stk.push(3);
        stk.push(2);
        stk.push(1);

        stk.display();

        System.out.printf("\nTop element is %d\n", stk.peek());
        System.out.println("Stack after popping 2 times");
        stk.pop();
        stk.pop();

        stk.display();

        System.out.printf("\nTop element is %d\n", stk.peek());
    }
}

Output

1->2->3->4->
Top element is 1
Stack after popping 2 times
3->4->
Top element is 3

Time Complexity: All methods other than display() take O(1) time. The display() method takes O(N) time as we have to traverse the list to print the elements.

So, in this article, we have tried to explain the most efficient approach to implement a stack using a singly linked list. This is an important concept when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Doubly Circular Linked List Introduction and Insertion
Next post Insert a value in a sorted way in a sorted Doubly Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *