How to find the largest element of a doubly-linked list

Gorakhnath yadav
Last Updated: May 13, 2022

Introduction

In this blog, we will learn to find the largest element of a doubly linked list. Let's first begin with a brief introduction of how doubly-linked lists 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-

Given doubly linked list-

78->65->97->87->45->23->54

Largest element- 97

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;
}

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.

Frequently asked questions

  1. What is a doubly-linked list?
    Doubly linked list a data structure with nodes linked to each other using pointers, in doubly nodes consists of data, a pointer to the previous node and a pointer to the next node.
  2. Why do we use a doubly-linked list?
    A doubly linked list is generally used to perform navigation operations and navigate in front and back directions. 
  3. Describe the advantages of a doubly linked list?
    It can be traversed in both directions. Insert and delete operations are more efficient in the doubly linked list.
  4. Describe the disadvantages of the double-linked list?
    It takes more space to store the extra pointer. Also, each operation needs extra effort to handle this extra pointer. 
  5. Is linked list a linear data structure or a circular data structure?
    A linked list is a linear data structure in which we can traverse in either direction, but we can't move to the first element directly from the last element. 

Key takeaways

In this blog, we learn how to find the largest element of a doubly linked list.

To do so, we create a temporary node and initialize it with the head of the doubly linked list. Then we traverse through the linked list and compare the value of each node with the value of the maximum. Whenever we find a node with a value greater than the maximum value, we update it. If the node value is smaller than the value of the maximum, we continue the traversal. Once we reach the tail of the linked list, we return the value of the maximum, which contains the largest element of the doubly linked.

You can learn more about the linked lists and also practice similar problems on the CodeStudio.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think