Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Solution Approach
2.1.
Algorithm 
2.2.
C++ code
2.3.
Algorithm Complexity
3.
Frequently Asked Questions
3.1.
What is a linked list?
3.2.
What is the key difference between a singly linked list and a doubly-linked list?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Largest and Smallest Element in a Singly Linked List

Author Riya
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
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);
}

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)

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

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

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.

 

Conclusion

This article discussed the problem of finding the “Largest and Smallest Element in a Singly Linked List”, the approach to solving 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 Coding Ninjas Studio.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Previous article
Sort a Linked List that is Sorted Alternating Ascending and Descending Orders
Next article
Rearrange a Linked List such that all Even and Odd Positioned Nodes are Together
Live masterclass