Stack Implementation Using Linked List.

Implementing a stack using a linked list involves utilizing the dynamic nature of linked lists to create a Last-in, First Out (LIFO) data structure. A linked list, comprising nodes where each node contains data and a reference to the next node, is ideal for stack implementation due to its efficient insertion and deletion at the beginning or to the top of a stack.

In this article, we will discuss how to perform push, pop, peek, isEmpty, and size operations of a stack using a linked list.

To implement a stack using a linked list we need to create nodes that will contain a value and a reference to the next node and we also need a top pointer to point to the topmost node that will help us in further push and pop operation. Initially, our top pointer pointed to null as the stack is empty.

Stack Operations using Linked List.

Push operation: The push operation involves adding an element to the top of the stack. This process begins by creating a new node and linking it to the current top node. The newly created node becomes the new top of the stack, updating the top pointer to this newly added node. This operation has a constant time complexity of O(1), irrespective of the stack's size.

Pop operation: The pop operation removes the top element from the stack. It starts by checking if the stack is empty. If not, it removes the top node, reassigning the top pointer to the subsequent node in the linked list. This constant-time operation O(1) effectively removes the element from the stack, ensuring adherence to the LIFO principle.

Peek operation: The peek (or top) operation retrieves the top element without removing it. It simply returns the value of the top node, allowing users to view the element at the stack's top without altering the stack's structure.

IsEmpty operation: The isEmpty operation inspects whether the stack is empty by checking if the top pointer is null, promptly determining the stack's status without traversing the entire linked list.

Size operation: The size operation determines the number of elements in the stack. It traverses the entire linked list while incrementing a counter for each node encountered. This operation exhibits a linear time complexity O(n), directly proportional to the number of elements in the stack.

Below is the code implementation of the above stack operations using Linked List.

C++ Java Python C#

// C++ code implementation for stack using linked list
#include <iostream>
using namespace std;

// Node class for the linked list
class Node {
public:
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

// Stack class using linked list
class Stack {
private:
    Node* top;

public:
    Stack() : top(nullptr) {}

    // Push operation
    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = top;
        top = newNode;
    }

    // Pop operation
    void pop() {
        if (isEmpty()) {
            cout << "Stack is empty. Cannot pop." << endl;
            return;
        }
        Node* temp = top;
        top = top->next;
        delete temp;
    }

    // Check if the stack is empty
    bool isEmpty() {
        return top == nullptr;
    }

    // Display the top element of the stack
    void peek() {
        if (isEmpty()) {
            cout << "Stack is empty." << endl;
            return;
        }
        cout << "Top element: " << top->data << endl;
    }
};

int main() {
    // Example usage of the stack
    Stack stack;

    // Push elements onto the stack
    stack.push(1);
    stack.push(2);
    stack.push(3);

    // Display the top element
    stack.peek();

    // Pop an element
    stack.pop();

    // Display the top element after pop
    stack.peek();

    return 0;
}

// Java code implementation for stack using Linked list
public class Main {
  // Node class for the linked list
  static class Node {
      int data;
      Node next;
      Node(int value) {
          data = value;
          next = null;
      }
  }

  // Stack class using linked list
  static class Stack {
      private Node top;

      // Push operation
      void push(int value) {
          Node newNode = new Node(value);
          newNode.next = top;
          top = newNode;
      }

      // Pop operation
      void pop() {
          if (isEmpty()) {
              System.out.println("Stack is empty. Cannot pop.");
              return;
          }
          top = top.next;
      }

      // Check if the stack is empty
      boolean isEmpty() {
          return top == null;
      }

      // Display the top element of the stack
      void peek() {
          if (isEmpty()) {
              System.out.println("Stack is empty.");
              return;
          }
          System.out.println("Top element: " + top.data);
      }
  }

  public static void main(String[] args) {
      // Example usage of the stack
      Stack stack = new Stack();

      // Push elements onto the stack
      stack.push(1);
      stack.push(2);
      stack.push(3);

      // Display the top element
      stack.peek();

      // Pop an element
      stack.pop();

      // Display the top element after pop
      stack.peek();
  }
}

# Python code implementation of stack using linked list
class Node:
def __init__(self, value):
    self.data = value
    self.next = None

class Stack:
def __init__(self):
    self.top = None

# Push operation
def push(self, value):
    new_node = Node(value)
    new_node.next = self.top
    self.top = new_node

# Pop operation
def pop(self):
    if self.is_empty():
        print("Stack is empty. Cannot pop.")
        return
    self.top = self.top.next

# Check if the stack is empty
def is_empty(self):
    return self.top is None

# Display the top element of the stack
def peek(self):
    if self.is_empty():
        print("Stack is empty.")
        return
    print("Top element:", self.top.data)

# Example usage of the stack
stack = Stack()

# Push elements onto the stack
stack.push(1)
stack.push(2)
stack.push(3)

# Display the top element
stack.peek()

# Pop an element
stack.pop()

# Display the top element after pop
stack.peek()

// C-Sharp  code implementation for stack using linked list
using System;

// Node class for the linked list
public class Node {
    public int Data;
    public Node Next;

    public Node(int value) {
        Data = value;
        Next = null;
    }
}

// Stack class using linked list
public class Stack {
    private Node top;

    // Push operation
    public void Push(int value) {
        Node newNode = new Node(value);
        newNode.Next = top;
        top = newNode;
    }

    // Pop operation
    public void Pop() {
        if (IsEmpty()) {
            Console.WriteLine("Stack is empty. Cannot pop.");
            return;
        }
        top = top.Next;
    }

    // Check if the stack is empty
    public bool IsEmpty() {
        return top == null;
    }

    // Display the top element of the stack
    public void Peek() {
        if (IsEmpty()) {
            Console.WriteLine("Stack is empty.");
            return;
        }
        Console.WriteLine("Top element: " + top.Data);
    }
}

class Program {
    static void Main() {
        // Example usage of the stack
        Stack stack = new Stack();

        // Push elements onto the stack
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);

        // Display the top element
        stack.Peek();

        // Pop an element
        stack.Pop();

        // Display the top element after pop
        stack.Peek();
    }
}

Output:

Top element: 3
Top element: 2

Time Complexity: All stack operations like, push, pop, peek, and isEmpty take O(1) constant time as it doesn't rely on traversal. But for counting the number of nodes in the stack take O(n) time as we need to traverse the complete list.

Space Complexity: O(n) where n represents the number of elements in the stack. Each node in the linked list consumes space for value and a reference to the next node.

Related Post: Stack Implementation using Array.

Benefits of Stack Implementation using LinkedList.

• Dynamic Memory Allocation: Linked lists allow dynamic memory allocation, accommodating a varying number of elements without predefining a fixed size, providing flexibility.

• Efficient Insertions and Deletions: Push and pop operations in linked lists execute in constant time, making them efficient for stack implementations.

• Simplicity and Ease of Use: Implementing a stack using a linked list is relatively straightforward and easy to understand, aiding in code readability and maintenance.

• No Memory Wastage: Linked lists utilize memory efficiently by allocating space only as needed for elements, preventing memory wastage.

Deletion in Singly Linked List in C++.

We have discussed Insertion and Searching a node in a singly Linked List in our previous post. In this post, we are going to discuss the Deletion of a node in a Linked List.

There are multiple situations of deleting a node from a linked list and these are:

• Deletion of a node from the middle of the list.

Input: 3->8->1->2
Output: 3->8->2

• Deletion of a node from the end of the list.

Input: 3->8->1->2
Output: 3->8->1

• Deletion of a node from the beginning of the list.

Input: 3->8->1->2
Output: 8->1->2

Approach for Deletion of a node.

In a singly linked list, deletion is performed by modifying the pointers of the preceding and subsequent nodes to bypass the node to be deleted. Below are the steps to follow:

• The deletion method takes integer data as an argument and searches the list for the node with the matching data. 
• If the head node contains the data, the node is deleted and the head is updated to point to the next node. 
• If the data is found in another node, the pointers of the preceding and subsequent nodes are modified to bypass the node to be deleted, and the node is deleted.

C++ Code to Delete a node from Singly Linked List.

//C++ Program to delete the node from a linked list
#include <iostream>
using namespace std;

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

class SinglyLinkedList {
private:
  Node *head;

public:
  SinglyLinkedList() : head(nullptr) {}

  void insert(int data) {
    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = head;
    head = newNode;
  }

  void deleteNode(int data) {
    //when list is empty
    if (head == nullptr) return;
    //deleting first node of the list
    if (head->data == data) {
      Node *temp = head;
      head = head->next;
      delete temp;
      return;
    }
    //deleting middle or last node of the list
    Node *prev = head;
    Node *curr = head->next;
    while (curr != nullptr && curr->data != data) {
      prev = curr;
      curr = curr->next;
    }
    if (curr == nullptr) return;
    prev->next = curr->next;
    delete curr;
  }

  void printList() {
    Node *temp = head;
    while (temp != nullptr) {
      cout << temp->data << " ";
      temp = temp->next;
    }
    cout << std::endl;
  }
};

int main() {
  SinglyLinkedList list;

  list.insert(10);
  list.insert(20);
  list.insert(30);
  list.insert(40);
  list.insert(50);
  list.printList();
  list.deleteNode(30);
  list.printList();
  return 0;
}

Output:

50 40 30 20 10
50 40 20 10

• Time Complexity: O(n)
• Space Complexity: O(1)

Searching in Singly Linked List in C++.

Given a singly integer Linked List having n number of nodes and a key value. You need to search the key value in the given linked list and return true if the key is present in the list otherwise return false.

Example:
Input: 10->15->9->12->20->11, key = 15
Output: True

Input: 12->32->8->10, key = 11
Output: False

Searching an element in a Linked List.

Unlike an array, a linked list does not provide random access so you need to traverse the entire linked list from the first node. You need to keep comparing the value present in each node with the given key value until you found the value. This process is the same as performing a linear search on Linked List. 

Follow the below steps to search for the key value:

• Create a temp pointer and initialize it with the head. 
• Run a while loop with condition temp not equal to NULL.
• Compare the value present in the temp node with the key value and return true if the value matches else move to the next node. (temp = temp->next)
• Return false if the key value is not found in the list. 

Below is the C++ code for searching for an element in a Linked List.

//C++ Example of Searching in Singly Linked List
#include<iostream>
using namespace std;

class Node{
    public:
    int data;
    Node *next;
    //constructor
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};

//Adding node at the end of the list
Node *insertEnd(Node *head, int data){
    //create a new node
    Node *new_node = new Node(data);
    Node *temp = head;
    //when list is empty
    if(temp == NULL){
        head = new_node;
    }
    else{
        while (temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = new_node;
    }
    return head;
}
//Searching a key in linked list
bool searchList(Node *head, int key){
    //when list is empty
    if(head == NULL){
        return false;
    }
    //when list is not empty
    else{
        Node *temp = head;
        while (temp != NULL){
            if(temp->data == key)
              return true;
            temp = temp->next;  
        }
    }
    return false;
}
//Traversing Linked List
void display(Node *head){
    Node *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}

int main(){
    Node *head = NULL;
    head = insertEnd(head, 12);
    head = insertEnd(head, 13);
    head = insertEnd(head, 22);
    head = insertEnd(head, 25);
    head = insertEnd(head, 10);

    cout<<"Linked List: ";
    display(head);

    cout<<"\nKey is present in the list: ";
    if(searchList(head, 25))
       cout<<"True"<<endl;
    else
       cout<<"False"<<endl;   

    return 0;   
}

Output:

Linked List: 12 13 22 25 10
Key is present in the list: True

• Time Complexity: O(n), here is the number of nodes present in the linked list.
• Space Complexity: O(1) 

Insertion in Singly Linked List in C++

In the previous post, we discussed the Singly Linked List and the operations that we can perform it. Here we are going to discuss the insertion of new nodes in a singly linked list in detail. 

There are three ways of inserting a new node into a Linked List and these are, 

• Adding a node at the beginning of the list.
• Adding a node after a given position in the list.
• Adding a node at the end of the list.

Structure of our node using C++ class:

class Node{
    public:
    int data;
    Node *next;
    //constructor
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};

1. Adding a node at the beginning of the Linked List.

A head pointer is used in the linked list that always points to the first node of the list and when we add a new node in front the new node becomes the first node and now the head pointer should point to this new node. You can follow the below three steps to add a new node at the front of the list. 

• Create a new node and store the data value in the first part of the node and the second part is initially pointing to NULL. 

//create a new node and initialize data value using constructor
Node *new_node = new Node(data);

• Point the next pointer of the newly created node to the existing first node whose address is present inside the head pointer. 

new_node->next = head;

• Update the value of the head pointer with the address of our new node as the head always points to the first node of the list. 

head = new_node;

2. Adding a node at a position in the Linked List.

You can follow the below steps to insert a new node at a specified position in the Singly Linked List. 

• Traverse the given list and reach the position-1 node and mark that node as current.
• Create a new node with the given data value and the next pointer initially pointing to NULL.
• Point the next pointer of the new node to the next of the current node.
• Point the next pointer of the current node to the newly created node. 

3. Adding a node at the end of the Linked List.

This is the most common way of adding a new node to the list because whenever we create a new node we prefer to add it at the end of the list. You can follow the below steps to add a new node at the end of a singly linked list.

• Traverse a given list using a temp pointer till you reach the end of the list. 
• Create a new node with the given data value and the next pointer of the new node pointing to NULL.
• Point the next pointer of the temp node to the new node and the next pointer of the new node is already pointing to NULL. 

Complete C++ program of Inserting a new node in a Singly Linked List.

//C++ Example of Insertion in Singly Linked List
#include<iostream>
using namespace std;

class Node{
    public:
    int data;
    Node *next;
    //constructor
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};

//Add a node to the front of list
Node *insertFront(Node *head, int data){

    Node *new_node = new Node(data);
    //add a new node when list is empty
    if(head == NULL)
      head = new_node;
    //adding new node at the front of the list  
    else{
        new_node->next = head;
        head = new_node;
    }
    return head;  
}
//Add a node after the position
Node *insertPos(Node *head, int pos, int data){
    int count = 0;
    Node *current = head;

    //Adding a node in empty list
    if(current == NULL){
        Node *new_node = new Node(data);
        head = new_node;
    }
    //Adding a node after given position
    else{
        while (count != pos-1)
        {
            current = current->next;
            count++;
        }
        Node *new_node = new Node(data);
        new_node->next = current->next;
        current->next = new_node;
    }
    return head;
}
//Adding node at the end of the list
Node *insertEnd(Node *head, int data){
    //create a new node
    Node *new_node = new Node(data);
    Node *temp = head;
    //when list is empty
    if(temp == NULL){
        head = new_node;
    }
    else{
        while (temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = new_node;
    }
    return head;
}

//Traversing Linked List
void display(Node *head){
    Node *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}

int main(){
    Node *head = NULL;
    head = insertFront(head, 10);
    head = insertFront(head, 13);
    head = insertEnd(head, 22);
    head = insertEnd(head, 23);
    head = insertFront(head, 33);
    head = insertPos(head, 3, 32);

    cout<<"Singly Linked List: ";
    display(head);
    return 0;    
}

Output:

Singly Linked List: 33 13 10 32 22 23

• Time Complexity: Adding a node at the front of the list takes O(1) time whereas adding a node at the end or in between the list takes O(n) time in worst cases. 
• Space Complexity: No extra space is required to perform any insertion operation so space complexity will be O(1).

Singly Linked List in C++

A singly Linked List is the simplest linked list in which you can traverse the list only in one direction from head to the last node.

A Linked List is a linear data structure in which each element is stored in the form of a node and each node contains two parts, one part is to store the data and another part contains a pointer pointing to the next node (the pointer holds the address of the next node). 

Unlike an array, in linked list nodes are not stored at a contiguous memory location. All nodes are linked using pointers and form a linear structure. We use a head pointer that always points to the first node of the list and it is used to traverse the linked list. The last node of the list points to null that indicates the end of the list. 

List of Operations on Singly Linked List.

1. Creating a new List.

Create a class Node with two attributes one is data and the other one is a node. The data is used to store elements and the node is a pointer pointing to the next node.

class Node{
    public:
    int data;
    Node *next;
    //constructor
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};

As we are creating a completely new list it means there should be no address to store inside the head pointer so in that case, the head pointer points to null. Create a new node and the head node will store the address of the newly created node.

2. Adding a new node to the List.

We have three cases for adding a new node in a singly linked list. We can add a node at the front of the list, at the end of the list, or anywhere in the list. 

• Adding a node at the front takes O(1) time complexity.
• Adding a node at the end takes O(n) time complexity.
• Adding a node anywhere in between takes O(n) time complexity. 

Read our post, Insertion in a Singly Linked List to understand the process of adding a new node in detail.

3. Search for a node in the list.

To search for a value in a linked list, we need to traverse the list to compare the value and in the worst case, it will take O(n) time. The below function will return true if the value is present in the list.

bool search(Node *head, int value){
    Node *current = head;
    //traverse list
    while(current != NULL){
        if(current->data == value)
           return true;
        current = current->next;   
    }
    return false;
}

4. Remove a node from the list.

We can remove a node from the front, end, or middle of the linked list and worst case it can take O(n) time complexity. Always remember to free the memory of the deleted node.

C++ Code Implementation of Singly Linked List.

//C++ Example of Singly Linked List
#include<iostream>
using namespace std;

class Node{
    public:
    int data;
    Node *next;
    //constructor
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};

//Add a node to the list
Node *addNode(Node *head, int data){

    Node *new_node = new Node(data);
    //add a new node when list is empty
    if(head == NULL)
      head = new_node;
    //adding new node at the front of the list  
    else{
        new_node->next = head;
        head = new_node;
    }
    return head;  
}

//Search a node in the list
bool search(Node *head, int value){
    Node *current = head;
    //traverse list
    while(current != NULL){
        if(current->data == value)
           return true;
        current = current->next;   
    }
    return false;
}
//Remove a node from the list
void deleteNode(Node* head, int position)
{
    Node* temp;
    Node* prev;
    temp = head;
    prev = head;
    for (int i = 0; i < position; i++) {
        if (i == 0 && position == 1) {
            head = head->next;
            free(temp);
        }
        else {
            if (i == position - 1 && temp) {
                prev->next = temp->next;
                free(temp);
            }
            else {
                prev = temp;
 
                // Position was greater than
                // number of nodes in the list
                if (prev == NULL)
                    break;
                temp = temp->next;
            }
        }
    }
}
//Traversing Linked List
void display(Node *head){
    Node *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}

int main(){
    Node *head = new Node(32);
    head = addNode(head, 20);
    head = addNode(head, 40);
    head = addNode(head, 12);

    cout<<"Singly Linked List: ";
    display(head);
    
    if(search(head, 20))
      cout<<"\nValue is present in the List";
    else
      cout<<"\nValue is not present in the List";

    deleteNode(head, 2);

    cout<<"\nSingly Linked List after deletion: ";
    display(head);

    return 0;    
}

Output:

Singly Linked List: 12 40 20 32
Value is present in the List
Singly Linked List after deletion: 12 20 32