Given a doubly-linked list, find the largest node in the doubly linked list.
Examples:
Input: 10->8->4->23->67->88 Largest node is: 88 Output: 88 Input : 34->2->78->18->120->39->7 Largest node is: 120 Output :120
Approach Used:
- Initialize the temp and max pointer to head nodes.
- Traverse the whole list.
- if temp’s data is greater than max’s data, then put max = temp.
- move on to the next node.
Implementation:
C++
/* C++ Program to find the largest nodes in doubly linked list */ #include <iostream> using namespace std; // Create a node of the doubly linked list struct Node { int data; struct Node* next; struct Node* prev; }; /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the Doubly Linked List */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* since we are adding at the beginning, prev is always NULL */ new_node->prev = NULL; /* link the old list of the new node */ new_node->next = (*head_ref); /* change prev of head node to new node */ if ((*head_ref) != NULL) (*head_ref)->prev = new_node; /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to find the largest nodes in Doubly Linked List */ int LargestInDLL( struct Node** head_ref) { struct Node *max, *temp; /* initialize two pointer temp and max on the head node */ temp = max = *head_ref; // traverse the whole doubly linked list while (temp != NULL) { /* if temp's data is greater than max's data, then put max = temp and return max->data */ if (temp->data > max->data) max = temp; temp = temp->next; } return max->data; } // Driver code int main() { // Start with the empty list struct Node* head = NULL; // Let us create a linked list push(&head, 20); push(&head, 14); push(&head, 181); push(&head, 100); cout << LargestInDLL(&head); return 0; } // This code is contributed by shubhamsingh10 |
C
/* Program to find the largest nodes in doubly linked list */ #include <stdio.h> #include <stdlib.h> // Create a node of the doubly linked list struct Node { int data; struct Node* next; struct Node* prev; }; /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the Doubly Linked List */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* since we are adding at the beginning, prev is always NULL */ new_node->prev = NULL; /* link the old list of the new node */ new_node->next = (*head_ref); /* change prev of head node to new node */ if ((*head_ref) != NULL) (*head_ref)->prev = new_node; /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to find the largest nodes in Doubly Linked List */ int LargestInDLL( struct Node** head_ref) { struct Node *max, *temp; /* initialize two pointer temp and max on the head node */ temp = max = *head_ref; // traverse the whole doubly linked list while (temp != NULL) { /* if temp's data is greater than max's data, then put max = temp and return max->data */ if (temp->data > max->data) max = temp; temp = temp->next; } return max->data; } int main() { // Start with the empty list struct Node* head = NULL; // Let us create a linked list push(&head, 20); push(&head, 14); push(&head, 181); push(&head, 100); printf ( "%d" , LargestInDLL(&head)); return 0; } |
Java
// Java Program to find the largest // nodes in doubly linked list class GFG { // Create node of the doubly linked list static class Node { int data; Node next; Node prev; }; // UTILITY FUNCTIONS // Function to insert a node at the // beginning of the Doubly Linked List static Node push(Node head_ref, int new_data) { // allocate node Node new_node = new Node(); // put in the data new_node.data = new_data; // since we are adding at the // beginning, prev is always null new_node.prev = null ; // link the old list of the new node new_node.next = (head_ref); // change prev of head node to new node if ((head_ref) != null ) (head_ref).prev = new_node; // move the head to point to the new node (head_ref) = new_node; return head_ref; } // Function to find the largest // nodes in Doubly Linked List static int LargestInDLL(Node head_ref) { Node max, temp; // initialize two pointer temp // and max on the head node temp = max = head_ref; // traverse the whole doubly linked list while (temp != null ) { // if temp's data is greater than // max's data, then put max = temp // and return max.data if (temp.data > max.data) max = temp; temp = temp.next; } return max.data; } public static void main(String args[]) { // Start with the empty list Node head = null ; // Let us create a linked list head = push(head, 20 ); head = push(head, 14 ); head = push(head, 181 ); head = push(head, 100 ); System.out.printf( "%d" , LargestInDLL(head)); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 program to find largest # node in doubly linked list # Node of the doubly linked list class Node: def __init__( self , data): self .data = data self .prev = None self . next = None # Function to find pair whose product # equal to given value x def pairProduct(head, x): # Set two pointers, # first to the beginning of DLL # and second to the end of DLL. first = head second = head while (second. next ! = None ): second = second. next # To track if we find a pair or not found = False # The loop terminates when either of two pointers # become None, or they cross each other (second.next # == first), or they become same (first == second) while (first ! = None and second ! = None and first ! = second and second. next ! = first) : # pair found if ((first.data * second.data) = = x) : found = True print ( "(" , first.data, ", " , second.data, ")" ) # move first in forward direction first = first. next # move second in backward direction second = second.prev else : if ((first.data * second.data) < x): first = first. next else : second = second.prev # if pair is not present if (found = = False ): print ( "No pair found" ) # A utility function to insert a new node at the # beginning of doubly linked list def push( head, data): temp = Node( 0 ) temp.data = data temp. next = temp.prev = None if (head = = None ): (head) = temp else : temp. next = head (head).prev = temp (head) = temp return head """ Function to find the largest nodes in Doubly Linked List """ def LargestInDLL( head_ref): max = None temp = None """ initialize two pointer temp and max on the head node """ temp = max = head_ref # traverse the whole doubly linked list while (temp ! = None ): """ if temp's data is greater than max's data, then put max = temp and return max.data """ if (temp.data > max .data): max = temp temp = temp. next return max .data # Driver Code if __name__ = = "__main__" : # Start with the empty list head = None # Let us create a linked list head = push(head, 20 ) head = push(head, 14 ) head = push(head, 181 ) head = push(head, 100 ) print ( LargestInDLL(head)) # This code is contributed by Arnab Kundu |
C#
// C# Program to find the largest // nodes in doubly linked list using System; class GFG { // Create node of the doubly linked list public class Node { public int data; public Node next; public Node prev; }; // UTILITY FUNCTIONS // Function to insert a node at the // beginning of the Doubly Linked List static Node push(Node head_ref, int new_data) { // allocate node Node new_node = new Node(); // put in the data new_node.data = new_data; // since we are adding at the // beginning, prev is always null new_node.prev = null ; // link the old list of the new node new_node.next = (head_ref); // change prev of head node to new node if ((head_ref) != null ) (head_ref).prev = new_node; // move the head to point to the new node (head_ref) = new_node; return head_ref; } // Function to find the largest // nodes in Doubly Linked List static int LargestInDLL(Node head_ref) { Node max, temp; // initialize two pointer temp // and max on the head node temp = max = head_ref; // traverse the whole doubly linked list while (temp != null ) { // if temp's data is greater than // max's data, then put max = temp // and return max.data if (temp.data > max.data) max = temp; temp = temp.next; } return max.data; } // Driver code public static void Main(String[] args) { // Start with the empty list Node head = null ; // Let us create a linked list head = push(head, 20); head = push(head, 14); head = push(head, 181); head = push(head, 100); Console.Write( "{0}" , LargestInDLL(head)); } } // This code contributed by Rajput-Ji |
Javascript
<script> // javascript Program to find the largest // nodes in doubly linked list // Create node of the doubly linked list class Node { constructor(val) { this .data = val; this .prev = null ; this .next = null ; } } // UTILITY FUNCTIONS // Function to insert a node at the // beginning of the Doubly Linked List function push(head_ref , new_data) { // allocate node var new_node = new Node(); // put in the data new_node.data = new_data; // since we are adding at the // beginning, prev is always null new_node.prev = null ; // link the old list of the new node new_node.next = (head_ref); // change prev of head node to new node if ((head_ref) != null ) (head_ref).prev = new_node; // move the head to point to the new node (head_ref) = new_node; return head_ref; } // Function to find the largest // nodes in Doubly Linked List function LargestInDLL(head_ref) { var max, temp; // initialize two pointer temp // and max on the head node temp = max = head_ref; // traverse the whole doubly linked list while (temp != null ) { // if temp's data is greater than // max's data, then put max = temp // and return max.data if (temp.data > max.data) max = temp; temp = temp.next; } return max.data; } // Start with the empty list var head = null ; // Let us create a linked list head = push(head, 20); head = push(head, 14); head = push(head, 181); head = push(head, 100); document.write(LargestInDLL(head)); // This code contributed by umadevi9616 </script> |
Output
181
Time Complexity: O(n)
Auxiliary Space : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!