Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Implement a Stack using a Singly Linked List

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.

1. 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.

2. 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).

3. 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.

4. 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.

5. 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.

### 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() {
}

/* Count stack elements */
/* Input Validation */
printf("Error : Invalid stack pointer !!!\n");
return;
}

int length = 0;
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 */
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* 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;

top = tem;
}

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

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

if (!isEmpty())
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;

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 << "-> ";

}
}
}

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;

private class Node {

int data;
}

Node top;

{
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;

top = temp;
}

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

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

if (!isEmpty()) {
}
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;
}

}

// 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);

}
}
}
}

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

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):

def isempty(self):
return True
else:
return False

def push(self,data):

else:
newnode = Node(data)

def pop(self):

if self.isempty():
return None

else:

poppednode.next = None
return poppednode.data

def peek(self):

if self.isempty():
return None

else:

def display(self):

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 3``````

### Complexity 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.

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.