Find the largest node in Doubly linked list

Suppose that given linked list is combination of integer value. we are need to find largest node of this doubly linked list. We can solve this problem by using linked list traversal from front node to last node.

Process: When linked list is not empty then use one integer variable and assign front node value to this integer variable. Using of linked list pointer iterates linked list nodes are one by one visiting upcoming nodes. And check that linked list element value are greater than integer variable values . Then assign this value to resultant variable. This process are execute until not found last linked list node. This process are time complexity is O(n).

Suppose we are inserted the following (14, 31, 12, 15, 11, 25 ) node in a sequence.

Find the largest node

Here given code implementation process.

//C Program
//Find out max value node in doubly linked list
#include <stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node
{
  int data;
  struct Node*next;
  struct Node*prev;
};


//insert Node element of end of linked list
void insert(struct Node**head,int value)
{

  //Create a dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL)
  {
    printf("Memory overflow\n");
  }
  else
  {
    //set data value
    node->data=value;
    node->next=NULL;
    node->prev=NULL;
    if(*head==NULL)
    {
      *head=node;
    }
    else
    {
      struct Node*temp=*head;
      //find last node
      while(temp!=NULL && temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add new node to last positions
      temp->next=node;
      node->prev=temp;

    }
  }
}
//display element of Node
void display(struct Node*temp)
{

  if(temp==NULL)
  {
    printf("Empty linked list");
  }
  else
  {
    printf("\nLinked List Elements :");

    //Traverse doubly linked list from front to rear
    while(temp!=NULL)
    {
      //print node value
      printf("%d  ",temp->data);
      temp=temp->next;
    }
  }

}
//Find largest node element
void  big_node(struct Node*temp)
{
  if(temp!=NULL)
  {

    int big=temp->data;
    temp=temp->next;
    //get remove node
    while(temp!=NULL)
    {
      if(temp->data>big)
      {
        big=temp->data;
      }
      temp=temp->next;
    }
    printf("\nBig Element : %d\n",big);


  }
  else
  {
    //when linked list is empty
    printf("Empty linked list");

  }
}

int main()
{
  //set node pointer value
  struct Node*head=NULL;

  //Insert element of linked list
  insert(&head,14);
  insert(&head,31);
  insert(&head,12);
  insert(&head,15);
  insert(&head,11);
  insert(&head,25);
  //display all node
  display(head);

  big_node(head);
  return 0;
}

Output

Linked List Elements :14  31  12  15  11  25  
Big Element : 31
//C++ Program
//find maximum element in doubly linked list
#include <iostream> 
using namespace std;
//create structure
struct Node
{
  int data;
  Node*next;
  Node*prev;
};
class DoublyList
{
  struct Node*head;
public:
  DoublyList();
  void insert(int);
  void display();
  void big_node();
};
//set inital value
DoublyList::DoublyList()
{
  head=NULL;
}

//insert a linked list Node element
void DoublyList:: insert(int value)
{
    //Create a dynamic node
  Node*node=new Node;
  if(node==NULL)
  {
    cout<<"Memory overflow\n";
  }
  else
  {
    //set data value
    node->data=value;
    node->next=NULL;
    node->prev=NULL;
    if(head==NULL)
    {
      head=node;
    }
    else
    {
      Node*temp=head;
      //find last node
      while(temp!=NULL && temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add new node to last positions
      temp->next=node;
      node->prev=temp;

    }
  }
}
//display all element of doubly linked list
void DoublyList::display()
{

  if(head==NULL)
  {
    //when linked list is empty
    cout<<"Empty linked list";
  }
  else
  {
    cout<<"Linked List Element :";
    Node*temp=head;
    while(temp!=NULL)
    {
      //display node elemement
      cout<<" "<<temp->data;
      temp=temp->next;
    }
  }

}

//Find largest node element
void DoublyList:: big_node()
{
  if(head!=NULL)
  {
    struct Node*temp=head;
    int big=temp->data;
    temp=temp->next;
    //get remove node
    while(temp!=NULL)
    {
      if(temp->data>big)
      {
        big=temp->data;
      }
      temp=temp->next;
    }
    cout<<"\nBig Element : "<<big<<endl;


  }
  else
  {
    //when linked list is empty
    cout<<"Empty linked list";

  }
}


int main()
{
  DoublyList obj=DoublyList();
  //Insert element of linked list
  obj.insert(14);
  obj.insert(31);
  obj.insert(12);
  obj.insert(15);
  obj.insert(11);
  obj.insert(25);
  obj.display();
  obj.big_node();
  return 0;
}

Output

Linked List Element : 14 31 12 15 11 25
Big Element : 31
//Java program
//Find largest node in doubly linked list
class Node
{
  public int data;
  public Node next,prev;
}
public class LinkedList
{

  //head of linked list
  public Node head;
  //Class constructors
  LinkedList()
  {
    head=null;
  } 
    //add newly created node at End of linked list
  public void insert(int value)
  {
    //Create a dynamic node
    Node node=new Node();
    //add node value and pointer value
    node.data=value;
    node.next=null;
    node.prev=null;
    //when no element
    if(head==null) head=node;
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null) temp=temp.next;
      //add node
      node.prev=temp;
      temp.next=node;
    }
  }
  //display all Linked List node value
  public void display()
  {
    if(head!=null)
    {
      System.out.print(" Linked List Element :");
      Node temp=head;
      while(temp!=null)
      {
        //display node value
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
    }
    else
    {
      System.out.println("Empty Linked list"); 
    }
  }
  //Find largest node element
  public void  bigNode()
  {
    if(head!=null)
    {
      Node temp=head.next;
      int big=head.data;
      //get remove node
      while(temp!=null)
      {
        if(temp.data>big)
        {
          big=temp.data;
        }
        temp=temp.next;
      }
      System.out.println("\nBig Element :"+big);


    }
    else
    {
      //when linked list is empty
      System.out.println("Empty linked list");

    }
  }


  public static void main(String[] args) 
  {

    LinkedList obj=new LinkedList();

    //Insert element of linked list
    obj.insert(14);
    obj.insert(31);
    obj.insert(12);
    obj.insert(15);
    obj.insert(11);
    obj.insert(25);
    
    //display all node
    obj.display();

    obj.bigNode();

  }
}

Output

Linked List Element : 14 31 12 15 11 25
Big Element : 31
#Python Program
#Find largest node in doubly linked list
class Node:
  def __init__(self,data):
    self.data=data
    self.next=None
    self.prev=None

#create class LinkedList  
class LinkedList:
  def __init__(self):
    #set initial head value
    self.head=None


  #insert new node to end of Linked List  
  def insert(self,data):
    #make a new node
    node=Node(data)

    if(self.head==None):
      #when empty list
      self.head=node
    else:
      temp=self.head
      #find last node
      while temp.next!=None:
        temp=temp.next
      #add node  
      temp.next=node
      node.prev=temp
  #Find out maximum element in doubly linked list   
  def bigNode(self):
    if self.head==None:
      print("Linked List Empty : ")
    else:
      temp=self.head.next
      big=self.head.data
      while temp!=None:
        if(big<temp.data):
          #new big element
          big=temp.data  
        temp=temp.next
        
      print("Big node : ",big)

  #view all node values  
  def display(self):
    if self.head==None:
      print("Linked List Empty : ")
    else:  
      temp=self.head
      print("Linked List Elements : ")

      while(temp!=None):
        #print node value
        print(temp.data,end=" ")
        temp=temp.next
      print("\n")
def main():

  #Create Object of class LinkedList
  obj=LinkedList()
   
  #Insert element of linked list
  obj.insert(14);
  obj.insert(31);
  obj.insert(12);
  obj.insert(15);
  obj.insert(11);
  obj.insert(25);
  #display all node
  obj.display();

  obj.bigNode();
  

if(__name__=="__main__"):
  main()

Output

Linked List Elements : 
14 31 12 15 11 25 

Big node :  31
//C# program
//Find largest node in doubly linked list
using System;
public class Node
{
  public int data;
  public Node next,prev;
}
public class LinkedList
{

  //head of linked list
  public Node head;
  //Class constructors
  LinkedList()
  {
    head=null;
  } 
  //add newly created node at End of linked list
  public void insert(int value)
  {
    //Create a dynamic node
    Node node=new Node();
    //add node value and pointer value
    node.data=value;
    node.next=null;
    node.prev=null;
    //when no element
    if(head==null) head=node;
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null) temp=temp.next;
      //add node
      node.prev=temp;
      temp.next=node;
    }
  }
  //display all Linked List node value
  public void display()
  {
    if(head!=null)
    {
      Console.Write(" Linked List Element :");
      Node temp=head;
      while(temp!=null)
      {
        //display node value
        Console.Write("  "+temp.data);
        temp=temp.next;
      }
    }
    else
    {
      Console.WriteLine("Empty Linked list"); 
    }
  }
  //Find largest node element
  public void  bigNode()
  {
    if(head!=null)
    {
      Node temp=head.next;
      int big=head.data;
      //get remove node
      while(temp!=null)
      {
        if(temp.data>big)
        {
          big=temp.data;
        }
        temp=temp.next;
      }
      Console.WriteLine("\nBig Element :"+big);


    }
    else
    {
      //when linked list is empty
      Console.WriteLine("Empty linked list");

    }
  }


  public static void Main(String[] args) 
  {

    LinkedList obj=new LinkedList();

    //Insert element of linked list
    obj.insert(14);
    obj.insert(31);
    obj.insert(12);
    obj.insert(15);
    obj.insert(11);
    obj.insert(25);

    //display all node
    obj.display();

    obj.bigNode();

  }
}

Output

Linked List :  14  31  12  15  11  25
Big Element : 31
<?php
//Php program 
//Find maximum element in doubly linked list
class Node
{
  public $data;
  public $next;
  public $perv;
  function __construct($data)
  {
    $this->data = $data;
    $this->next = NULL;
    $this->prev = NULL;
  }
}
class LinkedList
{

  private $head;
  function __construct()
  {
    $head=NULL;
  }
  /*
  * Append the Given data value at Beginning of linked list
  * Fun : insert
  * Parm: data value
  *@return None
  */
  function insert($data)
  {
    //Create a dynamic node
    $node=new Node($data);
    if($node==NULL)
    {
      echo "Memory overflow\n";
    }
    else
    {
      if($this->head==NULL)
      {
        $this->head=$node;
      }
      else
      {
        $temp=$this->head;
        //find last node
        while($temp!=NULL && $temp->next!=NULL)
        {
          $temp=$temp->next;
        }
        //add new node to last positions
        $temp->next=$node;
        $node->prev=$temp;

      }
    }
  }
    //Display all inserted node in linked list
  function display()
  {
    if($this->head==NULL)
    {
      echo "Empty Linked List";
    }
    else
    {
      $temp=$this->head;
      echo "Doubly Linked List :";
      while($temp!=NULL)
      {
        //display node value
        echo "  ".$temp->data;
        $temp=$temp->next; //visit to next node
      }
    }   
  }
  //find largest node 
  public function  big_node()
  {
    if($this->head==NULL)
    {
      //when linked list is empty
      echo "Empty linked list";
    }
    else
    {
      $big=$this->head->data;
      $temp=$this->head->next;
      
     
      while($temp!=NULL)
      {
        if($big<$temp->data)
        {
          $big=$temp->data;
        }
        $temp=$temp->next;
        
      }
      echo "\nBig node is ".$big."\n";


    }
  }
}
function main()
{
  //Make a object of LinkedList class
  $obj= new LinkedList();


  //Insert element of linked list
  $obj->insert(14);
  $obj->insert(31);
  $obj->insert(12);
  $obj->insert(15);
  $obj->insert(11);
  $obj->insert(25);
  $obj->display();
  $obj->big_node();
}
main();
?>

Output

Doubly Linked List :  14  31  12  15  11  25
Big node is 31


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved