Finding the minimum and maximum values in a linked list is a common task in computer programming and data analysis. Whether you are working in C or Java, linked lists offer an efficient way to store and manage collections of data elements. In this article, we will explore how to find the minimum and maximum values in a linked list using C and Java.
The first node in the list is called the head node, and the last node is called the tail node. The tail node’s next field points to a null value, indicating the end of the list. Let’s discuss our problem to find largest element in linked list in C programming and also find minimum value in linked list in C.
How To Find Minimum Value in Linked List in C and How To Find Largest Element in Linked List in C programming
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 will give a better understanding to find largest element in linked list in C++, C, Python and Java and find max value in linked list Java, C, C++, Python.
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 and Minimum 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: 2Time Complexity: O(n) is the time complexity to find minimum value in linked list in C++, Java and in Python and also O(n) will be the time complexity to find largest element in linked list in C++, Java and in Python, as list traversal is needed.
Conclusion
In conclusion, finding the smallest and largest element in a linked list can be accomplished by iterating through the list and comparing each node’s value with the current smallest or largest value. These operations have a time complexity of O(n), and can be optimized for larger linked lists.
Frequently Asked Questions Related to find largest element in linked list in C programming
Here are some FAQs related to find minimum value in linked list in C and to find largest element in linked list in C programming language.
Q1. What happens if the linked list is empty when we try to find the smallest or largest element?
Ans. If the linked list is empty, we cannot find the smallest or largest element, as there are no nodes to compare. In this case, we could return a default value or raise an error, depending on the requirements of the application.
Q2. Is it possible to find the smallest or largest element in a linked list using recursion instead of iteration?
Ans. Yes, it is possible to find the smallest or largest element in a linked list using recursion. However, recursion may not be the most efficient approach, as it can lead to stack overflow errors for very large linked lists. The iterative approach is generally preferred.
Q3. Can we find the smallest and largest element in a linked list in constant time?
Ans. No, it is not possible to find the smallest and largest element in a linked list in constant time, as we need to examine each element in the list to find the smallest or largest value. The time complexity of this operation is O(n), where n is the number of nodes in the linked list.
Q4. If the linked list contains duplicate values, which node’s value should be considered as the smallest or largest element?
Ans. If the linked list contains duplicate values, we can choose to consider any one of the nodes with the smallest or largest value as the smallest or largest element. However, this decision should be based on the requirements of the application and should be documented clearly in the code or documentation.