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 solving 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);
}

You can also try this code with Online C++ Compiler

Run Code

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)