In Data structures we have seen how the memory is dynamic in linked lists,Stacks and queues. Now let’s just look at how to implement data structures i.e stacks using other data structures i.e linked lists. In the below article lets just see the implementation of stack using linked list

### Problem Statement of stack using singly linked list

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 of the implementation of stack using linked list

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 of stack using singly linked list

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 2^{nd}node our new head. - After this, we will do
**temp → next = NULL**, and free (temp). - In this way, we are making deleting the 1
^{st}node of the list and making the 2^{nd}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 of stack using singly linked list

### Code Implementation implementation of stack using linked list

#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 of implementation of stack using linked list

1->2->3->4->

Top element is 1

Stack after popping 2 times

3->4->

Top element is 3

**Time Complexity of stack using singly linked list:** 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.

### Conclusion

So, in this article, we learned that one data structure can be used to implement another data structure. We have seen how the implementation of stack using singly linked list works. 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.

## FAQs

- What is peek() in Linked list?
- What is pollLast() in the linked list?
- Why linked list is used to implement the stack not array?

**Ans.** The peek() method retrieves the first head of the list, but it does not remove the head.

**Ans.** This method removes or retrieves the last element of the list, and returns null if the list is empty.

**Ans.** We already know that array’s memory is already predetermined unlike the linked list where the memory can shrink or grow accordingly.