Largest and Smallest Element in a Singly Linked List

Introduction-  

This article will discuss the problem of finding the “Largest and Smallest Element in a Singly Linked List” and its solution. Before jumping into the details of the problem and approach to solve it, you need to know about the linked list data structure.
 

Now, let’s understand the problem. In this problem, a singly linked list is given, and we have to find the value of the largest and smallest element in a singly linked list that is given in the problem.

Let’s take an example to understand it:

Assume the given linked list is : 1 -> 4 -> 5 -> 9 -> 8 -> 5 -> 2

All the values of the nodes present in the linked list are 1, 4, 5, 9, 8, 5, 2. Here we can see that 9 and 1 are the largest and smallest elements respectively among all the nodes’ values.

So, our code should return 9 and 1 as the largest and smallest element in a Singly linked list which is taken in the above example.

Solution Approach

We have to find the largest and smallest element in a singly linked list, so our solution approach is to traverse each node of the singly linked list and get the largest and smallest of all the nodes’ values. 

Algorithm -

Step 1. Create a class ‘Node’ for creating the linked lists.

Step 2. Then create the function “largestAndSmallest()” to print the largest and smallest element in a singly linked list, which will accept one parameter - pointer to the head node of the given linked list.

Step 3.  Initialize two variables, “smallestElement = INT_MAX” and “largestElement = INT_MIN”, to store the current smallest and largest elements, respectively, after traversing each node of the given singly linked list.

Step 4. Initialize a pointer to the node as “curr_node = head” and traverse the whole linked list with the help of this pointer in a while loop. Compare the value of the current node with “smallestElement” and “largestElement” and update them.

Step 5. Finally, after traversing the linked list, print the values of the smallest and largest elements in the given singly linked list.

C++ code:

#include <bits/stdc++.h>
using namespace std;

// Class for creating nodes of the linked list
class Node {
   public:
      int data;
      Node* next;
      Node(int val) {
           this->data = val;
           this->next = NULL;
      }
};

// Function to print the linked list
void printList(Node* head)
  {
     Node* curr_node = head;
     while(curr_node != NULL)
     {
          if(curr_node->next == NULL) cout<< curr_node->data <<" ";
          else {
              cout<<curr_node->data<<" -> ";
          }
          curr_node = curr_node->next;
     }
      cout<<endl;
  }

// Function to find the smallest and largest element of a Singly Linked list
void smallestAndLargest(Node* head)
 {
      int smallestElement = INT_MAX;
      int largestElement = INT_MIN;
 
      Node* curr_node = head;
 
      while(curr_node != NULL)
      {
           if(curr_node->data < smallestElement) smallestElement = curr_node->data;
           if(curr_node->data > largestElement) largestElement = curr_node->data;
    
            curr_node = curr_node->next;
       }
    
        cout<<"The smallest and largest element in the given singly linked list are "<<smallestElement<<" and  "<<largestElement<<"         respectively"<<endl; 
 }
int main()
{
    Node* head = new Node(1);
    head->next = new Node(4);
    head->next->next = new Node(5);
    head->next->next->next = new Node(9);
    head->next->next->next->next = new Node(8);
    head->next->next->next->next->next = new Node(5);
    head->next->next->next->next->next->next = new Node(2);

    cout<<"The given linked list is: "<<endl;
    printList(head);

    // Call the function to find the smallest and largest element of a Singly Linked list
    smallestAndLargest(head);
}

Output:
The given linked list is: 
1 -> 4 -> 5 -> 9 -> 8 -> 5 -> 2 
The smallest and largest element in the given singly linked list are 1 and  9 respectively

Algorithm Complexity: 

Time Complexity: O(N)

In the function “largestAndSmallest()”, we have created a “while loop” to one by one traverse all the nodes of the given linked list. So, the time complexity is O(N), where ‘N’ is the number of nodes in the given linked list.

Space Complexity: O(1) 

As we have used constant space, so the space complexity is O(1)

Frequently asked questions-

1. What is a linked list?

A linked list is a linear data structure that is formed by connected nodes. Each node has a value associated with it and the pointer(s) to its directly connected node(s).   

2. What is the key difference between a singly linked list and a doubly-linked list?

  A singly-linked list is unidirectional, which means that the node of a singly linked list contains the pointer to its next node only. In contrast, a doubly-linked list is bidirectional, and its node contains the pointer to its next and previous nodes.

Key takeaways-

This article discussed the problem of finding the “Largest and Smallest Element in a Singly Linked List”, approach to solve the problem, its C++ implementation, and its time and space complexities. If you want to practice problems on a linked list, then you can visit codestudio.

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.