Last Updated on April 23, 2023 by Prepbytes
A stack is an abstract data type that follows the LIFO (Last In First Out) principle. It is widely used in computer science, programming languages, and operating systems. Implementing a stack using a singly linked list is a common exercise that helps to understand how linked lists work and how they can be used to implement other data structures. In this article, we will learn how to do stack implementation using singly linked list.
Understanding Stack Implementation Using Singly Linked List
When implementing a stack using singly linked list, it is essential to consider the standard operations of push, pop, and peek. The push operation involves adding an element to the top of the stack, while the pop operation removes the top element from the stack. The peek operation returns the value of the top element without removing it.
Suppose we insert elements 4, 3, 2, and 1 into the stack using the push operation. In push operation elements are added to the top of the stack. In other words, the last element to be pushed onto the stack becomes the top element, while the first element to be pushed becomes the bottom element. So, when elements are pushed onto the stack in that order, the top of the stack will contain element 1, and the bottom of the stack will contain element 4.
When we want to access the elements in the stack, we can only access them in a LIFO (Last-In-First-Out) manner, meaning that we can only access the top element first, followed by the second-to-top element, and so on. In other words, we must first remove the top element using the pop operation to access the next element in the stack.
So, to access the elements in the order 1, 2, 3, and 4, we would need to pop the elements from the stack in reverse order, starting with 1, then 2, then 3, and finally 4. This is because the top of the stack currently contains element 1, so it must be popped first to access the next element, which is 2. The below image shows how these elements are represented in a singly linked list.
Overall when accessing elements in a stack, we can only access them in reverse order of insertion, starting with the last element pushed onto the stack.
Approach of Stack Implementation Using Singly Linked List
The approach and algorithm for implementing a stack using singly linked list involves five main functions: push, pop, peek, isEmpty, and display.
-
push() Function
The push function adds an element to the top of the stack. To implement this function with a singly linked list, we first check if the list is empty. If it is, we make the new node the head of the list. If the list is not empty, we make the next of the new node point to the head of the list and then make the new node the new head of the list. -
pop() Function
The pop function removes the topmost element of the stack. To implement this function with a singly linked list, we first check if the list is empty. If it is, we return NULL. If there is only one node in the list, we remove the head and return NULL. If there is more than one node in the list, we create a new node temp and make it point to the head. Then, we make the 2nd node our new head by doing head = head → next. Finally, we make temp → next = NULL, and free (temp). -
Peek() Function
The peek function returns the top element of the stack without deleting it. To implement this function with a singly linked list, we first check if the list is empty. If it is, we simply exit as there is no data in the list. If the list is not empty, we just return the head → data, as it is the top element of the stack. -
isEmpty() Function
The isEmpty function checks whether the stack is empty or not. To implement this function with a singly linked list, we 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() Function
The display function prints the stack. To implement this function with a singly linked list, we do a list traversal and print the elements of the list one by one.
Dry Run of Implementing Stack Using Singly Linked List
Code Implementation of Stack Using Singly Linked List
Now, let’s see how to implement stack using singly linked list in C, C++, Java, and Python:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
}*top;
/*
Initialize an empty stack
*/
void initialize() {
top = NULL;
}
/*
Checks if Stack is empty or not
*/
int isEmpty() {
if (top == NULL)
return 1;
else
return 0;
}
/*
Returns the top element of Stack
*/
int peek() {
return top->data;
}
/* Count stack elements */
int getStackSize(struct node *head){
/* Input Validation */
if (head == NULL) {
printf("Error : Invalid stack pointer !!!\n");
return;
}
int length = 0;
while(head != NULL){
head = head->next;
length++;
}
return length;
}
/*
Push an Element in Stack
*/
void push(int num) {
struct node *temp;
temp =(struct node *)malloc(1*sizeof(struct node));
temp->data = num;
if (top == NULL) {
top = temp;
top->next = NULL;
} else {
temp->next = top;
top = temp;
}
}
/*
Pop Operation: Removes Top Element of the Stack
*/
void pop() {
struct node *temp;
if (isEmpty(top)) {
printf("\nStack is Empty\n");
return;
} else {
temp = top;
top = top->next;
printf("Removed Element : %d\n", temp->data);
free(temp);
}
}
/*
Prints the linked list representation of a stack
*/
void printStack(struct node *nodePtr) {
while (nodePtr != NULL) {
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf("-->");
}
printf("\n");
}
void main() {
/* Initialize Stack */
initialize();
/* Push Elements in stack */
push(1);
push(2);
push(3);
push(4);
/* Prints Size of Stack */
printf("Stack Size : %d\n", getStackSize(top));
/* Printing top element of Stack */
printf("\nTop Element : %d\n", peek());
/* Printing Stack */
printf("Stack as linked List\n");
printStack(top);
/* Removing elements from stack */
pop();
pop();
pop();
pop();
pop();
printStack(top);
return;
}
#include <bits stdc++.h="">
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());
}
}
class Node:
def __init__(self,data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def isempty(self):
if self.head == None:
return True
else:
return False
def push(self,data):
if self.head == None:
self.head=Node(data)
else:
newnode = Node(data)
newnode.next = self.head
self.head = newnode
def pop(self):
if self.isempty():
return None
else:
poppednode = self.head
self.head = self.head.next
poppednode.next = None
return poppednode.data
def peek(self):
if self.isempty():
return None
else:
return self.head.data
def display(self):
iternode = self.head
if self.isempty():
print("Stack Underflow")
else:
while(iternode != None):
print(iternode.data,"->",end = " ")
iternode = iternode.next
return
MyStack = Stack()
MyStack.push(4)
MyStack.push(3)
MyStack.push(2)
MyStack.push(1)
MyStack.display()
print("\nTop element is ",MyStack.peek())
MyStack.pop()
MyStack.pop()
print("Stack after poping 2 times")
MyStack.display()
print("\nTop element is ", MyStack.peek())
Output:
1->2->3->4->
Top element is 1
Stack after popping 2 times
3->4->
Top element is 3Complexity Analysis of Stack Implementation Using Singly Linked List
Let’s analyze the time and space complexity of each operation in the implementation of a stack using linked list.
-
push() Operation:
Since we always add a new element at the top of the stack, this operation takes constant time. We only need to allocate memory for the new node, set its data, and update the "next" pointer to the current top of the stack.Time complexity: O(1)
Space complexity: O(1)We only allocate memory for the new node, so the space complexity of the push operation is constant.
-
pop() Operation:
Since we always remove the top element of the stack, this operation takes constant time. We only need to update the "top" pointer to the next node and free the memory of the removed node.Time complexity: O(1)
Space complexity: O(1)We only remove a node from the stack, so the space complexity of the pop operation is constant.
-
peek() Operation:
This operation only returns the value of the top element, so it takes constant time.Time complexity: O(1)
Space complexity: O(1)We don’t need to allocate or remove any memory, so the space complexity of the peek operation is constant.
-
isEmpty() Operation:
This operation only checks if the "top" pointer is null or not, so it takes constant time.Time complexity: O(1)
Space complexity: O(1)We don’t need to allocate or remove any memory, so the space complexity of the isEmpty operation is constant.
-
getStackSize() Operation:
We need to traverse the whole linked list to count the number of nodes, so the time complexity of this operation is linear to the size of the stack.Time complexity: O(n)
Space complexity: O(1)We don’t allocate or remove any extra memory, so the space complexity of the getStackSize operation is constant.
Overall, the time and space complexity of operations of a stack using singly linked list are efficient and provide good performance.
Conclusion
In conclusion, the implementation of a stack using singly linked list is an efficient way to perform various stack operations such as push, pop, peek, and check if the stack is empty. The linked list implementation has a time complexity of O(1) for insertion and deletion operations, and the space complexity increases linearly with the number of elements in the stack. Overall, the stack implementation using singly linked list is a practical and efficient way to perform stack operations. If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.
FAQs Related to Stack
Here are some frequently asked questions related to stack implementation using singly linked lists.
Q1: How do you push an element into an implementation of stack using singly linked list?
Answer: To push an element into an implementation of stack using singly linked list, you need to create a new node and set its data field to the value you want to push. Then, you set its next field to the current head of the linked list and update the head of the linked list to point to the new node.
Q2: How do you pop an element from the implementation of stack using singly linked list?
Answer: To pop an element from the implementation of stack using singly linked list, you simply remove the head of the linked list and update the head of the linked list to point to the next element in the stack.
Q3: How do you handle stack overflow in a stack implementation using singly linked list?
Answer: Since a linked list can grow dynamically, stack overflow is not typically a concern when implementing a stack using singly linked list.
Q4: How do you handle memory leaks in a stack implementation using singly linked list?
Answer: To avoid memory leaks in a stack implementation using singly linked list, you should always free the memory allocated for each node when it is removed from the stack.
Q5: How do you handle concurrent access to a stack implementation using singly linked list?
Answer: To handle concurrent access to a stack implemented using singly linked list, you should use a locking mechanism such as a mutex to ensure that only one thread can access the stack at a time.
Q6: How do you handle data corruption in an implementation of a stack using singly linked list?
Answer: Data corruption can occur if the pointers in the linked list become invalid due to memory errors or other issues. To avoid data corruption in the implementation of stack using singly linked list, you should always check the validity of pointers before dereferencing them.