Do you think IIT Guwahati certified course can help you in your career?
Introduction
A Stack is one of the most fundamental and extremely used Data structures. Linked Lists also fall in the same category as stacks having a wide range of usages. There are various ways of implementing a stack, it may be using a Queue, an Array, or any other Data Structure. In this article, we are going to take a look at how to implement a Stack using a Linked List.
Problem Statement
Implement stack using a singly linked list that supports the basic operations of stack data structure such as push(), pop(), top(), isEmpty(), and follows the last in first out order(LIFO).
Basic operations of stack
push(): it pushes an element into the stack data structure.
pop(): it removes the top element of the stack.
top_element(): it gives the value of the top element of the stack.
isEmpty(): it returns true if the stack is empty else returns false.
print_stack(): it prints the contents of the stack in LIFO order.
Algorithm of Stack Implementation Using Singly Linked List
To implement a stack using a singly linked list, we make some changes in the singly linked list to make it work as a stack. Here the top of the stack is the head of the linked list. Initially, the head pointer of the linked list is pointing to NULL.
push() Operation:
We attach the new node in front of the linked list to follow LIFO(last in first out) order like the stack data structure.
Steps:
Create a new node temp.
Point temp’s next as the head, temp->next = head.
Finally, make the temp node as the new head, head = temp.
Example:
push(5)
Initially, the head of the linked list = NULL.
Create a temp node of the given value
temp->next = head
head = temp
push(3)
Repeat the above steps.
pop() Operation:
We remove the elements from the front of the linked list to follow the LIFO( last in first out) order as the stack data structure.
Steps:
If the head is NULL, print “stack is empty”.
Else create a temp node and store the head in the temp node.
Make head as the head’s next node, head = head->next.
Delete the temp node.
Example:
Initially, the linked list is:
pop()
Steps:
Create a temp node and store the head of the list in it.
head = head->next.
Delete temp.
top_element() Operation:
If the linked list is empty, print “stack is empty”. Else return the data of the head node.
isEmpty() Operation:
If the head is pointing to the NULL, return true else, return false.
print_stack() Operation:
Steps:
Declare a curr pointer pointing to the head of the list.
Run a while loop till curr!=NULL.
Print the curr->data and do curr=curr->next.
You can also watch our video on this topic for a visual understanding of the agenda at hand.
Code in C++
C++
C++
#include <bits/stdc++.h> using namespace std;
struct node { int data; node* next; };
struct node* head = NULL;
void push(int x) { node* temp; temp = new node(); temp->data = x; temp->next = head; head = temp; }
// Main class public class Main { static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } }
StackNode root;
// Push method push element to the head of linked list public void push(int data) { StackNode newNode = new StackNode(data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } }
// pop method pop element from head and return it's data public int pop() { int popped; if (root == null) { System.out.println("Stack is Empty"); return 0; } else { popped = root.data; root = root.next; return popped; } }
// top_element will return the top of the stack public int top_element() { if (root == null) { System.out.println("Stack is empty"); return Integer.MIN_VALUE; } else { return root.data; } }
public static void main(String[] args) { Main obj = new Main(); obj.push(5); obj.push(2); obj.push(8); obj.push(7);
# Node class class Node: def __init__(self,data): self.data = data self.next = None
# Stack class class Stack:
# constructor initializing head with None def __init__(self): self.head = None
# Checks if stack is empty def isempty(self): return True if self.head == None else False
# push method adds element to the start of stack def push(self,data): if self.head == None: self.head=Node(data) else: new_node = Node(data) new_node.next = self.head self.head = new_node
# returns the data of the head node def topElement(self): if self.isempty(): return None else: return self.head.data
# pop method will remove the current head and return its value def pop(self): if self.isempty(): return None else: popped_node = self.head self.head = self.head.next popped_node.next = None return popped_node.data
push(): O(1), as we are not traversing the whole list.
pop(): O(1), as we are not traversing the entire list.
isEmpty(): O(1), as we are checking only the head node.
top_element(): O(1), as we are printing the head node.
print_stack(): As we are traversing through the whole list it will be O(n), where n is the number of nodes present in the linked list.
Space complexity: O(1), as we require constant extra space.
Benefits of implementing a stack using a singly linked list:
There are several advantages to implementing a stack using a singly linked list compared to an array-based approach:
Dynamic Size: Unlike arrays, which have a fixed size defined at allocation, a singly linked list can grow or shrink as needed. This makes it ideal for situations where the size of the stack is unknown beforehand or can vary significantly during program execution. No risk of stack overflow due to exceeding the predefined size.
Efficient Memory Management: Linked lists only allocate memory for the nodes they contain, leading to more efficient memory utilization. Arrays might reserve extra space even if not fully used. This is particularly beneficial for large stacks or when memory resources are limited.
Ease of Insertion and Deletion: Since insertion and deletion in a linked list happen at the beginning (top of the stack), these operations are very efficient. Only the head pointer needs to be updated, requiring minimal modifications to the existing list structure.
No Fragmentation: Unlike arrays, where deleted elements leave gaps leading to fragmentation, linked lists do not suffer from this issue. Memory allocation and deallocation are simpler as nodes can be easily removed without affecting the overall structure.
Simpler Implementation: The logic for implementing basic stack operations (push and pop) using a singly linked list is often considered simpler and more intuitive compared to an array-based approach.
A stack is a linear data structure in which operations are performed in a specific order. The order can be LIFO (last-in, first-out) or FILO (first in, first out) (First In Last Out).
What does the stack work?
A stack is a type of linear data structure in which elements are stacked on top of one another. Only the most recent element added, i.e. the element at the top of the stack, can be accessed. A stack, in other words, is a Last In First Out (LIFO) structure. It is the inverse of a queue, which operates on a first-come, first-served basis (FIFO).
Conclusion
So, this article discussed the approach to implementing a stack using a singly linked list and all the steps to implement the basic operations of the stack like push(), pop(), top(), and isEmpty() with examples and code in C++.
310+ registered 
