Find the smallest and largest elements in a singly linked list

Linked list has various elements or items of data in its structure. Below it is given a singly linked list with various elements where we will see how to find the maximum value in the linked list in which we will look for the greatest value in the given linked list and how to find the smallest value in the linked list.

Let’s try to understand how to find the maximum value in the linked list and how to find the smallest value in the linked list with the help of an example.

Suppose the linked list is:

In this list, the smallest value is 2 and the maximum value is 9. So, the final output will be:

  • Maximum Value: 9
  • Smallest Value: 2

Input :

Output :: 9, Smallest value: 2.

Explanation: As the maximum value is 9 and the smallest Value is 2, we are printing 9 and 2.

This question is not a tricky one. We just have to make use of simple list traversal in the given Linked list to solve this problem. Let us have a glance at the approach.

Approach for how to find the maximum value in the linked list

The approach is going to be simple.

  • We will create two variables min and max.

  • min will be initialized with INT_MAX and max will be initialized with INT_MIN.

  • We are using INT_MAX because all the integers are lesser than it, and INT_MIN because all the integers are greater than it. With the help of these, finding the minimum and maximum becomes easy.

  • Now, we will traverse through the given list, and for every node, we will have two checks.

    1) If the data of the current node is less than the data of min, we will store the current node’s data in min.

    2) Else, If the data of the current node is greater than max, we will store the current node’s data in max.

  • After reaching the end of the list, min and max will contain the smallest and the largest element, respectively.

Algorithm to find the maximum value in the linked list

  • Create a variable max and initialize it with INT_MIN.
  • Traverse through the list and for every node, compare its data with max.
  • If the current node’s data is greater than max, then store the value of the current node’s data in max.
  • In the end, max will contain the Maximum value of the list.

Algorithm to find the smallest value in the linked list

  • Create a variable min and initialize it with INT_MAX.
  • Traverse through the list and for every node, compare its data with min.
  • If the current node’s data is lesser than min, then store the value of the current node’s data in min.
  • In the end, min will contain the Maximum value of the list.

Dry Run

How to find the Maximum value in the linked list

How to find the smallest value in the linked list

Code Implementation on how to find maximum value in linked list and how to find the smallest value in linked list

#include
#include
#include
struct Node {
    int data;
    struct Node* next;
};
int largestElement(struct Node* head)
{
    int max = INT_MIN;
    while (head != NULL) {
        if (max < head->data)
            max = head->data;
        head = head->next;
    }
    return max;
}
int smallestElement(struct Node* head)
{
    int min = INT_MAX;
    while (head != NULL) {
        if (min > head->data)
            min = head->data;
        head = head->next;
    }
    return min;
}
void push(struct Node** head, int data)
{
    struct Node* newNode =
        (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = (*head);
    (*head) = newNode;
}
// Display linked list.
void printList(struct Node* head)
{
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}
int main()
{
    struct Node* head = NULL;
    push(&head, 9);
    push(&head, 7);
    push(&head, 2);
    push(&head, 5);
    
    printf("Linked list is: ");
    printList(head);
    printf("Maximum element in linked list: ");
    int max_element = largestElement(head);
    printf("%d\n",max_element);
    printf("Minimum element in linked list: ");
    int small = smallestElement(head);
     printf("%d\n",small);
  
    return 0;
}

#include 

using namespace std;

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

int largestElement(struct Node* head)
{

    int max = INT_MIN;

    while (head != NULL) {

        if (max < head->data)
            max = head->data;
        head = head->next;
    }
    return max;
}

int smallestElement(struct Node* head)
{

    int min = INT_MAX;


    while (head != NULL) {

        if (min > head->data)
            min = head->data;

        head = head->next;
    }
    return min;
}

void push(struct Node** head, int data)
{

    struct Node* newNode =
        (struct Node*)malloc(sizeof(struct Node));

    newNode->data = data;

    newNode->next = (*head);

    (*head) = newNode;
}

// Display linked list.
void printList(struct Node* head)
{
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main()
{
    struct Node* head = NULL;
    push(&head, 9);
    push(&head, 7);
    push(&head, 2);
    push(&head, 5);
    
    cout << "Linked list is: " << endl;

    printList(head);
    cout << "Maximum element in linked list: ";

    cout << largestElement(head) << endl;
    cout << "Minimum element in linked list: ";

    cout << smallestElement(head) << endl;

    return 0;
}
public class PrepBytes
{

static class Node
{
    int data;
    Node next;
}
static Node head = null;

static int largestElement(Node head)
{
    
    int max = Integer.MIN_VALUE;

    while (head != null)
    {

        if (max < head.data)
            max = head.data;
        head = head.next;
    }
    return max;
}

static int smallestElement(Node head)
{

    int min = Integer.MAX_VALUE;

    while (head != null)
    {

        if (min > head.data)
            min = head.data;

        head = head.next;
    }
    return min;
}

static void push(int data)
{

    Node newNode = new Node();

    newNode.data = data;

    newNode.next = (head);

    (head) = newNode;
}

static void printList(Node head)
{
    while (head != null) {
        System.out.print(head.data + " -> ");
        head = head.next;
    }
    System.out.println("NULL");
}


public static void main(String[] args)
{
    push( 9);
    push( 7);
    push( 2);
    push( 5);
    System.out.println("Linked list is: ") ;
    printList(head);
    System.out.print("Maximum element in linked list: ");
    System.out.println(largestElement(head));
    System.out.print("Minimum element in linked list: ");
    System.out.print(smallestElement(head));
}
}
class Node:

    def __init__(self):
        self.data = None
        self.next = None

head = None

def largestElement(head):

    max = -32767
    while (head != None):
        if (max < head.data) :
            max = head.data
        head = head.next
    
    return max

def smallestElement(head):

    min = 32767

    while (head != None) :
        if (min > head.data) :
            min = head.data
        head = head.next
    
    return min

def push( data) :

    global head

    newNode = Node()
    newNode.data = data
    newNode.next = (head)
    (head) = newNode

def printList( head) :

    while (head != None) :
        print(head.data ,end= " -> ")
        head = head.next
    
    print("None")

# Driver code

# Start with empty list
# head = new Node()

# Using push() function to construct
# singly linked list
# 17.22.13.14.15
push( 9)
push( 7)
push( 2)
push( 5)
print("Linked list is : ")

printList(head)
print("Maximum element in linked list: ",end="")

print(largestElement(head))
print("Minimum element in linked list: ",end="")

print(smallestElement(head),end="")

Output

Linked list is:

5 -> 2 -> 7 -> 9 -> NULL

Maximum element in linked list: 9

Minimum element in linked list: 2

Time Complexity: O(n), as list traversal is needed.

Conclusion

So, in this article, we have tried to explain the most efficient approach on how to find the maximum value in the linked list and understood how well and efficiently we drew the output.We have also seen how to find the smallest value in the linked list. If you want to solve more questions on Linked List, which our expert mentors at PrepBytes curate, you can follow this Link.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Student management system using linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. How to traverse through a linked list?
    Using loops such as for loop, While loop , etc.
  1. Where is the singly linked list applicable?
    A single linked list is used in:

    • Polynomial Manipulation representation.
    • Sparse Matrices
    • Mailing Lists etc.
  2. What are the Operations which are used in a singly linked list?
    Operations that are used in Singly linked lists are:

    • Traversal
    • Insertion
    • Deletion
    • Sort etc.

Leave a Reply

Your email address will not be published. Required fields are marked *