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; }
#includeusing 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.
FAQs
- How to traverse through a linked list?
Using loops such as for loop, While loop , etc.
-
Where is the singly linked list applicable?
A single linked list is used in:- Polynomial Manipulation representation.
- Sparse Matrices
- Mailing Lists etc.
-
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.