How to Find the Largest Element of a Doubly-Linked list

Introduction

In this blog, we will learn to find the largest element of a doubly linked list Data Structure. Let's first begin with a brief introduction of how Doubly Linked List work. Each node has three components in doubly linked lists- data, a pointer to the next node, and another pointer to the previous node. The next pointer of the last node or tail points to the null pointer. Similarly, the previous pointer of the first or the head node points to the null. For example-

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Solution using a single variable

Now we need to devise a method to find the largest element of a doubly linked list. To do that, we will have to create a temporary node. Let's say we call it maximum. It will hold the largest element of a doubly linked list. To start with, we initialize the maximum with the head of the linked list. Then we traverse through the linked list and compare the values of the nodes with the value of the maximum. If we find the value of a node greater than the current value of the maximum, we update it. Else we continue traversal until we reach the tail of the linked list.

Now let’s have a look at the algorithm and implementation for this method-

Algorithm

• Take the linked list as user input
• Create a variable node to hold the node with the largest element of a doubly linked list.
• Initialize this variable with the first node.
• Traverse through the linked list and compare each node’s data with the data of the maximum -

 -If data in the node is greater than the data in maximum, we update it.

 -Else, we continue traversal. 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
//Structure for a node in the doubly linked list.
struct node
{
    int data;
    struct node *next;
    struct node *prev;
};
//Function to find the largest element of a doubly linked list.
int largestnode(struct node** headr)
{
    //Declare two nodes, one for storing the maximum value, 
    //another for traversal of the linked list.
    struct node *maximum, *itr;
    //Initialise both the nodes with the head of the linked list.
    itr=maximum=*headr;
    while(itr!=nullptr)
    {
        //When the value of the cureent node is greater than the 
        //maximum value till now.
        if(itr->data>maximum->data)
        {
            maximum=itr;
        }
        itr=itr->next;
    }
    //Returning the maximum value.
    return maximum->data;
}
//Function to push nodes into the list.
void push(struct node** headr, int new_val)
{
    //Creatng a new node.
    struct node* new_node= (struct node*)malloc(sizeof(struct node));
    //Putting the value in the node.
    new_node->data= new_val;
    //Previous pointer to the null as node is added in the 
    //beginning.
    new_node->prev=nullptr;
    //Linking the node to the list.
    new_node->next=(*headr);
    //Chaanging the previous pointer of the head to the new node.
    if((*headr)!=nullptr)
    {
        (*headr)->prev = new_node;
    }
    //Shifting the head pointer to the new node.
    *headr= new_node;
}
//Driver function.
int main()
{
    //Creating an empty list.
    struct node* head=nullptr;
    //Enter no  of nodes in the node.
    int size;
    cout<<"Enter the number of nodes in the list- ";
    cin>>size;
    //Pushing the nodes in it.
    cout<<"Enter the nodes in the list- ";
    for(int i=0;i<size;i++)
    {
        int a;
        cin>>a;
        push(&head,a);
    }
    //To find the largest element of a doubly linked list.
    int maxelement=largestnode(&head);
    cout<<maxelement;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input-

8
99 78 55 245 68 19 240 255

Output-

Enter the number of nodes in the list-
Enter the nodes in the list- 
255

Complexity Analysis

The time complexity of this approach will be O(N), as we need a traversal of the linked list.

The space complexity of this approach will be constant, i.e., O(1), because we don't need any extra space.